企业官网建设流程全解析

写快速排序最容易陷入的自我感动，就是把 Hoare 分区的骨架抄对之后，跑一组随机数据，看到耗时比冒泡快了两个数量级，然后关掉编辑器收工。真正上线或者刷题刷到十万级数据才会发现，同一份 Hoare 分区代码，喂进去一串基本有序的输入，耗时能从几十毫秒膨胀到几秒，甚至直接栈溢出。这篇接着上一篇的内容往下走，只聊两件事：三数取中怎么把基准从“闭眼摸一张”变成“有依据地挑一张”，以及小区间优化怎么把递归树底部的那些叶子节点从函数调用开销里救出来。顺带把 Hoare 分区最容易翻车的几个边界逐行拆开，让你能自己复现问题、自己定位、自己修。

读这篇不需要你已经是算法竞赛选手，只要你能看懂for循环和递归，并且亲手写过一次快排就行。我会把每个选择背后的“为什么”讲清楚——为什么基准不取第一个、为什么阈值不是随便定的 10、为什么 Hoare 返回的是j而不是i。这些都是文档里通常不会写、但你在调试器里会撞上的东西。

1. 递归树形状决定常数项：这版优化到底在优化什么

很多人对快排的理解停留在“平均 O(n log n)”这句结论上，于是觉得只要代码里出现了递归和分区，性能就自动达标了。这个认知偏差会导致一个很尴尬的局面：你写出来的快排确实比 O(n²) 的算法快，但你可能永远不知道自己离“理论上限”还差多远。

1.1 基准选不好，O(n²) 不是理论恐吓而是现场事故

快排的耗时由递归树的形状直接决定。每一次分区，基准把区间切成左右两段；如果每次都能切成对半，树高是 log₂n，总工作量是 n log n；如果每次都切成 1 和 n-1，树高退化到 n，总工作量变成 n² 级别。

关键在于，“取第一个元素作基准”这个做法，在已经有序的输入上必然每次都切出 1 和 n-1。我第一次正经测这件事的时候用的是十万条已经排好序的记录，程序跑了将近二十秒，而我以为是死循环，差点去加打印语句。实际上它没死，它只是在老老实实做 O(n²) 的活。

更隐蔽的是递归深度。十万元素、每次切 1 和 n-1，递归深度接近十万层，每层压一个栈帧，几百 KB 到几 MB 的栈空间瞬间见底，程序直接崩掉。所以“基准选择”这件事，本质上是在保护两样东西：时间复杂度的期望值和递归深度上界。

1.2 Hoare 分区在这套优化里的两个先手优势

既然要做优化，先得说清楚为什么这套代码用的是 Hoare 分区而不是教科书上更“好懂”的 Lomuto 分区（也就是用单指针扫一遍、把小于基准的往前挪那种）。

第二行是我最看重的一条。实际业务数据里“大量重复值”太常见了——按状态字段排序、按省份分组、按年龄段统计，几万个元素里可能只有十几个不同的值。Lomuto 在这种输入上会把所有等于基准的元素全甩到一边，分区彻底失衡；Hoare 的双指针在遇到相等元素时仍然会向中间靠拢，天然把重复元素摊到两侧。这一点是免费的性能保险，不用白不用。

至于“交换次数少”，多出来的收益在数据量大、元素体积大的时候才明显。如果你排的是int，缓存友好性比交换次数更重要；如果你排的是包含几十个字段的结构体，那交换次数直接决定内存带宽压力。

1.3 两张优化的分工：一个管上层结构，一个管底层叶片

我习惯把这两项优化理解成对递归树不同高度的处理：

• 三数取中作用于树的上层。它让前几层分区尽量均匀，把树高压住，避免出现“一条腿长、一条腿短”的畸形递归。上层只要歪一次，下面的所有节点都要多干活。
• 小区间优化作用于树的底层。当区间小到只剩十来个元素，继续递归下去的开销（函数调用、参数压栈、基准选择、分区循环）已经超过了排序本身的成本。这时候用插入排序接管，是纯粹在砍常数项。

