Lecture 7: 排序算法：选择、插入、归并与快速排序（Sorting: Selection, Insertion, Merge & Quicksort）（对应课程真实讲座 L13）

目录 · ← l6 · l8 →

Lecture 7: 排序算法：选择、插入、归并与快速排序（Sorting: Selection, Insertion, Merge & Quicksort）（对应课程真实讲座 L13）

概述

本讲系统学习四类排序算法：先讲两个 O(n²) 的朴素算法——选择排序与插入排序，通过它们体会”比较多 vs 交换多”的工程权衡；再讲分治思想的代表归并排序 O(n log n)，最后简介快速排序。排序是无数上层算法（二分查找、去重、中位数、统计）的基石，官方称其在计算机科学中应用极广；学会从”最好/平均/最坏 + 空间”四个维度比较算法，是本讲真正的目的。 （对应官方 2026 夏季 CS106B：L13 Tuesday, July 14 “Sorting Algorithms”。官方配套发布了 sorting-stuff.zip 幻灯片与代码，并附有选择/插入/归并在不同规模随机向量上的实测耗时对比。）

核心概念与算法原理

先约定：本课程说”已排序（sorted）”默认指非降序（从小到大，允许相等），这比”严格递增”更精确（官方第 9 讲的定义）。下面所有算法都在原容器内就地排序，只依赖元素间的 < 比较，属于比较排序。

1. 选择排序（selection sort）——”多看少动”的等待型算法

• 问题定义：把数组从小到大排好序。
• 直观解释：像每次从一堆牌里挑出最小的一张放到最前面，再在剩下的牌里挑最小的放第二位……直到挑完。每轮只做一次交换，但为了确定”谁最小”要比较很多次——官方戏称它是”wait and see”算法，花大量时间比较，才决定把哪个元素换到目标位。
• 步骤分解：
  1. 维护前缀 [0, start) 已排好，start 从 0 开始；
  2. 在 [start, n) 里线性扫描找出最小值下标 minIdx（第一轮 n 次比较，第二轮 n−1 次……）；
  3. 把 v[start] 与 v[minIdx] 交换（每轮至多 1 次）；
  4. start++，重复直到只剩一个元素。
• 逐轮走查（竖线左边是已排序前缀）：

数组 [3 1 4 2]
第1轮 start=0：扫 [3 1 4 2] 最小=1 → 交换 → [1 | 3 4 2]
第2轮 start=1：扫 [3 4 2]  最小=2 → 交换 → [1 2 | 4 3]
第3轮 start=2：扫 [4 3]    最小=3 → 交换 → [1 2 3 | 4]
第4轮 只剩 4，结束。比较总次数 = 3+2+1 = n(n-1)/2，即 O(n²)

2. 插入排序（insertion sort）——”边走边停”的理牌算法

• 直观解释：像打扑克理牌：左手牌已排好，右手每次摸一张新牌，把它往左拖，一路与左边的牌比较，直到遇到比它小的牌就停，落位。官方戏称它是 “let’s gooooo!” 算法——每经过一个位置就交换/挪动一次，但一旦遇到更小的牌立即停止，因此比较次数可能远少于选择排序。
• 步骤分解：
  1. 前缀 [0, start) 已有序，start 从 1 开始；
  2. 取 key = v[start]（新摸的”牌”），在已排序前缀里从右向左把比 key 大的元素逐个右移一格（腾出空位）；
  3. 遇到 ≤ key 的元素或到达开头，把 key 填入空位；
  4. start++ 重复。
• 逐轮走查：

数组 [3 1 4 2]
第1轮 取1：3>1 → 3右移 [3 3 4 2]，1落位 → [1 3 4 2]
第2轮 取4：3<4 立即停，原位不动      → [1 3 4 2]
第3轮 取2：4>2右移、3>2右移、1<2停   → [1 2 3 4]
对“已有序输入”，每轮只比 1 次就停 → 总比较 n-1 次，O(n)！

3. 比较多 vs 交换多：工程权衡（官方第 13 讲重点） 选择排序比较多、交换少（O(n²) 次比较但最多 n−1 次交换）；插入排序交换/挪动可能多、比较可以少（遇到小牌提前停）。官方给的场景化例子很形象：

