手写排序总览：快排、归并、堆排序的对比与选择

排序是算法的手工基础课：面试要求手写的「三巨头」——快速排序、归并排序、堆排序——都是 O(n log n)，但性格迥异。本库《第 K 个最大元素》用过快速选择（快排的兄弟），《合并 K 个升序链表》用过归并的思想（本库语境）；本篇把三个排序一次写清、对比取舍，并回答那个终极问题：既然 Python 的 sorted 又快又稳，为什么还要手写。

快速排序：分治 + 分区，平均最快的原地排序

快排的思想：选一个基准（pivot），把数组分区（partition）——比基准小的放左、大的放右，基准落在最终位置；然后对左右两半递归。Lomuto 分区（最易写的版本）：把最后一个元素当基准，单指针扫一遍，维护「小于区」的边界：

import random

def quick_sort(arr: list[int], lo: int = 0, hi: int | None = None) -> None:
    if hi is None:
        hi = len(arr) - 1
    if lo >= hi:
        return
    p = random.randint(lo, hi)          # 随机基准：防有序输入的 O(n²) 退化
    arr[p], arr[hi] = arr[hi], arr[p]
    pivot, boundary = arr[hi], lo       # Lomuto 分区：boundary 是「小于区」右界
    for i in range(lo, hi):
        if arr[i] < pivot:
            arr[i], arr[boundary] = arr[boundary], arr[i]
            boundary += 1
    arr[boundary], arr[hi] = arr[hi], arr[boundary]   # 基准归位
    quick_sort(arr, lo, boundary - 1)
    quick_sort(arr, boundary + 1, hi)

性格：平均 O(n log n) 且常数最小（缓存友好、原地 O(log n) 栈空间）——实践中最快的通用排序；弱点：最坏 O(n²)（基准总选到极值——随机化是标准解药），不稳定（相等元素的相对顺序会被打乱）。快排的兄弟：快速选择（只递归包含第 k 位的一侧，平均 O(n)——本库《第 K 个最大元素》正是这套分区的应用）。

归并排序：稳定合并，链表与外排的王者

归并的思想：分成两半递归排序，然后合并两个有序数组（双指针线性合并——本库《合并 K 个升序链表》的多路归并是它的 k 路推广）。性格：稳定 O(n log n)（最好最坏都一样——无退化风险）、稳定排序（相等元素保持原序——这是它与快排/堆排序的决定性差异）、空间 O(n)（合并需要辅助数组——主要缺点）。它的主场：链表排序（链表合并 O(1) 空间——本库《合并 K 个升序链表》正是 k 路归并）、外部排序（磁盘上的大数据排序——归并是多趟外排的天然结构）、以及需要稳定性的场景（多关键字排序的次级排序依赖稳定性）。归并与快排的分治差异也值得记：快排是「先分区后递归」（工作在递归前做），归并是「先递归后合并」（工作在递归后做）——前者工作在下降的路上，后者工作在回来的路上——这句话概括了所有分治算法的两种形态。

堆排序：原地选择，以及「为什么不如快排快」

堆排序的思想：先建最大堆（本库语境：原数组原地建堆，O(n)），然后反复「堆顶（最大值）与末尾交换 + 堆尺寸减一 + 下沉修复」——每次把当前最大值放到末尾，n-1 轮后数组有序。性格：严格 O(n log n)（无最坏退化）、原地 O(1) 空间、不稳定；为什么实践中不如快排快：堆的下沉访问的内存模式跳跃（缓存不友好——快排的顺序扫描缓存命中率高），常数因子大。它的主场：内存极严的原地场景（嵌入式）、以及「只要前 k 大」的堆选择（本库《前 K 个高频元素》的最小堆、优先队列的实现根基——堆作为「数据结构」的价值比作为「排序算法」更大）。三巨头之外的注脚：Python 的 sorted 用 Timsort（归并+插入的混合，稳定）、C++ 的 sort 用内省排序（快排+堆排+插入的混合，防退化）——工业级排序都是混合体，纯手写版是教学与面试的产物。

手写的边界：什么时候写、什么时候用库

最后一个诚实的问题：工程中永远用库（sorted/sort——高度优化、稳定保证、经过实战检验），手写的价值在三个场景。场景一：面试——快排手写是基本功考试（分区无 bug、随机化意识、复杂度分析）；场景二：特殊需求——库排序不满足的定制（按自定义比较的多键、部分排序、稳定性的特殊要求、或排序中的副作用——本库《打家劫舍》式的「排序中做别的事」）；场景三：理解依赖排序的算法——快速选择、归并思想（合并 K 链）、堆（优先队列）都以排序为地基——手写排序的目的不是排序本身，是把「分治、分区、堆化」这三套基本功练进手里。学习的建议：三个排序各手写一遍 + 各自的核心变体（快排的快速选择、归并的 k 路、堆的建堆）跑通本地测试——这大概是算法手工课的全部作业量，也是回报率最高的作业。

比较排序的下界：为什么 O(n log n) 是天花板

