一、比较排序

### 1. 冒泡排序

算法描述： 依次比较相邻元素，若逆序则交换。每一趟将最大元素”冒泡”到末尾，共 n-1 趟。

 void BubbleSort(int A[], int n){
     int i, j, tmp;
     for(i = 0; i < n-1; i++){
         for(j = 0; j < n-1-i; j++){
             if(A[j] > A[j+1]){
                 tmp = A[j];
                 A[j] = A[j+1];
                 A[j+1] = tmp;
             }
         }
     }
 }

算法分析：

• 时间复杂度：最坏 O(n²)，最好 O(n)（优化后）
• 空间复杂度：O(1)
• 稳定性：稳定

---

2. 选择排序

算法描述： 每趟从待排序序列中选择最小元素，与当前位置交换。

 void SelectSort(int A[], int n){
     int i, j, min, tmp;
     for(i = 0; i < n-1; i++){
         min = i;
         for(j = i+1; j < n; j++){
             if(A[j] < A[min]) min = j;
         }
         if(min != i){
             tmp = A[i];
             A[i] = A[min];
             A[min] = tmp;
         }
     }
 }

算法分析：

• 时间复杂度：O(n²)
• 空间复杂度：O(1)
• 稳定性：不稳定

---

3. 插入排序

算法描述： 将 L[i] 插入到有序序列 L[1..i-1] 中，使 L[1..i] 有序。重复 n-1 次。

 void InsertSort(ElemType A[], int n){
     int i, j;
     for(i = 2; i <= n; i++){
         if(A[i] < A[i-1]){
             A[0] = A[i];
             for(j = i-1; A[j] > A[0]; --j)
                 A[j+1] = A[j];
             A[j+1] = A[0];
         }
     }
 }

折半插入排序：将查找插入位置改为折半查找，减少比较次数，但移动次数不变。

算法分析：

• 时间复杂度：最坏 O(n²)，最好 O(n)
• 空间复杂度：O(1)
• 稳定性：稳定

---

4. 希尔排序

基本思想： 通过逐步缩小增量，对相隔一定距离的元素构成的子序列进行直接插入排序，使整个序列趋于有序，最后再进行一次增量为 1 的直接插入排序。

 void ShellSort(ElemType A[], int n){
     int i, j, dk;
     for(dk = n/2; dk >= 1; dk = dk/2){
         for(i = dk+1; i <= n; i++){
             if(A[i] < A[i-dk]){
                 A[0] = A[i];
                 for(j = i-dk; j > 0 && A[j] > A[0]; j -= dk)
                     A[j+dk] = A[j];
                 A[j+dk] = A[0];
             }
         }
     }
 }

算法分析：

• 时间复杂度：O(n^1.3) ~ O(n²)（取决于增量序列）
• 空间复杂度：O(1)
• 稳定性：不稳定

---

5. 归并排序

基本思想： 采用分治策略，将序列递归地分成两半，分别排序后合并两个有序子序列。

 void Merge(int A[], int L[], int R[], int l, int r){
     int i = 0, j = 0, k = 0;
     while(i < l && j < r){
         if(L[i] <= R[j]) A[k++] = L[i++];
         else A[k++] = R[j++];
     }
     while(i < l) A[k++] = L[i++];
     while(j < r) A[k++] = R[j++];
 }
 ​
 void MergeSort(int A[], int n){
     if(n < 2) return;
     int mid = n/2;
     int L[mid], R[n-mid];
     for(int i = 0; i < mid; i++) L[i] = A[i];
     for(int i = mid; i < n; i++) R[i-mid] = A[i];
     MergeSort(L, mid);
     MergeSort(R, n-mid);
     Merge(A, L, R, mid, n-mid);
 }

算法分析：

• 时间复杂度：O(n log n)
• 空间复杂度：O(n)
• 稳定性：稳定

---

6. 快速排序

基本思想： 任选一个元素为枢轴（pivot），将序列分为左右两部分，左边 ≤ 枢轴 ≤ 右边，递归排序左右。

 int Partition(int A[], int low, int high){
     int pivot = A[low];
     while(low < high){
         while(low < high && A[high] >= pivot) high--;
         A[low] = A[high];
         while(low < high && A[low] <= pivot) low++;
         A[high] = A[low];
     }
     A[low] = pivot;
     return low;
 }
 ​
 void QuickSort(int A[], int low, int high){
     if(low < high){
         int p = Partition(A, low, high);
         QuickSort(A, low, p-1);
         QuickSort(A, p+1, high);
     }
 }