选择/插入的其他取舍：插入排序对”几乎有序”数据表现惊艳（官方建议：若应用里输入经常接近有序，选插入排序吃它的最好情形 O(n)）；而排序算法越简单越容易写对、容易调试——快速原型 vs 极致性能之间永远要权衡。

4. 归并排序（merge sort）——”先分后合”的分治算法

• 问题定义与思路：把数组从中间一分为二，递归把两半各自排好，再写一个”合并（merge）”过程把两个有序子数组合成一个有序数组。官方概括为”易分难合（easy split, hard join）“：拆是两行递归的事，难点全在合并。
• 步骤分解：
  1. 基准：区间只剩 0 或 1 个元素，天然有序，直接返回；
  2. 分：mid = lo + (hi - lo) / 2（防溢出公式，官方再次强调 (lo+hi)/2 会溢出），递归排 [lo, mid] 与 [mid+1, hi]；
  3. 合：用两个指针 i、j 分别指向左右两半开头，每次把较小者放入辅助数组 aux；某半耗尽后把另半剩余整体倒入；最后把 aux 拷回原区间。
• 递归树与复杂度图解（每层总工作量 O(n)，共约 log₂n 层）：

               [38 27 43 3 9 82 10]
              /                     \
      [38 27 43 3]              [9 82 10]
       /        \                /      \
   [38 27]    [43 3]         [9 82]    [10]
   /    \     /    \         /    \
 [38]  [27] [43]  [3]      [9]  [82]      ← 拆到单元素（分）
      ↑ 每层“合”的工作量加起来都是 O(n)，层数 O(log n) → 总 O(n log n)
   [27 38]  [3 43]        [9 82]    [10]
      \        /            \        /
   [3 27 38 43]            [9 10 82]
          \                    /
      [3 9 10 27 38 43 82]            ← 最终有序（合）

• 合并过程示例（左右各一指针，比较后取小者放入辅助区）：

左半 [3 27 38 43]   右半 [9 10 82]
i→3  vs  9 → 取3            aux: [3]
i→27 vs  9 → 取9            aux: [3 9]
i→27 vs 10 → 取10           aux: [3 9 10]
i→27 vs 82 → 取27           aux: [3 9 10 27]
……直至右半耗尽，左半剩余 [38 43] 整体倒入 → aux: [3 9 10 27 38 43 82]

• 缺点（官方明说）：① 合并需要 O(n) 辅助空间，内存吃紧时不合适；② 递归调用有压栈开销，对很小的数组（如 ≤100 个元素）选择/插入反而更快——官方实测：n=10 时三者都在毫秒级且插排略胜；n=100 时归并才开始反超；n=50,000 时差距拉大到 2.4 秒（选择）vs 1.4 秒（插入）vs 约 7 毫秒（归并）。

5. 快速排序（quicksort）——”难分易合”，实践中最快之一

• 官方把它与归并对比：归并是”易分难合”，快排是”难分易合（hard split, easy join）“——难点在 O(n) 的分区（partition），合并不需要（递归返回时数组已经就位，官方原话：join 是递归的自然结果）。
• 步骤分解：
  1. 选一个基准 pivot（示例取区间末尾元素）；
  2. 分区：一趟把数组重排为”≤ pivot 的元素都在左，pivot 居中，> pivot 都在右”，返回 pivot 最终下标 p——一趟 O(n)；
  3. 递归排序 pivot 左右两个子区间（都严格小于原区间）；
  4. 基准：区间 ≤ 1 个元素。
• 快排性质：平均 O(n log n)、最坏 O(n²)（见”最坏情形”：已有序输入 + 固定取尾做 pivot 时，每趟只切掉一个元素）；实践中因为原地交换、缓存友好，往往跑得比归并还快——这也是它名字的由来。官方说明快排会在后续作业与 CS161 中正式登场，本讲只要求理解分区思想。

代码示例与实现详解

下面 3 个示例只依赖 C++17 标准库、自包含可编译。

示例 1：选择排序与插入排序

#include <iostream>
#include <utility>      // std::swap
#include <vector>
using namespace std;

