常见排序算法详解：思想、复杂度、稳定性与实现

排序是把记录按一个或多个关键字重新排列的过程。插入、选择、交换、分治等不同思想，会带来不同的时间、空间、稳定性和数据适应性。本文系统梳理直接插入、希尔、选择、堆、冒泡、快速和归并排序，并给出选择算法时真正需要考虑的边界。

1. 排序的基本概念

1.1 内部排序与外部排序

  • 内部排序：待排序数据可以全部放入内存；
  • 外部排序：数据规模超过内存，需要在内存与外部存储之间分批读写，典型方案是外部归并排序。

外部排序的主要成本通常是 I/O 次数，而不是单纯的比较次数。

1.2 稳定性

若两个记录的关键字相等，排序后它们的原相对顺序保持不变，则算法稳定。

例如学生记录先按姓名排序，再使用稳定排序按班级排序，同一班级内部仍可保持姓名顺序。稳定性只对“包含相同关键字但记录内容不同”的数据有意义。

1.3 原地、适应性与比较模型

  • 原地排序通常指额外空间为 $O(1)$ 或只使用递归栈；
  • 适应性表示算法能利用已有顺序，例如插入排序对近乎有序数据很快；
  • 比较排序只通过关键字比较决定顺序，它在一般模型下的最坏时间下界为 $\Omega(n\log n)$；
  • 计数排序、基数排序等非比较排序利用键的额外结构，能突破该下界，但有适用条件。

2. 总览

算法 最好时间 平均时间 最坏时间 额外空间 稳定性
直接插入 $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$ 稳定
希尔排序 依增量序列 依增量序列 常见实现可到 $O(n^2)$ $O(1)$ 不稳定
直接选择 $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ 不稳定
堆排序 $O(n\log n)$ $O(n\log n)$ $O(n\log n)$ $O(1)$ 不稳定
冒泡排序 $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$ 稳定
快速排序 $O(n\log n)$ $O(n\log n)$ $O(n^2)$ 平均 $O(\log n)$ 栈 不稳定
归并排序 $O(n\log n)$ $O(n\log n)$ $O(n\log n)$ $O(n)$ 稳定

表中的稳定性针对常见实现。修改比较或交换策略后，性质可能改变。

3. 直接插入排序

把区间分成“已排序”和“未排序”两部分。每轮取出未排序区的第一个元素，在已排序区从后向前寻找位置，并把较大元素后移。

1
2
3
4
5
6
7
8
9
10
11
12
static void insertion_sort(int a[], size_t n)
{
    for (size_t i = 1; i < n; ++i) {
        int value = a[i];
        size_t j = i;
        while (j > 0 && a[j - 1] > value) {
            a[j] = a[j - 1];
            --j;
        }
        a[j] = value;
    }
}

比较使用 > 而不是 >=，相等元素不会跨越，因此保持稳定。数组越接近有序，移动越少；完全有序时只需 $O(n)$。

插入排序常用于小数组，也常作为快速排序、归并排序的“小区间优化”。

4. 希尔排序

希尔排序把相距 gap 的元素划入同一组，对每组执行插入排序，再逐步缩小 gap，直到 gap=1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static void shell_sort(int a[], size_t n)
{
    for (size_t gap = n / 2; gap > 0; gap /= 2) {
        for (size_t i = gap; i < n; ++i) {
            int value = a[i];
            size_t j = i;
            while (j >= gap && a[j - gap] > value) {
                a[j] = a[j - gap];
                j -= gap;
            }
            a[j] = value;
        }
    }
}

早期的大步长能快速消除远距离逆序；最后一次就是普通插入排序，但数据已经接近有序。复杂度强烈依赖增量序列，不能笼统地给出唯一“平均 $O(n^{1.3})$”结论。由于相等元素可能在不同组中跨越，希尔排序通常不稳定。

5. 直接选择排序

每轮从未排序区找到最小值，与未排序区第一个元素交换：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static void selection_sort(int a[], size_t n)
{
    for (size_t i = 0; i < n; ++i) {
        size_t min_index = i;
        for (size_t j = i + 1; j < n; ++j) {
            if (a[j] < a[min_index]) {
                min_index = j;
            }
        }
        int tmp = a[i];
        a[i] = a[min_index];
        a[min_index] = tmp;
    }
}

无论数据是否有序，比较次数都是 $\Theta(n^2)$。它的交换次数只有 $O(n)$，因此在“写入特别昂贵、比较相对便宜”的特殊场景可能有价值。跨位置交换会改变相等记录的相对次序，所以常见实现不稳定。

