一、比较排序

1. 冒泡排序

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

1
2
3
4
5
6
7
8
9
10
11
12
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. 选择排序

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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 次。

1
2
3
4
5
6
7
8
9
10
11
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 的直接插入排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
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. 归并排序

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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），将序列分为左右两部分，左边 ≤ 枢轴 ≤ 右边，递归排序左右。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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. 堆排序

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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. 计数排序

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

1
2
3
4
5
6
7
8
9
10
11
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. 基数排序

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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) ✅
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章

快来参与讨论吧~