// 每轮找未排序区间的最小值，换到区间开头
void selectionSort(vector<int>& v) {
    for (int start = 0; start < (int)v.size() - 1; ++start) {
        int minIdx = start;                     // 假设当前位已是最小
        for (int j = start + 1; j < (int)v.size(); ++j) {
            if (v[j] < v[minIdx]) minIdx = j;   // 只更新下标，不急着交换
        }
        swap(v[start], v[minIdx]);              // 每轮至多一次交换
    }
}

// 每轮取未排序区第一个元素，往左拖到合适位置（比它大的整体右移）
void insertionSort(vector<int>& v) {
    for (int start = 1; start < (int)v.size(); ++start) {
        int key = v[start];                     // 新摸的“牌”
        int gap = start;                        // 空位从 start 开始向左找
        while (gap > 0 && key < v[gap - 1]) {   // 左邻更大 → 右移腾位
            v[gap] = v[gap - 1];
            --gap;
        }
        v[gap] = key;                           // key 落位
    }
}

void show(const vector<int>& v) {
    for (int x : v) cout << x << ' ';
    cout << endl;
}

int main() {
    vector<int> a = {3, 1, 4, 2};
    vector<int> b = a;
    selectionSort(a);   cout << "选择排序: "; show(a);
    insertionSort(b);   cout << "插入排序: "; show(b);
    return 0;
}

【代码做什么】：两个排序函数各就各位地对同一个输入演示。selectionSort 双层循环：外层固定”待安放位置”，内层找最小、外层结束后才交换一次；insertionSort 把新元素存进 key，用 gap 指针把比它大的元素一个个右移，最后把 key 写回空位（这就是”拖拽”的实现，官方代码里管这张牌叫 peach）。

【实现机制解说】：选择排序的交换必须放在内层循环之外——内层只是不断刷新 minIdx，找到最终目标才动手，否则每发现一个更小值就换一次，交换次数会从 O(n) 退化到 O(n²)（这正是”比较多 vs 交换多”取舍的代码体现）。插入排序的移动是整体平移而非两两交换：v[gap] = v[gap-1] 把大牌往右推一格，key 始终攥在手里，最后一次性落位，一趟的写次数等于”它左边比它大的元素个数”；而 while 的提前退出条件 key < v[gap-1] 一旦不成立（左邻 ≤ key）立即停止——对已排序输入，每轮只比较 1 次，整趟 O(n)，这就是插入排序最好情形的来源。两函数都就地修改、空间 O(1)。

示例 2：归并排序（递归 + 辅助 vector 归并）

#include <iostream>
#include <vector>
using namespace std;

// 归并排序 v[lo..hi]（闭区间）
void mergeSort(vector<int>& v, int lo, int hi) {
    if (lo >= hi) return;                   // 基准：0 或 1 个元素，天然有序
    int mid = lo + (hi - lo) / 2;           // 防溢出中点（勿写 (lo+hi)/2）
    mergeSort(v, lo, mid);                  // 分：左半
    mergeSort(v, mid + 1, hi);              // 分：右半
    // 合：双指针归并两个有序子数组
    vector<int> aux;                        // O(n) 辅助空间（本算法最大“缺点”）
    int i = lo, j = mid + 1;
    while (i <= mid && j <= hi)             // 两边都还有货：取较小者
        aux.push_back(v[i] <= v[j] ? v[i++] : v[j++]);
    while (i <= mid) aux.push_back(v[i++]); // 左半剩余整体倒入
    while (j <= hi)  aux.push_back(v[j++]); // 右半剩余整体倒入
    for (int k = 0; k < (int)aux.size(); ++k)   // 拷回原区间
        v[lo + k] = aux[k];
}

void mergeSort(vector<int>& v) {            // 包装函数（重载）
    if (!v.empty()) mergeSort(v, 0, (int)v.size() - 1);
}

int main() {
    vector<int> v = {38, 27, 43, 3, 9, 82, 10};
    mergeSort(v);
    for (int x : v) cout << x << ' ';
    cout << endl;                           // 3 9 10 27 38 43 82
    return 0;
}

【代码做什么】：mergeSort(v, lo, hi) 先递归排左右两半，再用辅助 vector aux 完成”合”：两个游标 i、j 分别走在左右半，谁小谁进 aux；某半耗尽就整体倒入另一半剩余；最后把 aux 的 lo..hi 段拷回原位。包装函数负责对外只暴露 mergeSort(v) 一个参数。

