建模。这是复杂度问答题，考点不是背数字，而是「平均与最坏的区分、空间与稳定性是否一并说出来、能不能解释为什么」。按「结论 → 原因 → 什么时候失效」三层组织答案。

关键步骤。归并排序：递推 \(T(n) = 2T(n/2) + \Theta(n)\)，递归树每层合并总量 \(\Theta(n)\)、共 \(\Theta(\log n)\) 层，因此最好 = 平均 = 最坏 = \(O(n \log n)\)；代价是 \(O(n)\) 辅助数组，换来的性质是稳定与纯顺序访问。快速排序：平均 \(O(n \log n)\)（随机基准下期望划分均衡），最坏 \(O(n^2)\)，触发条件是划分持续极不平衡——典型就是对已排序输入固定取端点为基准，递推退化为 \(T(n) = T(n-1) + \Theta(n)\)；它是原地的，期望递归栈 \(O(\log n)\)，但不稳定。

数值对照。对 \(n = 10^6\)：\(n \log_2 n \approx 2 \times 10^7\)，而 \(n^2 = 10^{12}\)——最坏与平均差了五个数量级，这就是随机化必须写的原因。

面试怎么讲。先各用一句话给结论，再主动补三点：快排最坏的触发与补救（随机基准、三数取中、三路划分压重复、introsort 深度超限切堆排）；归并为什么三档一致（切分与输入无关）；最后一句工程口径——「std::sort 是 introsort：快排打底、递归过深换堆排、小区间换插入排序，所以它有 \(O(n \log n)\) 的最坏保证还有接近快排的平均速度」。能把 std::sort 的实现策略讲出来，这题就从及格变成加分。

建模。两个关键字（代码为主、时间为次），但只允许排一次。如果排序算法稳定，那么「对主关键字做一次稳定排序」就自动保留按次关键字的原有次序——时间序已经排好，就是那个「原有次序」。

关键步骤。对代码列做稳定排序（归并或插入排序系）。相等代码的元素在输出中保持输入里的先后，即时间序。等价性论证：任意两条同代码记录 \(r_i\)、\(r_j\)，输入中 \(i \lt j\)（时间在前），稳定性保证输出中仍 \(i\) 在前。

数值演示。输入（已按时间排好）：

按代码稳定排序后：AAPL 09:30、AAPL 09:35、GOOG 09:36、MSFT 09:31、MSFT 09:40——每只代码内部时间序完好。若改用快排或堆排，输出可能是 AAPL 09:35、AAPL 09:30、…，时间序被打乱。

面试怎么讲。一句话点名机制：「稳定排序保证相等键的相对次序不变，所以先按次要键排好、再按主键稳定排一次，等价于按复合键排序」。再补一个反向追问的答案：如果只能用不稳定排序，就必须把两个键拼成复合比较函数（代码相等时比时间），或者排完后对同代码段再排一次时间。

思路。区间约定为左闭右开 \([l, r)\)，长度不超过 1 直接返回；否则取中点递归两侧，再双指针合并。稳定性由合并时「相等取左」这一行保证。

#include <vector>
using namespace std;

void mergeSort(vector<int>& a, int l, int r, vector<int>& tmp) {
    if (r - l <= 1) return;                 // [l, r) 长度 <= 1，天然有序
    int m = l + (r - l) / 2;
    mergeSort(a, l, m, tmp);                // 递归排左半 [l, m)
    mergeSort(a, m, r, tmp);                // 递归排右半 [m, r)
    int i = l, j = m, k = l;
    while (i < m && j < r)                 // 稳定性关键：相等时取左半
        tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
    while (i < m) tmp[k++] = a[i++];        // 左半剩余直接接上
    while (j < r) tmp[k++] = a[j++];        // 右半剩余直接接上
    for (int t = l; t < r; ++t) a[t] = tmp[t];
}

复杂度。时间 \(O(n \log n)\)（每层合并总量 \(\Theta(n)\)，\(\Theta(\log n)\) 层）；空间 \(O(n)\) 辅助数组加 \(O(\log n)\) 递归栈。

边界。空数组与单元素在第一行被 \(r - l \le 1\) 拦下；全相等数组走满递归树，仍是 \(O(n \log n)\)；负数、大数不受影响（只做比较）。追问延伸：把「取右半时」计数左半剩余元素个数，即得逆序对数目。

面试怎么讲。写完立刻自报家门：「区间是左闭右开，合并相等取左所以稳定，临时数组可以提到外层只分配一次」。主动提这两点，比等面试官抓 bug 印象分高得多。

思路。随机选基准与最右元素交换，再跑 Lomuto 划分；递归两侧。区间约定为左闭右闭 \([lo, hi]\)。

#include <cstdlib>
using namespace std;

int partition(vector<int>& a, int lo, int hi) {   // Lomuto 版，闭区间 [lo, hi]
    int r = lo + rand() % (hi - lo + 1);          // 随机基准：防有序输入退化
    swap(a[r], a[hi]);
    int pivot = a[hi];
    int i = lo;                                   // 不变量：a[lo, i) 均 <= pivot
    for (int j = lo; j < hi; ++j)
        if (a[j] <= pivot) swap(a[i++], a[j]);
    swap(a[i], a[hi]);                            // 基准落位：左侧 <=，右侧 >
    return i;
}