排序总览的最后回答一个理论问题：为什么比较排序不可能快于 O(n log n)。决策树论证：任何基于比较的排序，可以被建模为一棵决策树——每个内部节点是一次比较（两种结果），叶子是最终的排列（n 个元素有 n! 种可能的排列）；区分 n! 种排列，决策树至少需要 n! 个叶子，而高度为 h 的二叉树最多 2^h 个叶子 → h ≥ log₂(n!)。斯特林近似展开 log₂(n!) ≈ n log n——O(n log n) 是比较排序的信息论下界：每一次比较最多获得一比特的信息，区分 n! 种排列所需的信息量就是 n log n 比特。绕过下界的两条路：利用元素的特殊结构（计数排序、桶排序、基数排序——不是「比较」而是「按值定位」，绕开了决策树模型，达到 O(n+k)——前提是值域可枚举，本库《前 K 个高频》的桶排序同理）；利用输入的部分有序（Timsort 对近乎有序的数据接近 O(n)——利用已有的结构信息）。理论的实际意义：它告诉你优化比较排序的算法（更快的分区、更好的基准选择）只能在常数上做文章；数量级的突破必须换模型（非比较、或利用输入结构）——知道天花板在哪，才知道往哪突围。

三种排序的测试基准：实测数字与直觉的对照

三种排序的「性格差异」值得用实测数字校准（参考量级，具体因机器而异）。实测的形态：随机数组 100 万个整数，各排序的耗时对比——快排（含随机化）通常是基准的冠军（缓存友好+分支预测友好）；归并慢 1.5-2 倍（辅助数组的内存开销与拷贝）；堆排序再慢 2-3 倍（跳跃的内存访问模式——缓存命中率是排序实测的隐藏主角）。部分有序输入的变化：近乎有序的数据上，插入排序（小数据的标配）接近 O(n)、Timsort 直接 O(n)——而快排在「精心构造的反例」上退化到 O(n²)（mc 模式的对抗输入——这也是工业排序引入内省机制的动因）。稳定性实测：对结构体按次键排序，稳定排序保留主键序、不稳定排序打乱——「稳定性」不是理论洁癖，是多键排序的正确性依赖。实测的三条综合读数：随机数据快排冠军（常数优势）、近有序数据 Timsort/插入接近线性（利用已有结构）、内存受限或要稳定时归并/堆各就各位——实测数字与理论复杂度的关系：复杂度画曲线的形状，实测定曲线的常数——两者合起来才是完整的选择依据。

Timsort 的窥探：工业排序的混合智慧

Python 的 sorted 背后的 Timsort 值得窥探一眼——它是「工业排序如何混合智慧」的最佳样本。Timsort 的两个部件：run 识别——扫描数组找出天然的有序段（升序或严格降序，降序段就地反转），天然有序的数据几乎零成本；run 合并——把 run 按类似归并的方式两两合并。插入排序的角色：短 run（小于阈值 32）用插入排序补齐——小数据的插入排序常数优势 + 大数据的归并稳健性，混合体的每个部件都在自己的最佳区段工作。对比本库的三大手写排序：快排的分区思想、归并的稳定性、插入的小数据优势——Timsort 把三者的优点各取所需——工业级排序没有「纯粹的信仰」，只有「针对真实数据分布的混合策略」——这也是「手写排序练习」与「工业排序实现」的定位差异：前者练基本功，后者是基本功之上的工程混合艺术。

稳定性与「多键排序」：Python 的稳定排序实战

排序的稳定性在 Python 中有一个非常实用的应用场景：多键排序的实现。Python 的 sorted 是稳定的（文档明确保证），这意味着可以「分轮排序」来实现多键排序：先按次要键排序（如部门），再按主要键排序（如薪资）——第二次排序保留第一次排序的相对顺序（稳定性保证）——最终结果就是「先按部门分组、组内按薪资排序」。与「一次性多键比较」的对比：sorted(employees, key=lambda e: (e.dept, -e.salary)) 的元组比较也可以实现——但分轮排序的优势在于每轮的 key 更简单（不用构造复合元组），且可以动态调整键的优先级（改变轮次顺序 = 改变优先级）。稳定性的工程纪律：多键排序时「从次要键到主要键逐轮排序」的顺序不能反（反了就是主要键被次要键覆盖）；以及利用稳定性的设计（先按自定义规则分桶，桶内保持原始序——稳定性的保证让「分桶不打乱桶内」成为可能）。稳定性的实战价值总结：它不是「理论洁癖」，是多键排序和「保序分桶」的技术前提——没有稳定性，Python 的 sorted 就无法安全地分轮使用。

小结

排序总览收成四条：快排——分治+分区、平均最快、原地，弱点是最坏退化（随机化解药）与不稳定；归并——稳定 O(n log n)、链表与外排的王者，代价是 O(n) 辅助空间，工作在递归回来的路上；堆排序——严格 O(n log n) 原地但不稳定，缓存不友好是它输给快排的原因，堆作为数据结构的价值大于作为排序；工程用库、面试手写、排序是分治/分区/堆化三套基本功的训练场。排序的三个 O(n log n) 各有性格——选排序就是选「时间常数、稳定性、空间」三个维度的折中，没有全能冠军。

参考资料

LeetCode 912. 排序数组 —— 手写三大排序的练习场（本题考的就是这个）
本库前篇：《LeetCode 215. 数组中的第 K 个最大元素》《合并 K 个升序链表》《LeetCode 347. 前 K 个高频元素》
Timsort 与 Introsort 的公开材料 —— 工业级混合排序的设计