第 11 讲

四种排序:插入、计数、归并、快速

这一讲只讲四种最常用、最有代表性的排序: 插入排序、计数排序、归并排序、快速排序。 先看每种排序“手工怎么做”,再看复杂度、稳定性和代码; 最后用一张表把常见排序放在一起比较。

预计 80 分钟 前置:数组、循环、递归 关键词:插入 · 计数 · 分治 · 划分 · 稳定性

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 出现 1 次、2 出现 2 次、3 出现 2 次、4 出现 1 次、8 出现 1 次;
  2. 前缀和:算出每个值在结果数组中的“最后一个位置”;
  3. 从后往前放:把原数组元素依次放进对应位置。倒着放是为了让相等元素保持原次序,保证稳定。

结果是 [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)」。

为什么非要这么拼?因为快排有两个天生的短板:

内省排序(Introsort)的决策流程 sort(first, last) 深度 ≤ 2⌊log₂n⌋ 深度 > 2⌊log₂n⌋ ① 快速排序(主干) 三数取中 / median-of-3 选枢轴 + Hoare 划分 区间长度 > 阈值(通常 16)? 是 → 继续递归划分;否 → 交给插入排序 ② 插入排序(小区间收尾) 长度 ≤ 16:插排常数最小、cache 友好、天然稳定 ③ 堆排序(兜底) 对该区间建堆 + 反复取最值,最坏 O(n log n) 不递归 → 深度不再增长 从而把最坏情况的 O(n²) 彻底堵死 三者的分工 快排:平均快、 常数小、cache 好 插排:小区间最优 堆排:最坏有保证 最终的复杂度:平均 O(n log n)(接近快排常数)、最坏 O(n log n)(由堆排保证)、额外空间 O(log n)(递归栈)。
图 11-8 内省排序的决策流程图:快排主干 + 小区间插排 + 深度超限转堆排

下面这份代码是一个可以直接编译运行的 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;
}
考点:为什么 introsort 能同时保证「平均快」和「最坏 O(n log n)」 标准答题模板(三段):
  1. 平均快来自快排:快排的常数因子最小、访问局部性最好,随机输入下是实测最快的 O(n log n) 算法。
  2. 最坏有保证来自堆排兜底:一旦递归深度超过 2⌊log₂ n⌋, 说明划分已经严重偏斜(否则深度必然是 O(log n)), 此时把该区间交给最坏 O(n log n) 的堆排,于是整体最坏不会超过 O(n log n)。
  3. 常数更小来自插排收尾:小区间(≤ 16)用插排,省掉了大量递归调用与枢轴选择的固定开销。
补充一句会加分:插入排序稳定,但快排和堆排不稳定,所以组合出的 std::sort 整体不稳定; 需要稳定时要用 std::stable_sort。