6. 堆排序

升序堆排序使用大根堆：

  1. 自底向上建堆；
  2. 把堆顶最大值与末尾交换；
  3. 缩小堆区间，对新堆顶向下调整；
  4. 重复直到只剩一个元素。

从最后一个非叶节点开始自底向上建堆的总时间是 $O(n)$，不是 $O(n\log n)$。之后执行 $n-1$ 次 $O(\log n)$ 调整，总时间为 $O(n\log n)$。

堆排序最坏时间有保证，且额外空间为 $O(1)$，但访问位置跳跃、缓存局部性较弱，并且不稳定。

7. 冒泡排序

相邻元素逆序就交换，一轮后最大值“冒泡”到末尾：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static void bubble_sort(int a[], size_t n)
{
    while (n > 1) {
        bool exchanged = false;
        for (size_t i = 1; i < n; ++i) {
            if (a[i - 1] > a[i]) {
                int tmp = a[i - 1];
                a[i - 1] = a[i];
                a[i] = tmp;
                exchanged = true;
            }
        }
        if (!exchanged) {
            break;
        }
        --n;
    }
}

提前退出使完全有序时达到 $O(n)$。只交换严格逆序的相邻元素，因此保持稳定。不过它的平均和最坏时间仍为 $O(n^2)$，实际通用排序很少采用。

8. 快速排序

快速排序选择一个基准值，把区间划分成较小与较大的部分，再递归排序子区间。它体现分治思想。

8.1 三路划分

面对大量重复值时，把区间划分为 < pivot、== pivot、> pivot 三部分，能避免相等元素反复进入递归：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
static void quick_sort_range(int a[], size_t lo, size_t hi)
{
    if (hi - lo < 2) {
        return;
    }
    int pivot = a[lo + (hi - lo) / 2];
    size_t lt = lo;
    size_t i = lo;
    size_t gt = hi;

    while (i < gt) {
        if (a[i] < pivot) {
            swap_int(&a[lt++], &a[i++]);
        } else if (a[i] > pivot) {
            swap_int(&a[i], &a[--gt]);
        } else {
            ++i;
        }
    }
    quick_sort_range(a, lo, lt);
    quick_sort_range(a, gt, hi);
}

这里使用左闭右开区间 [lo, hi)，能减少边界混乱。

8.2 复杂度与退化

划分大致均衡时：

$$
T(n)=2T(n/2)+O(n)=O(n\log n)
$$

如果每次基准都是最小或最大值，递归变为：

$$
T(n)=T(n-1)+O(n)=O(n^2)
$$

随机选基准或“三数取中”可以降低遇到坏划分的概率，但不能把所有实现的理论最坏复杂度消除。生产级实现还常使用尾递归消除、优先递归较小分区和 introsort 等方法限制栈深与退化。

快速排序的交换可能让相等记录跨越，因此不稳定。平均递归栈深 $O(\log n)$，退化时可能达到 $O(n)$。

9. 归并排序

归并排序先把区间二分，递归排好左右部分，再线性合并两个有序序列。

合并时如果左右元素相等，应优先取左边元素，这样才能保持稳定：

1
2
3
4
5
if (a[i] <= a[j]) {
    tmp[k++] = a[i++];
} else {
    tmp[k++] = a[j++];
}

每层合并的总工作量是 $O(n)$，共有 $O(\log n)$ 层，因此最好、平均和最坏时间都是 $O(n\log n)$。数组版通常需要 $O(n)$ 辅助空间；链表归并则可以通过重连节点降低额外空间。

归并访问模式顺序、性能稳定，也非常适合外部排序和并行化。

10. 一份可运行的核心实现