void quickSort(vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;
    int p = partition(a, lo, hi);
    quickSort(a, lo, p - 1);                      // 递归基准左侧
    quickSort(a, p + 1, hi);                      // 递归基准右侧
}

退化分析。若去掉随机化、固定取 a[hi] 为基准，而输入已升序：每轮划分结果是「左侧 \(n-1\) 个、右侧 0 个」，递推 \(T(n) = T(n-1) + \Theta(n) = \Theta(n^2)\)。随机化后，持续命中最坏划分的概率随 n 指数衰减，期望复杂度回到 \(O(n \log n)\)。Hoare 双向夹逼版交换更少，但返回的是分界 j，递归区间为 \([lo, j]\) 与 \([j+1, hi]\)，边界极易写错，面试选 Lomuto 更稳。

三路划分（重复元素多时）。

void quickSort3(vector<int>& a, int lo, int hi) {   // 三路：< p | == p | > p
    if (lo >= hi) return;
    int pivot = a[lo + rand() % (hi - lo + 1)];
    int lt = lo, i = lo, gt = hi;    // [lo, lt) < p；[lt, i) == p；(gt, hi] > p
    while (i <= gt) {
        if (a[i] < pivot)      swap(a[lt++], a[i++]);
        else if (a[i] > pivot) swap(a[i], a[gt--]);
        else                    ++i;            // 等于段整体跳过，不再递归
    }
    quickSort3(a, lo, lt - 1);                  // 只递归小于段
    quickSort3(a, gt + 1, hi);                  // 和大于段
}

复杂度与边界。平均 \(O(n \log n)\)、最坏 \(O(n^2)\)；全相等数组对三路版本是一次 \(O(n)\) 划分即结束，对两路版本是 \(O(n^2)\)。栈深最坏 \(O(n)\)（可先递归小半边、对大半边改循环，把栈压到 \(O(\log n)\)）。边界：空区间、单元素由 \(lo \ge hi\) 拦截；负数无影响；快排不稳定，需要稳定时换归并。

面试怎么讲。先声明「随机基准必须写，否则有序输入直接平方级」，写完 partition 后用手样例 [3, 1, 2] 走一遍 i、j 的移动。追问 std::sort 时答 introsort：快排 + 深度超 \(2\log_2 n\) 切堆排 + 小区间插入排序。

思路。把数组 \([0, n)\) 视为完全二叉树（节点 i 的孩子是 \(2i+1\)、\(2i+2\)）。第一阶段自底向上建大顶堆：从最后一个非叶节点 \(n/2 - 1\) 倒着做下沉；第二阶段每轮把堆顶（最大值）换到堆尾并缩短堆边界。

void siftDown(vector<int>& a, int root, int end) {  // 堆区间 [0, end]
    while (2 * root + 1 <= end) {                   // 左孩子下标 2*root+1
        int child = 2 * root + 1;
        if (child + 1 <= end && a[child] < a[child + 1]) ++child;  // 取更大孩子
        if (a[root] >= a[child]) return;            // 已满足堆序，提前终止
        swap(a[root], a[child]);
        root = child;                               // 继续向下修复
    }
}

void heapSort(vector<int>& a) {
    int n = (int)a.size();
    for (int i = n / 2 - 1; i >= 0; --i)            // 建堆：总代价 O(n)
        siftDown(a, i, n - 1);
    for (int end = n - 1; end > 0; --end) {         // 每轮把最大值归位到末尾
        swap(a[0], a[end]);
        siftDown(a, 0, end - 1);                    // 堆边界左移一位
    }
}

建堆为什么是 \(O(n)\)。高度为 h 的节点约 \(n/2^{h+1}\) 个，每个下沉至多 h 步，总代价 \(\sum_h h \cdot n/2^{h+1} = O(n)\)——绝大多数节点在底层、几乎不动。怎么读：不是每个节点都花 \(\log n\)，只有树顶少数节点花得多，加权求和是线性的。

复杂度与边界。最好 = 平均 = 最坏 \(O(n \log n)\)，额外空间 \(O(1)\)（原地交换、无递归）；不稳定（下沉会跨越相等元素）。空数组、单元素：两个循环都自然不执行。全相等输入：建堆后每轮下沉立即终止（a[root] ≥ a[child] 成立），接近线性但仍做 n 次交换，不如三路快排干脆。

为什么实践常输给快排。两点：一是访问模式——孩子下标 \(2i+1\)、\(2i+2\) 每步跨半个数组，缓存命中率远低于快排的顺序扫描；二是常数——每层最多比较两次、且大量交换。快排平均要快数倍。但堆排有两个不可替代的时刻：需要最坏 \(O(n \log n)\) 保证，或只允许 \(O(1)\) 额外空间。堆结构本身（优先队列）的用法见 004 章。

面试怎么讲。强调「建堆 O(n) + n 次 \(O(\log n)\) 下沉」，这两个数分开说，很多候选人误把建堆也当成 \(O(n \log n)\)。被问「那 std::sort 为什么不用堆排」时，答缓存与常数，再带出 introsort 的组合策略。