四种排序:插入、计数、归并、快速
这一讲只讲四种最常用、最有代表性的排序: 插入排序、计数排序、归并排序、快速排序。 先看每种排序“手工怎么做”,再看复杂度、稳定性和代码; 最后用一张表把常见排序放在一起比较。
11.1 先约定三件事
稳定性:两个关键字相等的记录,排序前后的相对次序不变,叫稳定。 需要保留原始顺序时很重要:先按姓名排好,再按成绩做稳定排序,同分时姓名顺序才不会乱。
原地排序:不额外开辟与 n 同阶的数组;
快排的递归栈是 O(log n),通常单独说明。
归并排序需要 O(n) 的临时数组,所以不是原地排序。
比较排序与非比较排序:插入、归并、快速都靠比较关键字; 计数排序不比较,而是直接统计每个值出现几次。
11.2 插入排序
11.2.1 直觉:像摸扑克牌
把数组分成“左边已排好”和“右边待处理”两部分。
每次取右边第一个元素 key,在左边从后往前找位置:
比 key 大的元素统统右移一格,最后把 key 放进空位。
例:[5, 2, 9, 1, 7]
处理 2:5 右移,变成 [2, 5, 9, 1, 7];
处理 9:不动;
处理 1:2、5、9 都右移,变成 [1, 2, 5, 9, 7];
处理 7:9 右移,变成 [1, 2, 5, 7, 9]。
11.2.2 跟着动画走
key,虚线框是元素搬走后留下的“坑”;
每右移一次,坑往左挪一格,直到 key 落坑。
11.2.3 代码与复杂度
#include <vector>
using namespace std;
// 直接插入排序(升序,0 基下标)
void insertionSort(vector<int>& a) {
int n = (int)a.size();
for (int i = 1; i < n; ++i) {
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key) { // 严格大于才右移,保证稳定
a[j + 1] = a[j];
--j;
}
a[j + 1] = key; // 放进空位
}
}
最坏和平均是 O(n²);数据已经基本有序时接近 O(n)。
空间 O(1),稳定:内层用 a[j] > key,相等时停下,不跨过相等元素。
11.3 计数排序
11.3.1 适用条件:关键字是小范围整数
计数排序不比较元素大小,而是统计每个值出现了几次。 它要求关键字是范围不大的整数(或能映射成小范围整数)。 如果最大值和最小值相差很大,桶数组会非常浪费。
11.3.2 三步与一个例子
以 [4, 2, 2, 8, 3, 3, 1] 为例:
- 统计:1 出现 1 次、2 出现 2 次、3 出现 2 次、4 出现 1 次、8 出现 1 次;
- 前缀和:算出每个值在结果数组中的“最后一个位置”;
- 从后往前放:把原数组元素依次放进对应位置。倒着放是为了让相等元素保持原次序,保证稳定。
结果是 [1, 2, 2, 3, 3, 4, 8]。
11.3.3 代码与复杂度
#include <vector>
#include <algorithm>
using namespace std;
// 计数排序(升序):关键字必须是范围不大的整数
void countingSort(vector<int>& a) {
if (a.empty()) return;
int mn = *min_element(a.begin(), a.end());
int mx = *max_element(a.begin(), a.end());
int k = mx - mn + 1; // 值域大小
vector<int> cnt(k, 0);
for (int x : a) ++cnt[x - mn]; // 1. 统计频率
for (int i = 1; i < k; ++i)
cnt[i] += cnt[i - 1]; // 2. 前缀和:最后一个位置
vector<int> out(a.size());
for (int i = (int)a.size() - 1; i >= 0; --i) {
int v = a[i] - mn;
out[--cnt[v]] = a[i]; // 3. 倒序填充,保证稳定
}
a.swap(out);
}
设值域大小为 k = max − min + 1:
时间 O(n + k),空间 O(n + k)。
当 k 与 n 同阶时是线性的;k 很大时会浪费空间。
按上面的倒序填充,计数排序是稳定的。
11.4 归并排序
11.4.1 直觉:先分开,再合并
归并排序是标准的分治: 分:把区间从中间切成两半; 治:递归排好左右两半; 合:把两个已经有序的段合并成一个有序段。
合并用双指针:i 指左段、j 指右段,谁小取谁;
一侧取完后,另一侧整段抄过去。相等时取左段,所以归并排序稳定。
11.4.2 跟着动画走
11.4.3 代码与复杂度
#include <vector>
#include <algorithm>
using namespace std;
// 归并排序(升序,0 基下标):排序 a[l..r]
void mergeSort(vector<int>& a, int l, int r) {
if (l >= r) return; // 0 或 1 个元素
int mid = l + (r - l) / 2;
mergeSort(a, l, mid); // 排左半
mergeSort(a, mid + 1, r); // 排右半
vector<int> tmp; // 暂存合并结果
int i = l, j = mid + 1;
while (i <= mid && j <= r) {
if (a[i] <= a[j]) tmp.push_back(a[i++]); // 相等取左,保证稳定
else tmp.push_back(a[j++]);
}
while (i <= mid) tmp.push_back(a[i++]); // 左段剩余
while (j <= r) tmp.push_back(a[j++]); // 右段剩余
copy(tmp.begin(), tmp.end(), a.begin() + l); // 写回原数组
}
最好、平均、最坏都是 O(n log n);
合并需要临时数组,空间 O(n),不是原地排序。
稳定:合并时写 a[i] <= a[j] 取左段,相等元素不会跨过去。
11.5 快速排序
11.5.1 直觉:选基准,把区间分开
选一个基准 pivot,做一次划分:
比它小的放左边,比它大的放右边,基准落到最终位置;
然后递归处理左右两半。
快排和归并都是分治,但顺序相反: 归并是“先递归排好,再合并”;快排是“先划分,再递归”。
11.5.2 跟着动画走
i、橙色 j 是扫描指针;
每完成一次划分,基准的位置就固定了,不再参与后面的递归。
11.5.3 基准怎么选,什么时候退化
理想情况下基准接近中位数,每次把区间分成两半,递归深度 log n,
平均时间 O(n log n)。
如果每次基准都是最大或最小值,划分成“一边空、一边 n−1 个”,
递归深度退化成 n,最坏时间 O(n²)。
取首元素/尾元素最简单,但有序数据会退化; 常用随机基准或三数取中(首、中、尾取中位数)来避免。
11.5.4 代码与复杂度
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/* ============================================================
快速排序的尾递归优化(消除尾递归)
把两个递归调用中的「长的一半」改成循环,只递归「短的一半」
效果:递归深度从最坏 O(n) 降到 O(log n),杜绝栈溢出
============================================================ */
int partitionHole(vector<int>& a, int l, int r) {
int pivot = a[l], i = l, j = r; // 挖坑法
while (i < j) {
while (i < j && a[j] >= pivot) --j;
if (i < j) a[i++] = a[j];
while (i < j && a[i] <= pivot) ++i;
if (i < j) a[j--] = a[i];
}
a[i] = pivot;
return i;
}
int maxDepthPlain = 0, maxDepthTail = 0;
/* 普通双递归版:最坏情况下递归深度 = n */
void quickSortPlainD(vector<int>& a, int l, int r, int d) {
if (d > maxDepthPlain) maxDepthPlain = d;
if (l >= r) return;
int p = partitionHole(a, l, r);
quickSortPlainD(a, l, p - 1, d + 1);
quickSortPlainD(a, p + 1, r, d + 1);
}
/* 尾递归优化版:只对较短的一半递归,较长的一半用 while 循环吃掉 */
void quickSortTailD(vector<int>& a, int l, int r, int d) {
if (d > maxDepthTail) maxDepthTail = d;
while (l < r) {
int p = partitionHole(a, l, r);
if (p - l < r - p) { // 左半更短 → 递归左边,循环处理右边
quickSortTailD(a, l, p - 1, d + 1);
l = p + 1;
} else { // 右半更短 → 递归右边,循环处理左边
quickSortTailD(a, p + 1, r, d + 1);
r = p - 1;
}
}
}
static bool isSorted(const vector<int>& a) {
for (size_t i = 1; i < a.size(); ++i) if (a[i - 1] > a[i]) return false;
return true;
}
int main() {
/* 最坏情况:完全升序的数据 + 取首元素为基准 */
const int N = 1000;
vector<int> asc(N);
for (int i = 0; i < N; ++i) asc[i] = i;
vector<int> a = asc;
quickSortPlainD(a, 0, N - 1, 1);
cout << "普通双递归版:最大递归深度 = " << maxDepthPlain
<< "(n = " << N << "),有序性 " << (isSorted(a) ? "通过" : "失败") << "\n";
a = asc;
quickSortTailD(a, 0, N - 1, 1);
cout << "尾递归优化版:最大递归深度 = " << maxDepthTail
<< ",有序性 " << (isSorted(a) ? "通过" : "失败") << "\n";
cout << "\n结论:两者排序结果完全一样,但尾递归优化把栈空间从 O(n) 压到了 O(log n)。\n";
cout << "这就是为什么工程实现里绝不允许快排出现 O(n) 的递归深度。\n";
return 0;
}
平均 O(n log n),最坏 O(n²);
数组本身原地排序,递归栈平均 O(log n)。
不稳定:划分时的长距离交换可能改变相等元素的相对次序。
11.6 各种排序扩展简单对比
下面把本讲四种排序和常见的其他排序放在一起,只做选型参考,不展开细节。
| 排序 | 平均 | 最坏 | 空间 | 稳定 | 一句话特点 |
|---|---|---|---|---|---|
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 | 小数组、基本有序时很快 |
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | 稳定 | 关键字是小范围整数时是线性 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 | 稳定且最坏有保证,但要额外空间 |
| 快速排序 | O(n log n) | O(n²) | O(log n) 栈 | 不稳定 | 平均最快,原地,怕基准选坏 |
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 | 相邻交换,加标志最好 O(n) |
| 选择排序 | O(n²) | O(n²) | O(1) | 不稳定 | 交换次数少,最多 n−1 次 |
| 希尔排序 | 约 O(n^1.3) | O(n²) | O(1) | 不稳定 | 插入排序的增量加速版 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 | 原地、最坏有保证,也适合优先队列 |
| 基数排序 | O(d(n+r)) | O(d(n+r)) | O(n+r) | 稳定 | 按位分配,位数固定时接近线性 |
简单选型:小数组或基本有序用插入;小范围整数用计数; 要求稳定且能接受额外空间用归并;追求平均速度、内存紧用快排; 需要最坏有保证用堆;位数少的大整数用基数。
11.7 工程实战:std::sort 的内省排序
学完理论,最有价值的一步是看看真正被千万行代码调用的排序长什么样。 你会发现标准库的做法和教科书完全不同——它不追求某一个算法的最优, 而是追求「在所有输入上都不会太差」。
一句话本质:以快速排序为主干,用插入排序处理小区间,用堆排序兜底递归过深的情况, 三种算法各管一段,拼出「平均接近快排 + 最坏 O(n log n)」。
为什么非要这么拼?因为快排有两个天生的短板:
- 小区间效率低。当区间只剩十几个元素时,快排还要递归划分、还要选枢轴, 函数调用与划分的开销远超实际需要的比较次数。而插入排序在小规模、基本有序的数据上常数最小。 所以主流实现都设一个阈值(libstdc++ 是 16),区间长度 ≤ 阈值时直接插排返回。
- 深度会失控。如果枢轴每次都选到最值(比如对手刻意构造的输入),
划分变成 1 : n−1,递归深度退化成 O(n),时间复杂度 O(n²),甚至爆栈。内省(introspective)
的含义就是:算法自己监视递归深度,一旦超过
2⌊log₂ n⌋就判定「划分已经严重偏斜」, 立刻改用堆排序处理该区间——堆排最坏也是 O(n log n),且额外空间 O(1)。
下面这份代码是一个可以直接编译运行的 introsort 实现,把三道保险都写全了:
#include <bits/stdc++.h>
using namespace std;
/* ============================================================
自己实现 introsort(内省排序)= 快速排序 + 插入排序 + 堆排序
竞赛写法:全局数组 + 自由函数,区间统一用 [lo, hi) 左闭右开
· 主干:三数取中选枢轴的快速排序
· 小区间(len <= 16):改用插入排序收尾
· 递归深度 > 2*floor(log2(n)):改用堆排序,保证最坏 O(n log n)
平均 O(n log n),最坏 O(n log n),空间 O(log n),不稳定
数组大小依据:MAXN = 3e5 + 5,够放 3e5 个元素
============================================================ */
const int MAXN = 300005;
const int INSERTION_THRESHOLD = 16;
int a[MAXN];
int n = 0;
/* ---------- 插入排序:只处理 [lo, hi) ---------- */
void insertionSort(int lo, int hi) {
for (int i = lo + 1; i < hi; ++i) {
int key = a[i], j = i;
while (j > lo && a[j - 1] > key) { a[j] = a[j - 1]; --j; }
a[j] = key;
}
}
/* ---------- 下沉:把 a[lo .. lo+len-1] 看成堆,调整下标 root ---------- */
void siftDown(int lo, int len, int root) {
while (true) {
int child = 2 * root + 1;
if (child >= len) break;
if (child + 1 < len && a[lo + child] < a[lo + child + 1]) ++child; // 取较大的孩子
if (a[lo + root] < a[lo + child]) {
swap(a[lo + root], a[lo + child]);
root = child;
} else break;
}
}
/* ---------- 堆排序:只处理 [lo, hi),最坏也是 O(n log n) ---------- */
void heapSort(int lo, int hi) {
int len = hi - lo;
for (int i = len / 2 - 1; i >= 0; --i) siftDown(lo, len, i); // 建大顶堆
for (int end = len - 1; end > 0; --end) {
swap(a[lo], a[lo + end]); // 最大值换到末尾
siftDown(lo, end, 0); // 剩余部分重新成堆
}
}
/* ---------- 三数取中:把中位数换到倒数第二个位置并返回该下标 ---------- */
int medianOfThree(int lo, int hi) { // [lo, hi)
int mid = lo + (hi - lo) / 2;
--hi; // 指向最后一个有效元素
if (a[mid] < a[lo]) swap(a[mid], a[lo]);
if (a[hi] < a[lo]) swap(a[hi], a[lo]);
if (a[hi] < a[mid]) swap(a[hi], a[mid]);
/* 此时 a[lo] <= a[mid] <= a[hi],把 mid 换到 hi-1 当枢轴,最后一个元素 a[hi] 留作右端哨兵 */
swap(a[mid], a[hi - 1]);
return hi - 1;
}
/* ---------- 核心:带深度限制的快排 ---------- */
void introsortLoop(int lo, int hi, int depthLimit) { // [lo, hi)
while (hi - lo > INSERTION_THRESHOLD) {
if (depthLimit == 0) { heapSort(lo, hi); return; } // ① 深度用尽 → 堆排兜底
--depthLimit;
int pivot = medianOfThree(lo, hi); // ② 三数取中
int i = lo, j = hi - 1;
while (true) {
while (a[++i] < a[pivot]) {}
while (a[pivot] < a[--j]) {}
if (i < j) swap(a[i], a[j]); else break;
}
swap(a[i], a[pivot]); // 枢轴归位
introsortLoop(i + 1, hi, depthLimit); // 递归处理右半
hi = i; // 左半用循环继续处理(尾递归优化)
}
/* ③ 小区间直接退出,最后对整个区间做一次插入排序收尾 */
}
void introSort(int lo, int hi) { // [lo, hi)
if (hi - lo < 2) return;
int depthLimit = 2 * (int)log2((double)(hi - lo)); // 2 * floor(log2 n)
introsortLoop(lo, hi, depthLimit);
insertionSort(lo, hi); // 小区间收尾
}
int main() {
n = 40;
for (int i = 0; i < n; ++i) a[i] = (i * 17 + 5) % 40;
introSort(0, n);
for (int i = 0; i < n; ++i) printf("%d ", a[i]);
printf("\n");
/* 和标准库结果比对 */
int b[40];
for (int i = 0; i < n; ++i) b[i] = a[i];
sort(b, b + n);
bool same = true;
for (int i = 0; i < n; ++i) if (a[i] != b[i]) same = false;
printf("与 std::sort 结果一致:%s\n", same ? "是" : "否");
/* 已经有序的输入(快排的经典最坏场景)也不再退化 */
n = 100000;
for (int i = 0; i < n; ++i) a[i] = i;
introSort(0, n);
printf("10 万条已排序数据 introsort 完成,首尾 = %d %d\n", a[0], a[n - 1]);
return 0;
}
- 平均快来自快排:快排的常数因子最小、访问局部性最好,随机输入下是实测最快的
O(n log n)算法。 - 最坏有保证来自堆排兜底:一旦递归深度超过
2⌊log₂ n⌋, 说明划分已经严重偏斜(否则深度必然是O(log n)), 此时把该区间交给最坏O(n log n)的堆排,于是整体最坏不会超过O(n log n)。 - 常数更小来自插排收尾:小区间(≤ 16)用插排,省掉了大量递归调用与枢轴选择的固定开销。
std::sort 整体不稳定;
需要稳定时要用 std::stable_sort。