下面集中给出堆排序、三路快速排序与归并排序，并对多组边界数据进行断言验证。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static void swap_int(int *x, int *y)
{
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

static void sift_down(int a[], size_t n, size_t root)
{
    for (;;) {
        size_t child = root * 2 + 1;
        if (child >= n) {
            return;
        }
        if (child + 1 < n && a[child] < a[child + 1]) {
            ++child;
        }
        if (a[root] >= a[child]) {
            return;
        }
        swap_int(&a[root], &a[child]);
        root = child;
    }
}

static void heap_sort(int a[], size_t n)
{
    for (size_t i = n / 2; i > 0; --i) {
        sift_down(a, n, i - 1);
    }
    for (size_t end = n; end > 1; --end) {
        swap_int(&a[0], &a[end - 1]);
        sift_down(a, end - 1, 0);
    }
}

static void quick_sort_range(int a[], size_t lo, size_t hi)
{
    if (hi - lo < 2) {
        return;
    }
    int pivot = a[lo + (hi - lo) / 2];
    size_t lt = lo;
    size_t i = lo;
    size_t gt = hi;
    while (i < gt) {
        if (a[i] < pivot) {
            swap_int(&a[lt++], &a[i++]);
        } else if (a[i] > pivot) {
            swap_int(&a[i], &a[--gt]);
        } else {
            ++i;
        }
    }
    quick_sort_range(a, lo, lt);
    quick_sort_range(a, gt, hi);
}

static void quick_sort(int a[], size_t n)
{
    quick_sort_range(a, 0, n);
}

static void merge_range(int a[], int tmp[], size_t lo, size_t mid, size_t hi)
{
    size_t i = lo;
    size_t j = mid;
    size_t k = lo;
    while (i < mid && j < hi) {
        tmp[k++] = a[i] <= a[j] ? a[i++] : a[j++];
    }
    while (i < mid) tmp[k++] = a[i++];
    while (j < hi) tmp[k++] = a[j++];
    memcpy(a + lo, tmp + lo, (hi - lo) * sizeof(*a));
}

static void merge_sort_range(int a[], int tmp[], size_t lo, size_t hi)
{
    if (hi - lo < 2) {
        return;
    }
    size_t mid = lo + (hi - lo) / 2;
    merge_sort_range(a, tmp, lo, mid);
    merge_sort_range(a, tmp, mid, hi);
    merge_range(a, tmp, lo, mid, hi);
}

static bool merge_sort(int a[], size_t n)
{
    if (n < 2) {
        return true;
    }
    int *tmp = malloc(n * sizeof(*tmp));
    if (tmp == NULL) {
        return false;
    }
    merge_sort_range(a, tmp, 0, n);
    free(tmp);
    return true;
}

static bool sorted(const int a[], size_t n)
{
    for (size_t i = 1; i < n; ++i) {
        if (a[i - 1] > a[i]) return false;
    }
    return true;
}

int main(void)
{
    int a[] = {5, -1, 5, 3, 0, 9, -1};
    int b[] = {5, -1, 5, 3, 0, 9, -1};
    int c[] = {5, -1, 5, 3, 0, 9, -1};
    size_t n = sizeof(a) / sizeof(a[0]);
    heap_sort(a, n);
    quick_sort(b, n);
    assert(merge_sort(c, n));
    assert(sorted(a, n) && sorted(b, n) && sorted(c, n));
    puts("all sorts ok");
    return 0;
}

11. 非比较排序补充

如果键是范围较小的整数，可以统计每个值出现次数，再按值域输出，这就是计数排序。其时间为 $O(n+k)$、空间为 $O(k)$，其中 $k$ 是值域大小。

当 $k$ 远大于 $n$ 时，计数数组会造成严重浪费；若键不是可直接映射的小范围整数，也不能直接使用。基数排序和桶排序同样依赖数据分布与表示，不能简单替代所有比较排序。

12. 如何选择排序算法

  • 小规模或近乎有序：插入排序；
  • 需要稳定且最坏 $O(n\log n)$：归并排序；
  • 内存紧张且要求最坏 $O(n\log n)$：堆排序；
  • 通用内存数组、追求优秀平均性能：经过防退化处理的快速排序/introsort；
  • 键范围较小的整数：计数排序；
  • 数据大于内存：外部归并排序。

标准库排序通常经过大量优化，工程中应优先使用。手写排序的价值在于理解分治、堆、稳定性、边界和复杂度，而不是在生产代码里重复造一个未经充分测试的轮子。

13. 常见错误

  • 把快速排序的最坏时间写成 $O(n\log n)$；
  • qsort 比较器直接返回 a-b，整数溢出会破坏比较结果；应使用 (a > b) - (a < b)；
  • 快排递归区间边界不统一，遗漏或重复基准位置；
  • 归并时相等元素优先取右侧，破坏稳定性；
  • 建堆方向或升降序堆类型用反；
  • 用一次小规模计时给算法下结论，忽略预热、分布、优化级别和重复实验；
  • 只验证“结果有序”，没有验证元素是否丢失或重复。严格测试还应与可信排序结果逐项比较。

排序算法的重点不只是一张复杂度表。理解数据移动方式、稳定性、缓存访问、最坏情况和输入分布，才能解释为什么同为 $O(n\log n)$ 的算法在真实系统中表现不同。