两者互不冲突，但顺序上有讲究：小区间优化的阈值判断必须放在分区之前，否则你白做了一次分区才发现“哦这段只有八个元素”，那就白干了。这个细节后面第 3 节会展开。

2. 三数取中的代码写法与它撑不住的三类输入

“三数取中”这四个字听起来很学术，说白了就是：从区间里挑三个位置的值，比较一下，把中间那个值当作基准。常见取法是左端、中点、右端。

2.1 从“取第一个”到“取中位数”：三个下标怎么排

核心思路只有三步：比较a[l]和a[mid]，让小的在左边；比较a[l]和a[r]，让a[l]更小；比较a[mid]和a[r]，把a[mid]顶成中间值。三趟比较交换之后，a[l] <= a[mid] <= a[r]，中位数就落在mid位置上。

int mid = l + (r - l) / 2; // 注意别写成 (l + r) / 2 if (a[mid] < a[l]) std::swap(a[mid], a[l]); if (a[r] < a[l]) std::swap(a[r], a[l]); if (a[r] < a[mid]) std::swap(a[r], a[mid]); // 此时 a[l] <= a[mid] <= a[r]，中位数在 a[mid] std::swap(a[mid], a[l]); // 把中位数换到 l，供 Hoare 分区使用 int pivot = a[l];

mid用l + (r - l) / 2而不是(l + r) / 2，是个老生常谈但确实值得写进肌肉记忆的细节：当l和r都接近INT_MAX时后者会整型溢出成负数，接着就是越界读。虽然实际项目里数组长度不太可能到这个量级，但既然一行代码就能规避，没必要给自己留个理论坑。

最后那一步swap(a[mid], a[l])是把中位数“搬”到区间左端。为什么非要搬到左端？因为 Hoare 分区要拿pivot = a[l]作为扫描的天然停止位——这个值必须真实存在于区间内，才能保证两侧的do-while不会扫出边界。这一点在第 4 节会作为重点讲。

2.2 排序与归位的顺序不能反：一个低级但高频的错误

我在帮人看代码时见过一个很典型的写法：

// 错误示范 std::swap(a[mid], a[l]); // 先把中点搬到左端 if (a[mid] < a[l]) ... // 再比较？此时 a[l] 已经是被换下来的旧左端值了

这一换，三个位置上的值关系就乱了，后面再比较得出的“中位数”根本不成立。正确顺序永远是：先在原位比较交换把三个位置排成有序，最后再把中位数搬到l。搬运动作是收尾，不是开头。

还有一个变体思路是“不搬，直接以a[mid]的值作pivot”。这在 Hoare 里也能跑，但会失去“左端值是基准、必然成为停止位”的安全保证，需要额外处理越界判断，代码复杂度上升而收益为零。我建议就是老老实实搬过去。

2.3 有序、逆序、全相同：三数取中的能力边界

三数取中能解决什么，得说清楚它撑不住什么：

最后一行要特别注意：三数取中不是免死金牌。只要基准选择规则是确定性的、公开的，理论上就能构造出让每层都切偏的序列。想彻底免疫这类输入，就得引入随机化——随机挑一个下标和a[l]交换，再走原来的流程。代价是每次分区多一次随机数生成，实测在百万级数据上多出 1%～3% 的耗时，我觉得值。

至于“大量重复值”的极端情况，比如十万个元素只有三个不同取值。Hoare 分区本身能保证 O(n log n)，但你可以再往前一步，用三路划分（小于 / 等于 / 大于基准）把等于段整体跳过，这时候重复元素越多反而越快。这是三数取中之外的第三个话题，标题里没提，但如果你真正在生产环境排分组数据，值得单独写一版。

3. 小区间优化的阈值：8 还是 16，得让数据说话

小区间优化的思路朴素得不像优化：既然小数组上插入排序更快，那就在区间长度小于某个阈值时直接返回，最后对整个数组做一次插入排序收尾。

3.1 为什么小数组上插入排序能赢过快排

原因有三层，一层比一层关键。