【实现机制解说】：结合第 4 节的递归树理解执行流：mergeSort(v,0,6) 先递归到最深——[38]、[27] 等单元素区间逐一返回（基准 lo >= hi），然后归途上自底向上合并：[27 38]、[3 43]、[9 82]，再合并成 [3 27 38 43] 与 [9 10 82]，最后合成整段有序——合并总是发生在左右都已有序之后，所以双指针比较取小必然正确。归并用 <= 取左半元素，相等元素保持左先右后的相对顺序，因此归并是稳定的。三个 while 一个都不能少：主循环结束后必有一半先耗尽，剩余元素必须整体续尾，否则会丢元素。中点公式在此与二分查找同样防溢出。空间上每层合成都新建一个 aux，栈深度 O(log n) 层，同层最多共存约 n 大小的辅助区，故总辅助空间 O(n)。

示例 3：快速排序（完整小实现，Lomuto 分区）

#include <iostream>
#include <utility>      // std::swap
#include <vector>
using namespace std;

// 一趟分区：以末尾元素为 pivot，返回 pivot 最终位置；
// 结束后 pivot 左侧都 ≤ pivot，右侧都 > pivot
int partition(vector<int>& v, int lo, int hi) {
    int pivot = v[hi];
    int i = lo;                             // i 左边都是已确认 ≤ pivot 的
    for (int j = lo; j < hi; ++j) {
        if (v[j] < pivot) {                 // 发现该去左边的元素
            swap(v[i], v[j]);               // 换到“小元素区”末尾
            ++i;
        }
    }
    swap(v[i], v[hi]);                      // pivot 归位
    return i;
}

void quickSort(vector<int>& v, int lo, int hi) {
    if (lo >= hi) return;                   // 基准：0/1 个元素
    int p = partition(v, lo, hi);           // “难”的一步：O(n) 分区
    quickSort(v, lo, p - 1);                // 左边递归（比 pivot 小的）
    quickSort(v, p + 1, hi);                // 右边递归（比 pivot 大的）
}

void quickSort(vector<int>& v) {
    if (!v.empty()) quickSort(v, 0, (int)v.size() - 1);
}

int main() {
    vector<int> v = {7, 2, 9, 3, 6, 1, 8, 5, 4};
    quickSort(v);
    for (int x : v) cout << x << ' ';
    cout << endl;                           // 1 2 3 4 5 6 7 8 9
    return 0;
}

【代码做什么】：partition 选末元素为 pivot，用快慢两个下标 i、j 扫一遍：j 负责考察每个元素，凡小于 pivot 的都与 i 所指位置交换，使 i 左侧始终是”已确认 ≤ pivot”的区域；扫描结束把 pivot 换到 i 处并返回 i。quickSort 递归排 pivot 左右两侧。主函数对 9 个乱序整数排序验证。

【实现机制解说】：体会”难分易合”：partition 一趟 O(n) 完成重排后，pivot 已在其最终位置，左右两侧只需各自递归——没有合并步骤，因为”合”被分区天然完成了。为什么平均 O(n log n) 而最坏 O(n²)？若 pivot 每次都能把区间切成大致两半，递归树与归并一样深 O(log n)、每层 O(n)，总计 O(n log n)；但若输入已有序且 pivot 固定取末尾，每趟分区只把 pivot 挪走一个位置（一侧为空），递归树退化成一条长链，深度 O(n) → 总 O(n²)。实践中快排快的原因：完全原地（无辅助数组）、缓存局部性好；工程上还会用”随机选 pivot 或三数取中”来避免有序输入触发最坏情形。注意本实现用 < 而非 <= 比较，重复元素会偏向 pivot 右侧，功能正确但可进一步优化。

复杂度分析

官方实测参考（随机向量多次取平均）：n=10 时三者耗时都在 1 ms 上下（插排 0.000793 ms 甚至略快于归并 0.001027 ms）；n=1,000 时归并（约 0.10 ms）反超插排（0.56 ms）；n=50,000 时选择约 2.43 s、插入约 1.38 s、归并约 7.4 ms——印证两点：递归/辅助开销让小 n 时简单算法更优，而 n 一大 O(n log n) 对 O(n²) 就是数量级碾压。稳定性上：插入、归并（用 <= 取左）稳定；选择、快排的常见就地实现不稳定——若”相等元素保持原相对次序”重要，选稳定算法。