算法分析：

• 时间复杂度：平均 O(n log n)，最坏 O(n²)
• 空间复杂度：O(log n)（递归栈）
• 稳定性：不稳定

---

7. 堆排序

基本思想： 利用大根堆（或小根堆）的性质：堆顶元素是最大（最小）值。每次取堆顶与末尾交换，再调整堆。

 void Heapify(int A[], int n, int i){
     int largest = i;
     int l = 2*i + 1, r = 2*i + 2;
     if(l < n && A[l] > A[largest]) largest = l;
     if(r < n && A[r] > A[largest]) largest = r;
     if(largest != i){
         int tmp = A[i]; A[i] = A[largest]; A[largest] = tmp;
         Heapify(A, n, largest);
     }
 }
 ​
 void HeapSort(int A[], int n){
     for(int i = n/2-1; i >= 0; i--) Heapify(A, n, i);
     for(int i = n-1; i > 0; i--){
         int tmp = A[0]; A[0] = A[i]; A[i] = tmp;
         Heapify(A, i, 0);
     }
 }

算法分析：

• 时间复杂度：O(n log n)
• 空间复杂度：O(1)
• 稳定性：不稳定

---

二、非比较排序

8. 计数排序

基本思想： 统计每个值出现的次数，根据计数信息将元素放到正确位置。适用于数据范围较小的整数序列。

 void CountingSort(int A[], int n, int k){
     int count[k+1], output[n];
     for(int i = 0; i <= k; i++) count[i] = 0;
     for(int i = 0; i < n; i++) count[A[i]]++;
     for(int i = 1; i <= k; i++) count[i] += count[i-1];
     for(int i = n-1; i >= 0; i--){
         output[count[A[i]]-1] = A[i];
         count[A[i]]--;
     }
     for(int i = 0; i < n; i++) A[i] = output[i];
 }

算法分析：

• 时间复杂度：O(n + k)（k 为数据范围）
• 空间复杂度：O(n + k)
• 稳定性：稳定

---

9. 桶排序

基本思想： 将数据分到有限数量的桶中，每个桶内分别排序（可用插入排序），再按桶顺序合并。

算法分析：

• 时间复杂度：平均 O(n + n²/B + B)，近似 O(n)
• 空间复杂度：O(n + B)
• 稳定性：稳定（桶内排序稳定时）

---

10. 基数排序

基本思想： 按位排序，从最低位到最高位依次进行稳定排序（通常使用计数排序作为子过程）。

int GetMax(int A[], int n){
    int mx = A[0];
    for(int i = 1; i < n; i++)
        if(A[i] > mx) mx = A[i];
    return mx;
}

void CountSortByDigit(int A[], int n, int exp){
    int output[n], count[10] = {0};
    for(int i = 0; i < n; i++) count[(A[i]/exp)%10]++;
    for(int i = 1; i < 10; i++) count[i] += count[i-1];
    for(int i = n-1; i >= 0; i--){
        output[count[(A[i]/exp)%10]-1] = A[i];
        count[(A[i]/exp)%10]--;
    }
    for(int i = 0; i < n; i++) A[i] = output[i];
}

void RadixSort(int A[], int n){
    int m = GetMax(A, n);
    for(int exp = 1; m/exp > 0; exp *= 10)
        CountSortByDigit(A, n, exp);
}

算法分析：

• 时间复杂度：O(d × (n + k))（d 为位数，k 为基数）
• 空间复杂度：O(n + k)
• 稳定性：稳定

---

三、总结对照表

算法	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性
冒泡排序	O(n²)	O(n²)	O(1)	✅
选择排序	O(n²)	O(n²)	O(1)	❌
插入排序	O(n²)	O(n²)	O(1)	✅
希尔排序	O(n^1.3)	O(n²)	O(1)	❌
归并排序	O(n log n)	O(n log n)	O(n)	✅
快速排序	O(n log n)	O(n²)	O(log n)	❌
堆排序	O(n log n)	O(n log n)	O(1)	❌
计数排序	O(n + k)	O(n + k)	O(n + k)	✅
桶排序	O(n)	O(n²)	O(n + B)	✅
基数排序	O(d×(n+k))	O(d×(n+k))	O(n + k)	✅