第一层是函数调用开销。每次递归都要压栈、传参、保存返回地址，这些动作在指令级别是几十条起步。当区间只有 8 个元素时，分区本身可能只跑十几条比较指令，调用开销反而成了大头。

第二层是插入排序在小数组上的行为特性。插入排序的复杂度是 O(k²)，k 是区间长度。k=8 时内层循环平均只跑 2 次左右，实际比较次数约 20 次，而快排分区加递归在同样规模下要跑 40 次以上。平方复杂度在 k 小的时候完全不是劣势。

第三层，也是最容易被忽略的一层：缓存局部性。插入排序是顺序扫描加相邻移动，几乎不跳内存，CPU 预取器命中率极高。快排的分区是双指针相向扫描，两个指针分别在内存两端游走，缓存行的利用率天然不如单向扫描。现代 CPU 上这一项的差异比“比较次数”更明显，这也是为什么阈值实测值往往比教科书上写的“8 左右”要大一些。

3.2 递归出口改写与“最后一次性插入排序”的收尾结构

这里有个实现上的分歧，我先说结论：不要在递归里对每个小区间单独调用插入排序，而是让递归直接返回，最后对整段跑一次插入排序。

单独调用的写法是这样：

// 不推荐 if (r - l + 1 <= THRESHOLD) { insertionSort(a, l, r); return; }

它没错，但它有额外成本：每次调用插入排序都要重新初始化循环变量，而且这些小段的边界在主循环里被切得零零碎碎，缓存往返次数多。

推荐写法是：

// 排序入口 void sortArray(int *a, int n) { if (n < 2) return; quickSort(a, 0, n - 1); insertionSort(a, 0, n - 1); // 全局收尾，一次搞定 }

为什么全局收尾是对的？因为经过上层分区，任意一个长度为 k 的小段内部虽然没排序，但每个元素距离它最终的位置都不超过 k。换句话说，整个数组是“粗粒度有序、细粒度局部乱”的状态。在这种状态下跑插入排序，每个元素平均只需要移动 k/2 步，总比较次数约为 n·k/4，只看常数的话比 n log n 还低——因为省掉了全部递归和函数调用。

我用 k=16、n=10⁶ 估算过：主排序阶段约 1.9×10⁷ 次比较，收尾插入排序约 4×10⁶ 次移动，加起来和纯递归版本基本持平，但指令数少了一大截，实测耗时下降 8%～15%。

3.3 阈值实测表与我的取值习惯

阈值到底取多少，跟机器、编译器优化等级、元素类型都有关系。下表是我在一台普通开发机上跑的int数组结果，仅供你建立数量级的感觉，不要当成标准答案：

规律很清楚：8 到 16 之间有个平台期，16 之后开始回升。回升的原因是小段内部元素距离最终位置变远，收尾插入排序的平方项开始显形。

我的习惯是取 13 到 16 之间的偶数，如果元素是int这类 4 字节的小对象就取 16，如果是结构体就取 8～10，因为结构体拷贝成本高，让插入排序少搬几个更划算。这个取值不需要精确到个位，平台期内的差异基本在测量噪声范围内。

注意：换了编译器优化等级（比如从 -O0 到 -O2），最优阈值会往小移一点，因为函数调用的开销被编译器内联掉了一部分，递归的“罪”变轻了。所以最好在最终构建配置下做这组测试，别在 Debug 模式下量。

4. Hoare 分区的四个翻车点与逐行排查链路

这一节是我写这篇的主要动机。Hoare 分区那十几行代码，是快排里最容易“看起来对、跑起来错”的部分。下面四个坑，我每个都真踩过。

4.1 返回值是 j 不是 i：划分点语义的坑

先看标准实现：

int i = l - 1, j = r + 1; while (true) { do { ++i; } while (a[i] < pivot); do { --j; } while (a[j] > pivot); if (i >= j) break; std::swap(a[i], a[j]); } // 此处 j 是返回的划分点