关键要点

• 选择排序”多看少动”：O(n²) 次比较但只有 O(n) 次交换；每轮只交换一次（交换放内层循环外）。
• 插入排序”边走边停”：遇到不比它大的牌立即停，因此几乎有序的输入接近 O(n)——判断数据形态后优先考虑它。
• 归并排序”先分后合”：O(n log n) 最坏也稳，代价是 O(n) 辅助空间与小数组时的递归开销——空间紧张或 n 很小就别用它。
• 快排”难分易合”：分区一趟 O(n)，平均 O(n log n)、原地且缓存友好；pivot 选得差（有序输入）会退化 O(n²)。
• 没有”万能最好”的排序：选算法先问四个问题——输入规模多大？是否接近有序？比较/交换谁更贵？内存够不够？

常见陷阱与注意事项

1. 选择排序把交换写进内层循环：每发现更小值就交换一次，交换次数退化为 O(n²)，丢掉”少交换”的优点。规避：内层只更新 minIdx，内层结束后交换一次。
2. 插入排序的循环边界写错：写成 gap >= 0 && key < v[gap] 会越界或漏比较。规避：用”空位在 gap、比较左邻 v[gap-1]”的写法：while (gap > 0 && key < v[gap-1])，落位写 v[gap] = key。
3. 归并基准写成 lo > hi（或忘处理 lo==hi）：单元素区间还会继续分裂，陷入不必要的递归甚至死循环。规避：基准用 lo >= hi。
4. 合并的三个 while 少写一个：主循环结束后必有一半还有剩余，不续尾就丢元素。规避：两个”整体倒入剩余”的 while 一个都不能删。
5. 中点公式 (lo+hi)/2 溢出：与二分查找同款陷阱（官方第 13 讲再次强调）。规避：lo + (hi-lo)/2。
6. 忘记把辅助数组拷回原数组：排完序却仍是无序原数组。规避：合并收尾用 v[lo+k] = aux[k] 回写。
7. 快排的有序输入最坏情形：固定取尾做 pivot + 输入已有序 → O(n²) 且可能栈深爆掉。规避：随机选 pivot、三数取中，或对小分区切换插入排序。
8. 混淆”比较次数”与”运行时间”：复杂度分析针对的是比较/交换这些基本操作的数量级，别用墙钟秒数直接下结论（机器、输入分布都影响实测）。

思考题（带答案）

问题 1：给你一个”基本有序”的 10 万元素数组（只有少量位置错乱），你会选插入排序还是归并排序？两者复杂度分别如何？ 答案：优先插入排序。它的最好情形 O(n) 恰好在”近乎有序”时出现：每个元素往左拖不了几步就停，总比较接近 O(n)；归并虽然最坏保证 O(n log n)，但对这种输入没有利用有序性的优势，还要付出 O(n) 辅助空间。这正体现”选算法要看输入形态”（官方讨论过：若应用里常见某种触发最好情形的输入，就该选那个算法）；工程上也常用”归并/快排 + 小分区切插入排序”的混合策略。 问题 2：归并排序的 O(n) 辅助空间具体花在哪？能否完全省掉？ 答案：花在”合”：每一层合并都要一个能容纳整个待合并区间的辅助数组 aux（两个有序子数组无法在不覆盖对方的情况下原地两两归并）。递归栈本身只占 O(log n)。完全原地归并在理论上可行但实现复杂、常数巨大，实践中几乎不用——所以内存敏感场景往往选择原地排序（如快排、堆排序，后者会在后续章节出现）。 问题 3：什么输入会让示例 3 的快排退化到 O(n²)？怎样缓解？ 答案：输入已经有序（升序或降序）且 pivot 固定取末尾时，每趟分区只会把 pivot 移到一端，另一侧为空，递归深度变成 n，总时间 O(n²)。缓解手段：①随机选 pivot（把最坏输入变成概率极低事件）；②三数取中（取 lo、mid、hi 三者的中位数做 pivot）；③遇到小区间切换插入排序并限制递归深度。