很多人（包括曾经的我）会直觉地认为“相遇点i就是划分点”，于是返回i，然后写成quickSort(a, l, i - 1)和quickSort(a, i + 1, r)。这个写法在某些输入上能跑，在某些输入上会死循环或者漏排元素。

原因是 Hoare 分区不保证基准落在最终位置上。它只保证：[l, j]里的所有元素 ≤[j+1, r]里的所有元素，且j < r。注意这里的两个性质：一是两段各自内部无序，二是j最多到r-1，绝不会等于r。所以正确的递归调用是：

quickSort(a, l, j); // 左段包含 j quickSort(a, j + 1, r); // 右段从 j+1 开始

左段必须包含j，因为a[j]本身还没被保证在正确位置。我第一次把j写成j-1的时候，跑了五十万随机数据对拍std::sort，发现有两个元素顺序不对——那种“只错一点点”的 bug 比崩溃难查十倍。

4.2 i/j 的起始位置与 do-while 顺序

i = l - 1和j = r + 1这两个初值不能改。它们不是“装饰”，而是配合do-while的语义：do-while先自增再判断，所以第一次进入循环时i变成l、j变成r，正好从区间两端开始比较。

为什么用do-while而不是while？因为即使a[l] == pivot（此时l位置是基准位），我们也需要让i至少前进到l，让j至少后退到r，否则指针一步不动，循环永远出不去。这个细节就是死循环的根源之一。

还有一个变体是把内层写成while (a[i] < pivot) ++i;，配合i = l。这在一部分数据上是对的，但当a[l] == pivot且数组里所有元素都等于pivot时，i从头到尾不会动，j也不会动，直接死锁。所以老老实实用do-while加l-1 / r+1，不要自作聪明省一步。

4.3 只剩两个元素时的死循环现场复现

这段是我调试时间最长的一次，值得完整复盘。

现象：随机数据跑得好好的，跑到一组构造数据上程序挂住，CPU 占满单核，没有输出。

第一步：定位到卡在小规模区间。我加了个计数器，发现分区函数被调用了上百万次，而数组只有两万个元素。说明某次分区没有把区间缩小。

第二步：缩小复现范围。我把输入砍到只剩三个元素，逐个试，找到一组[2, 1, 2]能让它卡住。这一步很关键，别在几万元素上打转，手写三五个元素就能复现问题。

第三步：手动走一遍循环。假设l=0, r=2，三数取中后a[0]=2作基准（pivot=2）。i=-1, j=3。

• 第一轮：++i到 0，a[0]=2 < 2为假，停；--j到 2，a[2]=2 > 2为假，停；i=0 < j=2，交换a[0]和a[2]（值相同，无变化）。
• 第二轮：++i到 1，a[1]=1 < 2为真，继续++i到 2，a[2]=2 < 2为假，停；--j到 1，a[1]=1 > 2为假，停；i=2 >= j=1，跳出，返回j=1。

结果返回j=1，左段[0,1]、右段[2,2]，区间正常缩小。所以这个用例没问题。

第四步：换个角度看，问题出在“返回 j 但递归写成了 i”。我把递归改回quickSort(a, l, i-1)之后立刻复现了。当i == l且j == l时（比如区间内所有元素都大于基准），i-1 = l-1，递归进入[l, l-1]这种左端点大于右端点的非法区间。如果函数开头没有l >= r的保护，就会一路递归下探到负数下标，表现为越界读或者栈爆炸。

结论：死循环大多不是分区循环本身的问题，而是返回值和递归区间不匹配。修法是二选一：要么严格用j加[l, j] / [j+1, r]，要么换 Lomuto 用p加[l, p-1] / [p+1, r]。混着用一定出事。

4.4 递归深度与栈：先递归较小的一侧

即使分区均匀，递归写法的栈深也有讲究。常规写法是先递归左段再递归右段，栈深等于树高。虽然平均情况下树高是 log n，但你没发保证最坏情况不发生。

做法是把递归改成“只对较小的一侧递归，较大的一侧用循环继续”：

while (l < r) { // 分区，得到 j if (j - l < r - j) { quickSort(a, l, j); // 递归短的那一侧 l = j + 1; // 长的那一侧用循环消化 } else { quickSort(a, j + 1, r); r = j; } }

这样栈深被严格压到 O(log n)，即使遇到对抗数据也不会爆栈。代码结构上把尾递归变成了迭代，编译器本来就愿意帮你做这个优化，但显式写出来更保险，也不依赖编译器的尾调用分析是否开启。

5. 拼装完整实现：从单测到十万级压力测试

前面几节讲的是零件，这节把它们装起来，并且给出可复现的验证方法。

5.1 完整代码

#include <algorithm> static const int THRESHOLD = 16; static void insertionSort(int *a, int l, int r) { for (int i = l + 1; i <= r; ++i) { int key = a[i]; int j = i - 1; while (j >= l && a[j] > key) { // 用 > 而不是 >=，减少无谓搬移 a[j + 1] = a[j]; --j; } a[j + 1] = key; } } static void quickSort(int *a, int l, int r) { while (l < r) { if (r - l + 1 <= THRESHOLD) return; // 交给最终的统一收尾 int mid = l + ((r - l) >> 1); if (a[mid] < a[l]) std::swap(a[mid], a[l]); if (a[r] < a[l]) std::swap(a[r], a[l]); if (a[r] < a[mid]) std::swap(a[r], a[mid]); std::swap(a[mid], a[l]); // 中位数归位到 l int pivot = a[l]; int i = l - 1, j = r + 1; while (true) { do { ++i; } while (a[i] < pivot); do { --j; } while (a[j] > pivot); if (i >= j) break; std::swap(a[i], a[j]); } if (j - l < r - j) { quickSort(a, l, j); l = j + 1; } else { quickSort(a, j + 1, r); r = j; } } } void sortArray(int *a, int n) { if (n < 2) return; quickSort(a, 0, n - 1); insertionSort(a, 0, n - 1); }

几个值得对照检查的点：mid用位移计算避免溢出；三数取中的三次比较交换顺序不能乱；pivot取的是值而不是下标；i/j的初值分别是l-1 / r+1；返回值用j且左段包含j；较小侧递归、较大侧循环。

5.2 五组输入的对拍与耗时

只测耗时不够，先得保证正确。我的做法是用std::sort当对拍基准，跑完两边逐位比对，任何一位不等就打印下标和前十个元素现场。

测试数据集我固定用五类，每次改动代码都全部跑一遍：

最后一类“近乎有序”是我最推荐的测试用例。真实数据的排序字段往往是时间戳、自增 ID、或者某种被预处理的序号，绝大多数情况下是基本有序的。如果你只看随机数据，很可能漏掉三数取中本该救你的那个场景。

5.3 与库函数差距在哪、值不值得继续抠

十万个int的实测，我这套手写实现在随机数据上大约是标准库的 1.5 倍耗时，近乎有序数据上差距缩小到 1.2 倍左右。差距主要来自三处：标准库的对数深度控制更精细（超过 2·log n 会切换到堆排序，彻底堵死最坏情况）；它的插入排序实现做了移位优化和寄存器驻留；以及它避免了我这里每次都重算三次比较的分支预测失败。

要不要继续抠？我的判断标准是：如果排序只占你程序总耗时的 5% 以内，别抠了，收工。手写快排的价值在于你能改——比如把元素换成索引数组做间接排序、加上自定义比较器、或者在分区时顺带统计某个字段的分布。纯粹为了跑分去和标准库比，性价比极低。

真正值得继续做的两件事：一是给基准选择加随机化兜底，二是准备好三路划分版本应对重复值密集的输入。这两条属于“花半小时写，省半天排查”的投资。

最后提醒一个容易忽略的地方：如果你的数组元素是结构体或者类，所有swap都会触发三次拷贝构造。这种情况下把比较和交换拆开、用移动语义、或者干脆排索引数组，收益比调阈值大得多。我吃过一次亏，排一个 128 字节的结构体，把阈值从 16 降到 8 才勉强追平，最后换成排下标数组，耗时直接砍掉四成。