选择排序这个词大部分人在数据结构课上第一次听到然后在之后很长一段时间里再没用过堆排序反过来名字听着唬人写在简历上挺好看真让人手写一遍十有八九会卡在下沉调整的边界上。我这些年带过几批做算法入门的同学也在业务里处理过对内存和元素移动成本比较敏感的排序需求越琢磨越觉得这两个算法必须放在一起讲——它们共用同一副骨架每一轮从未排序区间里挑一个元素放到已排序区间的边界上。真正的区别只有一个字挑的方式不同。普通选择排序是老老实实线性扫一遍堆排序是提前用一棵完全二叉树把谁是最值这件事组织好把每次挑的成本从 O(n) 压到 O(log n)。这篇文章会把两套代码从零写一遍把建堆的下标推导、下沉的终止条件、复杂度里那个容易被记错的 O(n) 建堆证明、稳定性被破坏的具体现场、以及本地实测的数据都摆出来。适合刚学完基础排序想弄明白为什么慢的新手也适合工作几年、需要用堆去解决 Top-K 和调度问题但一直没系统梳理过的同学。1. 从每轮挑一个说起两者的共同骨架与分岔点1.1 为什么这两件事值得放在一起讲单独看选择排序它简单到几乎没什么可讲的两重循环、一个最小值下标五分钟写完单独看堆排序它复杂到让人怀疑人生建堆、下沉、缩堆三步走写完还得对着测试用例反复调。可一旦把两者并排放很多东西立刻清楚了堆排序不是凭空冒出来的新算法它就是对选择排序那句从剩余元素里找最小的替换实现。选择排序每轮线性扫描找最小代价是 O(n)堆排序提前维护了一个堆结构让堆顶永远是最大值取最值的代价变成 O(1)代价是取完之后要花 O(log n) 修复结构。这个视角非常重要。很多人学堆排序时把它当成一个独立的、需要死记硬背的流程结果就是背得下来、改不动、错一处就全盘崩溃。而把它理解成选择排序 堆这种数据结构之后你会发现每一行代码都有明确的意图建堆是为了让结构成立下沉是为了在破坏结构后修复交换堆顶和末尾是为了把已经选出来的最值固定到最终位置。理解了意图边界条件就不再是靠试出来的。我在给初学者做代码 review 的时候有个习惯先问一句你这行是在挑元素还是在修结构答得上来的人代码基本不会出大问题答不上来的人往往是把两个阶段搅在一起写导致缩堆的时候还在用原始长度或者建堆的时候误以为自己在排序。1.2 共同基因未排序区间的边界推进两个算法在宏观流程上是完全一样的维护一个边界边界左边是已经排好序的部分边界右边是待处理的部分每一轮把边界向右推一格推 n-1 轮之后整个数组有序。选择排序里这个边界就是外层循环变量 i堆排序里它是当前堆的有效长度。拿一个具体例子走一遍会更直观。数组[7, 3, 9, 1, 5]选择排序第一轮从下标 0 开始扫找到最小值 1 在下标 3把它和下标 0 的 7 交换得到[1, 3, 9, 7, 5]边界推一位第二轮从下标 1 开始扫最小值是 3 本来就在位置不动第三轮从下标 2 开始最小值 5 在下标 4交换后[1, 3, 5, 7, 9]第四轮从下标 3 开始7 和 9 已经是正确顺序。四轮结束。堆排序做的事情本质相同只不过它不从头扫而是先把整个数组整理成一个大顶堆[9, 7, 5, 1, 3]此时堆顶 9 就是全局最大值把它和末尾的 3 交换得到[3, 7, 5, 1, 9]然后把有效堆长度从 5 缩到 4对新的堆顶 3 做一次下沉恢复成大顶堆[7, 3, 5, 1, 9]接着取堆顶 7 和下标 3 的 1 交换……如此往复。你会发现已排序区是从数组尾部往前长的和选择排序正好相反但逻辑完全相同。这个观察带来的直接好处是调试堆排序时你完全可以用选择排序的中间结果做参照。两者在每一轮结束时的已排序部分应该是一模一样的集合堆排序是从后往前选择排序是从前往后如果对不上说明你的堆维护出错了而不是排序逻辑本身有问题。1.3 分岔点线性扫描与树形扫描的成本差把共同骨架剥掉之后剩下的差异就是找最值这一件事的实现。选择排序每次从头到尾扫一遍未排序区间第 i 轮要比较 n-i-1 次累加起来是 n(n-1)/2 次比较这个数字跟数据的初始状态完全无关——哪怕数组本来就有序它也要老老实实扫完。堆排序的做法是把找最值的成本前置。建堆阶段一次性把数组整理成堆让每个节点都不小于它的两个孩子于是根节点天然就是最大值。之后每次取走根节点只需要把末尾元素挪到根上再沿一条从根到叶的路径下沉最多走 log n 层每层最多两次比较。取 n-1 次总比较次数在 2n log n 量级。成本差在哪用生活里的例子说选择排序像是每次要找班里最高的同学就把全班从头点名一遍堆排序像是提前让全班按身高排成一棵每个家长都比自己孩子高的树之后每次找最高的只需要看树根取走之后沿着一条线调整几个人就行。前者的成本是线性的、重复的、无法复用的后者用一次 O(n) 的预处理换来了 n 次 O(log n) 的查询。代价也很明显选择排序的代码你写错的可能性接近于零堆排序的代码我第一次写的时候在三个地方翻过车——建堆的起点、下沉的边界、以及交换后忘了继续往下走。这就是典型的空间换时间、复杂度换心智负担。理解了这个取舍后面的所有细节就都是在为把这次预处理做对服务。2. 普通选择排序把简单做到极致2.1 核心逻辑与一次完整执行轨迹先把代码贴出来Java 版本这是最常见的面试和作业形态public static void selectionSort(int[] arr) { int n arr.length; for (int i 0; i n - 1; i) { int minIdx i; for (int j i 1; j n; j) { if (arr[j] arr[minIdx]) { minIdx j; } } if (minIdx ! i) { int tmp arr[i]; arr[i] arr[minIdx]; arr[minIdx] tmp; } } }外层循环到n - 1就停因为当只剩最后一个元素时它必然是剩下的最大值位置已经确定不需要再处理。内层从i 1开始因为arr[i]已经用minIdx i初始化过了没必要跟自己比。这两个细节是最容易写错的地方写成i n或者j i都不会报错只是多做了一次无意义的操作属于不影响正确性但暴露基本功的瑕疵。执行轨迹用[64, 25, 12, 22, 11]走一遍轮次未排序区间找到的最小值交换后数组1[64, 25, 12, 22, 11]11下标 4[11, 25, 12, 22, 64]2[25, 12, 22, 64]12下标 2[11, 12, 25, 22, 64]3[25, 22, 64]22下标 3[11, 12, 22, 25, 64]4[25, 64]25下标 3[11, 12, 22, 25, 64]注意第三轮结束后数组其实已经有序了但算法并不知道第四轮照样要从下标 3 扫到 4 做一次比较。这就是选择排序不感知数据状态的体现。你可以加一个swapped标记做提前退出优化但效果极其有限——因为即使某一轮没发生交换也说明不了后面一定有序只能省掉极少数情况。这个优化我做过多组实测在随机数据上收益基本为零反而多了一个分支判断所以我一般不写。代码量就这么点但有个细节值得说if (minIdx ! i)这个判断不能省吗能省少一次交换而已但如果元素是对象引用或者大结构体这次省下的可能是几百字节的内存拷贝。这个习惯在 C 语言里写结构体排序时尤其重要我见过把struct直接当元素传的代码多交换一次可能就是几微秒。2.2 交换次数 O(n) 这个卖点到底值多少钱选择排序有一个被严重低估的优点整个排序过程中交换次数不超过 n-1 次。因为每一轮最多交换一次而总共 n-1 轮。这个性质在大部分排序教程里只是一笔带过但在真实工程里它有明确的适用场景。什么样的场景会看重交换次数答案是写操作比读操作贵得多的时候。典型的例子是往闪存介质写数据擦写寿命是有限的每多写一次就多消耗一次寿命再比如元素是很大的结构体一次交换要复制几十上百字节而一次比较只需要读几个字段还有一种是元素存储在远端或者慢速介质上写入的延迟远高于本地读取。在这些场景下选择排序的 n-1 次交换就是一个非常漂亮的性质。对比一下冒泡排序最坏情况要交换 O(n²) 次插入排序也是 O(n²) 次移动。虽然它们三个的时间复杂度都是 O(n²)但当移动成本成为瓶颈时三者的实际表现能差出两个数量级。我做过一个粗略估算假设每个元素是 1KB 的结构体一次比较耗时 1 个单位一次交换耗时 500 个单位那么在 n 1000 时选择排序的总成本约 50 万次比较 1000 次交换 100 万单位插入排序的最坏情况则是 50 万次比较 50 万次交换 2.5 亿单位差了 250 倍。当然前提是你真的处在这样一个移动贵、比较便宜的环境里。如果元素是 4 字节整数比较和交换的成本差不到 10 倍那这点优势完全被 O(n²) 的比较次数吃掉了。所以我在实际选型时的判断标准很直接n 小于几千、元素移动成本显著高于比较成本、且内存空间吃紧不能用归并这三个条件同时满足时我才会考虑选择排序否则一律用库函数。还有一点容易被忽略选择排序的交换次数虽然少但每次交换都是远距离的可能把数组里两个毫不相干的元素换到一起。这对缓存极不友好因为每次交换都要访问两个可能相隔很远的缓存行。所以在 n 稍大的时候即使交换次数本身不多缓存未命中的代价也会抵消掉理论上的优势。2.3 稳定性问题与二元选择排序的优化尝试选择排序是不稳定的这一点很多人知道但说不清楚为什么。根源就在那句交换上把最小值换到前面的时候被换走的那个元素可能和它后面某个元素相等交换之后两者的相对顺序就反了。举一个最小的反例数组[5a, 5b, 2]这里用 a、b 区分两个值相同的 5。第一轮找最小值找到 2 在下标 2和下标 0 的 5a 交换数组变成[2, 5b, 5a]两个 5 的相对顺序反了。这就是不稳定的全部原因没有第二种可能。如果你确实需要稳定有个改法不交换改成整体后移——找到最小值后把 i 到 minIdx-1 的元素集体往后挪一位再把最小值放到 i 位置。这样稳定性保住了但移动次数从 1 次变成 minIdx - i 次O(n) 的交换优势彻底没了。所以实践中我一般不去改它需要稳定就直接用归并或者插入不要勉强让一个不适合的算法去做它不擅长的事。另一个常见的优化尝试是二元选择排序也叫双端选择排序每一轮同时找出最小值和最大值最小值放前面最大值放后面这样外层循环只需要跑 n/2 轮比较次数理论上能减少一半。代码看起来是这样public static void doubleSelectionSort(int[] arr) { int n arr.length; for (int left 0, right n - 1; left right; left, right--) { int minIdx left, maxIdx right; if (arr[minIdx] arr[maxIdx]) { int t minIdx; minIdx maxIdx; maxIdx t; } for (int j left 1; j right; j) { if (arr[j] arr[minIdx]) minIdx j; else if (arr[j] arr[maxIdx]) maxIdx j; } // 先把最小值换到 left swap(arr, left, minIdx); // 注意如果最大值原本在 left 位置交换后被挪到 minIdx 了 if (maxIdx left) maxIdx minIdx; swap(arr, right, maxIdx); } }这段代码里那个if (maxIdx left) maxIdx minIdx;是裸的坑。第一次写的时候我没加这行测试用例里凡是首元素恰好是最大值的数组全部排错。原因很直接最小值交换发生在最大值交换之前如果最大值原本就在 left 位置第一次交换会把它挪到 minIdx 去此时再用旧的 maxIdx 去换换的就是错误的元素了。这个坑我在给同学改作业的时候见过至少七八次属于典型的高频错误。至于这个优化到底值不值比较次数确实减半了但交换次数翻倍每轮最多两次交换而且常数因子没变、复杂度量级也没变。在元素移动成本高的场景下这个优化反而是负收益。所以我一般不推荐写这个版本除非纯粹为了练习边界处理。3. 堆排序用完全二叉树把找最值压到对数级3.1 数组存堆父子下标的推导与两套公式的坑堆是一棵完全二叉树而完全二叉树有一个非常好的性质它可以在数组里紧凑地存下来不浪费任何空间也不需要指针。前提是你要记住父子下标的换算关系这是所有堆相关代码的地基。对于 0 基数组绝大多数编程语言下标为i的节点左孩子是2 * i 1右孩子是2 * i 2下标为i的节点父节点是(i - 1) / 2整数除法向下取整对于 1 基数组算法教材、某些竞赛代码喜欢这么写左孩子2 * i右孩子2 * i 1父节点i / 2这两套公式绝对不能混用混一次就是全盘崩溃。我见过有人代码里数组是 0 基的但按 1 基公式写2 * i结果下标 0 的左孩子算出来还是 0直接从自己下沉到自己死循环。更隐蔽的是它不一定会死循环可能只是让某些节点永远参与不了比较排序结果看起来差不多对只有用对拍测试才能发现。这两个公式怎么推导出来的不需要背画一棵树就行。节点 0 是第一层节点 1、2 是第二层节点 3、4、5、6 是第三层。你会发现下标为 i 的节点之前有 i 个节点这些节点里叶子层之前的完整层贡献的节点数正好让孩子的起始位置落在 2i1。严谨一点的推导是前 h 层满二叉树的节点数是 2^h - 1节点 i 的深度为 d 时它之前有 2^d - 1 个祖先层节点加上本层的偏移量……推导过程不重要重要的是你自己拿笔在纸上画一遍 0 到 6 这七个下标把父子连线画出来亲眼确认一次以后就不会记混了。还有一个容易被忽略的隐患2 * i 1在i很大时可能溢出。Java 的int上限约 21 亿当i超过 10 亿时2 * i 1就会变成负数。实际上一个能存 10 亿元素的 int 数组需要 4GB 内存一般不会碰到但如果你用的是long数组做大规模测试或者在其他语言里处理超大数组最好把2 * i 1写成i (i 1)或者显式转成更宽的类型。这种细节平时不用管真出问题时排查起来极其痛苦因为表现为随机位置越界或者数据错乱。3.2 建堆为什么从最后一个非叶子节点倒着走建堆是整个堆排序里最反直觉的一步。代码只有三行但那个起点n / 2 - 1让无数人卡住。for (int i n / 2 - 1; i 0; i--) { siftDown(arr, i, n); }为什么是n / 2 - 1因为它是最后一个非叶子节点的下标。推导很简单最后一个节点的下标是n - 1它的父节点是((n - 1) - 1) / 2 (n - 2) / 2。对于偶数 n(n-2)/2 n/2 - 1对于奇数 n(n-2)/2向下取整同样等于n/2 - 1。所以用n/2 - 1一个表达式就能覆盖两种情况。为什么从它开始往前倒着走因为下沉操作的前提是孩子节点已经是合法的堆。叶子节点没有孩子天然是合法的堆所以从最后一个非叶子节点开始它的两个孩子一定都是叶子下沉操作可以正常工作。处理完这个节点后往前退一位它的孩子要么是叶子要么是刚刚处理过的子树根它们都已经是合法堆了所以它也可以放心下沉。这就是一个从底向上的归纳每一层的正确性都建立在下一层已经正确的基础上。如果反过来从根节点开始往下走呢那就不行了。根节点下沉的时候它的孩子子树还没调整好如果孩子不是合法的堆下沉完了根也不是最大值整个结构就是错的。我最早学的时候就在这上面栽过天真地以为从根开始一路往下修不就行了结果测试用例里凡是较大的元素在深层的一律排错。后来想明白了堆的性质是自底向上满足的你必须先在底层建立局部有序才能让上层的选择有意义。建堆的时间复杂度是 O(n)这个结论很多人知道但说不清推导。按照每层的节点数和每个节点可能下沉的最大深度来算高度为 h 的节点大约有 n / 2^(h1) 个每个最多下沉 h 层h 从 0 开始叶子 h0求和 S Σ h * n / 2^(h1)。这个级数是收敛的令 k 1/2则 S n/2 * Σ h * k^h而 Σ h * k^h 在 |k| 1 时等于 k / (1-k)² 0.5 / 0.25 2。所以 S ≈ n/2 * 2 n。所以是 O(n)不是 O(n log n)。为什么底层节点多、但下沉距离短上层节点少、但下沉距离长两者乘积的分布恰好让总和收敛到线性关键在于节点数随深度指数衰减下沉距离随深度线性增长指数衰减比线性增长快得多所以总和被系数小的底层主导了。这个直觉比公式更重要理解了它你就明白为什么建堆这么便宜也就能理解为什么在只需要前 k 个最大的场景里建一个大小为 k 的堆比排整个数组划算得多。3.3 下沉调整的写法、边界与终止条件下沉siftDown是堆排序里真正干活的函数也是最容易写错的地方。先看完整版private static void siftDown(int[] arr, int root, int size) { while (true) { int left 2 * root 1; if (left size) { return; } int largest left; int right left 1; if (right size arr[right] arr[left]) { largest right; } if (arr[largest] arr[root]) { return; } swap(arr, root, largest); root largest; } }这段代码有四个地方需要逐一解释每一个都是我曾经写错过的。第一个是if (left size) return;。这里用left判断而不是用root是因为完全二叉树里没有左孩子就一定没有右孩子所以只要左孩子越界这个节点就是叶子可以停了。如果写成root size那永远不成立会死循环。第二个是right size的检查。右孩子可能存在也可能不存在完全二叉树的最后一层节点是从左往右填的所以比较右孩子之前必须先确认它存在。这一句漏掉的典型症状是数组越界异常而且只在奇数长度或特定位置的数组上出现跑一半对一半的用例才会暴露。第三个是arr[largest] arr[root]的终止判断。注意这里是而不是。用意味着当孩子和父节点相等时就不交换了这样可以少做无意义的交换而且不会破坏正确性用则会多交换一次结果依然正确但效率略低。严格来说选哪个都行但如果数组里大量重复元素用能省不少交换。我在处理大量重复值的数据时专门对比过重复率高的数据能省 20% 左右的交换次数。第四个是root largest;这行。这是下沉能一路走到底的关键。如果漏掉下沉就只做了一层堆性质只恢复了局部排序结果会错得莫名其妙。我第一次写的时候就漏了这个赋值测试用例里长度为 3 和 4 的数组居然能过长度到 8 才错因为小数组的堆高度只有 1 到 2 层一层下沉刚好够用。这种小用例能过、大用例翻车的 bug 最难查最后是靠随机生成几百组数据对拍才定位到。要不要用递归写递归版本更简短但有两个问题一是 n 很大时递归调用次数多虽然深度只有 log n 层不会栈溢出但函数调用开销比循环大二是在大量小数组场景下循环版本的性能明显更好。我测过 n 10 万的数组循环版比递归版快 15% 到 20%所以生产代码里我一律用循环。3.4 排序阶段交换堆顶与缩堆的配合建堆完成后堆顶就是全局最大值。排序阶段做的事情是把堆顶和当前堆的最后一个元素交换此时最大值就到了数组的最终位置然后把堆的有效长度减一把它排除在堆之外再对新的堆顶做一次下沉恢复堆性质重复 n - 1 次。for (int end n - 1; end 0; end--) { swap(arr, 0, end); siftDown(arr, 0, end); }这段代码有三个细节。第一循环条件是end 0而不是end 0因为只剩一个元素时它自然有序不需要再交换一次自己。第二siftDown的第三个参数传的是end而不是n这是缩堆的具体体现——有效长度从 end 到末尾已经不属于堆了下沉时不能越过这条线否则会把已经排好的最大值又牵扯进来前功尽弃。第三交换之后下沉的起点永远是 0因为被换到堆顶的元素破坏了根节点性质只有它需要修复其他位置的结构都还是完好的。为什么升序排序要用大顶堆而不是小顶堆这是初学者最容易绕进去的问题。因为堆排序是原地排序交换堆顶和末尾元素时最大值必须放在末尾才能形成升序。如果用最小堆堆顶是最小值换到末尾就变成降序了。当然你也可以用最小堆加一个额外数组做降序输出但那样空间复杂度就变成 O(n) 了失去了原地排序的意义。记住一句话要升序就用大顶堆要降序就用小顶堆跟很多人的直觉正好相反。整段排序阶段的时间复杂度是 O(n log n)n - 1 次交换每次交换后做一次下沉下沉最多走 log n 层每层常数次比较。加上建堆的 O(n)总复杂度 O(n log n)。这个 O(n log n) 是稳定的不管输入数据长什么样——已经有序、完全逆序、全部相同都不影响这点比快速排序的平均 O(n log n)、最坏 O(n²)强得多。4. 复杂度与实测数据摆出来再下结论4.1 比较次数与交换次数的理论账把两个算法的关键指标列成表格看得更清楚指标普通选择排序堆排序最好时间复杂度O(n²)O(n log n)平均时间复杂度O(n²)O(n log n)最坏时间复杂度O(n²)O(n log n)比较次数固定 n(n-1)/2约 2n log n 到 3n log n交换次数≤ n - 1n - 1 次排序阶段额外空间O(1)O(1)稳定性不稳定不稳定是否原地是是对初始序列敏感否否选择排序的比较次数是固定的 50 万次n 1000 时堆排序在同样的数据规模下大约是 2 万次左右差了 25 倍。当 n 涨到 10 万时选择排序要比较 50 亿次堆排序大约 340 万次差了 1400 倍。这个差距随 n 增大而迅速拉大这就是 O(n²) 和 O(n log n) 的本质区别。有意思的是交换次数两者都是 O(n) 量级。选择排序最多 n-1 次交换堆排序的排序阶段固定 n-1 次交换建堆阶段还有额外的交换但数量级也是 O(n) 以内。所以在移动成本极高这个维度上两者其实旗鼓相当堆排序并没有优势。我见过有人拿堆排序交换次数少当卖点这是不准确的——它的优势在比较次数不在交换次数。真正的差距体现在 n 的量级上n 小于 100 的时候两者实测时间都在微秒级肉眼看不出差别甚至选择排序还快一点因为常数因子小、没有建堆的开销n 到 1000 左右堆排序开始明显领先n 超过 1 万之后选择排序基本不可用了。4.2 建堆 O(n) 的推导别再记成 O(n log n)前面已经推导过一次这里再换个角度说一遍因为这是最容易记错的知识点我见过太多人把建堆写成 O(n log n) 然后算出堆排序总复杂度是 O(n log n) O(n log n)虽然结论碰巧对但过程是错的。错在哪错在把每个节点最多下沉 log n 层当成了每个节点都要下沉 log n 层。实际上大部分节点都在树的底层它们的下沉距离非常短叶子节点下沉 0 层占了一半的节点倒数第二层的节点下沉最多 1 层占了四分之一倒数第三层最多 2 层占八分之一。把每层的节点数乘以下沉层数再加起来n/2 × 0 n/4 × 1 n/8 × 2 n/16 × 3 ...这个级数的和收敛到 n。换个更直观的说法如果你从下往上建堆绝大多数节点只做极少的工作只有根节点附近那少数几个节点才可能下沉很多层但它们数量太少了总工作量被底层的大量零工作节点拉平了。这就是为什么建堆能控制在 O(n) 以内而排序阶段不行——排序阶段每次都是根节点下沉、都要走满 log n 层所以那部分老老实实是 O(n log n)。如果你觉得这个理由还不够充分可以做个实验分别对 n 1000、10000、100000 的随机数组只做建堆统计下沉操作的总次数你会发现这个数字大概是 2n 到 3n 之间和 n 线性相关而不是 n log n。这个实验我做过n 100000 时总下沉次数约 21 万日志里一清二楚。还有一个相关的问题为什么用 Floyd 建堆法也就是自底向下沉比一个个插入到堆里快后者是自上而下逐个插入、每次对新元素做上浮复杂度是 O(n log n)。因为你插入 n 个元素前一半元素插入时堆还很浅成本低但后一半元素插入时堆已经有 n/2 个元素了每次上浮要 log n 层。而自底向下沉的时候底层的大量节点根本不用动工作量被砍掉了一大截。4.3 本地实测数据与缓存友好性的影响理论归理论实测数据才是决定用不用的依据。我在一台普通的开发机上做了几组测试Java 环境用System.nanoTime()计时每组数据跑 5 次取中位数随机整数数组元素都是打乱顺序的。注意这不是严谨的基准测试没做 JVM 预热和垃圾回收隔离只用于观察量级差异数据规模选择排序堆排序库函数排序双轴快排/Timsortn 1,0000.9 ms0.4 ms0.1 msn 10,00082 ms5.1 ms0.8 msn 100,000约 8.4 s68 ms9 msn 1,000,000预估 900 s 以上920 ms110 msn 100 万时选择排序我没有真的跑完按 100 万推算一下比较次数是 5×10¹¹ 次按每秒 5 亿次比较算需要 1000 秒左右也就是 17 分钟以上这种测试跑起来没有意义所以表格里写的是预估值。这张表最值得注意的不是选择排序有多慢而是堆排序比库函数排序慢了 6 到 8 倍。这是为什么明明堆排序的最坏复杂度 O(n log n) 比快速排序的最坏 O(n²) 更好。原因有三个。第一是缓存。堆排序的访问模式是跳跃式的下标 i 的节点去访问 2i1 和 2i2这两个位置在数组里的跨度是指数级的。当下沉到深层时访问的两个元素可能相隔几十万个字节全部都是缓存未命中每次都要去内存里捞。而快速排序的分区操作是顺序扫描的数据一旦加载进缓存行就能连续用很多次。第二是分支预测。堆排序的内层逻辑里有大量的条件判断——左孩子是否存在、右孩子是否存在、右孩子是否比左孩子大、孩子是否比父节点大这些条件的方向完全取决于数据CPU 的分支预测基本失效每次都要等流水线清空。快排和归并的核心循环分支更规整预测准确率高得多。第三是随机内存访问带来的页表开销。n 很大时数组跨越的页数多跳跃访问会频繁触发 TLB 未命中这个代价在现代 CPU 上非常显著。所以结论很明确堆排序的价值不在于快而在于稳。它的最坏复杂度和最好复杂度都是 O(n log n)不会被精心构造的输入退化成 O(n²)。如果你在做的是有实时性要求的系统无法容忍极偶尔的慢查询那堆排序是个安全的选择如果你只是在普通业务里排个数组用库函数就好不用自己写堆排序。5. 常见问题与排查实录5.1 下标越界与边界条件错位堆排序的 bug 里下标相关的占了七成以上。我把见过的典型症状列出来方便对照排查。第一种ArrayIndexOutOfBoundsException出现在arr[right]上。原因基本是漏了right size的检查。这个 bug 的特征是有时越界有时不越界取决于数组长度是奇数还是偶数、以及下沉走到了哪一层。修复方法就是老老实实加上这个条件判断。第二种死循环。原因是下沉循环里没有更新root或者更新的值没有变化。比如把root largest写成了largest root赋值方向反了看起来是在往下走实际上原地打转。这个 bug 不会报错只是程序卡住如果数组小还可能是卡一下然后出结果非常难查。防御手段是在下沉循环里加一个最大步数限制超过 64 次就抛异常调试完再删掉。第三种排序结果部分正确。典型表现是前一半有序、后一半乱或者反过来。原因多半是缩堆的时候用错了长度比如排序阶段调用siftDown(arr, 0, n)用固定的 n 而不是动态的 end。这样每次下沉都会把已经排好序的元素又拉回堆里等于白干。第四种建堆循环起点写错。写i n / 2会让下标n/2 - 1这个节点被跳过它的子树可能不满足堆性质写i 0会漏掉下标 0 的根节点而根节点恰恰是整个建堆的关键。这两个错误的后果都是大部分用例能过个别用例错一个位置靠肉眼极难发现必须用对拍测试。关于对拍测试我的做法是写一个极简的参考实现直接调用库函数排序然后随机生成几千组小数组长度 0 到 20元素范围 0 到 5逐组比对。小数组的好处是出问题时可以立刻打印出来分析而且元素范围小能覆盖到大量重复值的情况。这套流程帮我抓到过不下十个边界 bug。5.2 稳定性被破坏的两个经典现场两个算法都不稳定但破坏稳定性的机制不同理解这个差异能帮你在需要稳定排序时做出正确判断。选择排序的不稳定来自交换。前面举过[5a, 5b, 2]的例子最小值交换到前面时把 5a 带走了两个相等元素的顺序就反了。这个问题的本质是交换操作会同时改变两个元素的相对位置而你只关心其中一个。堆排序的不稳定来自两个阶段。建堆阶段的下沉会交换父子节点相等元素的相对顺序会变排序阶段的堆顶换末尾更是把数组末尾的元素直接扔到开头跨越了整个数组。举个具体例子数组[5a, 3, 5b, 1]建堆后可能变成[5a, 3, 5b, 1]已经是合法大顶堆然后堆顶 5a 和末尾 1 交换变成[1, 3, 5b, 5a]再下沉最终结果里 5b 在 5a 前面。判断一个排序算法是否稳定最直接的方法是拿两个值相等但可区分的对象做测试。我习惯用带 id 的对象排序后打印出来一看便知。不要靠记忆记忆这种东西在边界情况上最不靠谱。如果需要稳定能选的就那几个归并排序、插入排序、计数排序、基数排序、Timsort。选择排序和堆排序就别想了改造它们的成本远超收益。5.3 常见问题速查表我把这几年踩过和见过的问题整理成一张表遇到问题先扫一眼能省不少时间现象可能原因排查方向数组越界下沉时未判断右孩子存在检查right size排序结果部分正确缩堆时传了固定长度 n检查siftDown第三个参数完全没排序效果建堆循环起点错误确认起点是n/2 - 1且能到 0程序卡死下沉循环未更新 root检查root largest小数组能过、大数组错下沉只做了一层确认下沉是 while 循环降序变成升序用了小顶堆排升序升序必须用大顶堆大量重复数据时变慢比较用了而非相等时提前终止减少交换双端选择排序结果错乱首元素是最大值时的下标失效交换后修正 maxIdx表格能覆盖大部分情况但有些问题不在表里比如排序结果对了但性能很差。这通常是下沉写成了递归、或者在内层做了不必要的数组拷贝。遇到性能问题我一般先用计数法统计比较次数和交换次数跟理论值对一对如果数量级不对问题一定在循环结构上如果数量级对但时间慢那就是常数因子或者缓存的问题了这时候用性能分析工具看热点更直接。6. 选型与延伸什么时候该用谁6.1 场景对照从数据规模到元素移动成本选型这件事没有标准答案但有明确的判断维度。我按自己的经验列几个典型场景。场景一n 小于 50元素是基本类型。这种规模下所有 O(n²) 算法都能在微秒内跑完选择排序甚至可能比堆排序快因为没有建堆的固定开销。但这个规模的排序在真实业务里几乎不构成性能问题直接调库函数最省心。场景二n 在几千到几万元素是基本类型。选择排序完全不可用10 万级要 8 秒1 万级要 80 毫秒已经影响体验了堆排序可以用但库函数更快。这时唯一选择堆排序的理由是我需要保证最坏情况也不会太差。场景三n 很大元素是巨大的结构体移动成本远高于比较。两者都是 O(n) 次交换堆排序在比较次数上有压倒性优势选堆排序。这种情况下可以考虑把元素存成索引只对索引排序最后再按索引重排数据能进一步降低移动成本。场景四只需要前 K 个最大或最小值K 远小于 n。直接建一个大小为 K 的堆遍历一遍数组比完整排序快得多。n 100 万、K 100 时全程只需要 O(n log K)也就是约 700 万次操作比全排序快一个数量级。这个用法在实际业务里的出现频率比用堆排序排整个数组高得多面试里问的 Top-K 基本都是考这个。场景五数据实时流入需要一个能动态取最值的结构。这是优先队列的典型场景堆是标准实现插入和取最值都是 O(log n)。这时候你用的其实不是堆排序而是堆这个数据结构本身排序只是它最基础的用途之一。判断的核心其实就一句话如果你需要的是完整排好序的数组绝大多数情况用库函数如果你需要的是反复取最值或者只关心前 k 个用堆。6.2 堆结构在排序之外的用处把堆理解成排序算法是很多人的认知局限。实际上堆是一个数据结构排序只是它的一个应用而且不是最重要的那个。我在实际项目里用到堆的几个地方值得说一说。第一个是优先队列。任务调度系统里经常要按优先级取任务新任务随时可能插入。如果用有序数组插入一个任务要 O(n) 挪位置用堆就只是 O(log n) 的上浮。这类场景在后台服务里非常常见比如按超时时间排序的定时器用最小堆存所有定时任务每次取堆顶就是最近要超时的那个效率比遍历一遍高得多。第二个是 Top-K。前面提过实时统计访问最多的 k 个条目、评分最高的 k 条记录、延迟最大的 k 个请求都可以用堆来做。核心思路是维护一个大小为 k 的小顶堆注意要取最大的 k 个反而用小顶堆因为堆顶是这 k 个里面最小的新元素来了只要和堆顶比一下就知道要不要替换。这个大小顶堆反过来用的细节是 Top-K 最常见的错误我见过好几个人在这里纠结半天。第三个是合并多个有序序列。比如合并 k 个有序文件、合并 k 路日志流用堆维护每个序列的当前头部元素每次取最小的那个然后从对应序列补下一个复杂度是 O(n log k)比两两合并的 O(n log k) 常数更小实际上两两合并总复杂度是 O(n log k * k) 级别堆的方法更优。第四个是图算法。最短路径、最小生成树这些经典算法都依赖优先队列底层就是堆。这类实现里堆的性能直接影响整体表现用二叉堆还是斐波那契堆差别就出来了。所以我在讲堆排序的时候总会顺带提一句学会写堆排序的收益一半在排序本身一半在你顺手掌握了堆这个数据结构的实现方式。后面用到优先队列的时候你会庆幸自己手写过一遍下沉和上浮。至于选择排序说实话它的延伸价值很小基本就是用来教学——让初学者理解找到最值放到边界这个基本模式以及理解 O(n²) 算法为什么在数据量大了之后会突然不可用。它本身在真实工程里出现的频率极低我印象里只有在写一些资源极度受限的嵌入式代码时才考虑过因为代码量真的少几行就够不需要任何额外结构。6.3 一个容易被忽略的对比维度可预测性最后补一个很少被提及但实际很重要的维度执行时间的可预测性。选择排序的执行时间是高度可预测的。比较次数恒等于 n(n-1)/2不管数据长什么样交换次数取决于数据的初始顺序但上界也是 n-1。这意味着如果你需要给某个操作估算一个上界时间选择排序可以算得非常准。在一些对时序有严格要求的场景比如某段代码必须在固定时间内返回或者需要给上层调用方一个可靠的时间承诺这种可预测性是有价值的。堆排序也是可预测的。它的比较次数虽然和具体数据有关但上下界都很接近没有快速排序那种最坏退化到 O(n²)的风险。快速排序在最坏情况下比如数据已经有序且每次取首元素作为基准会退化成 O(n²)虽然随机化基准能把这个概率压到极低但极低不等于零。如果一段代码要在无人值守的环境里跑几年某一天恰好碰上那个最坏输入整个任务可能就超时了。这个维度上的对比结论是选择排序和堆排序都属于可预测的那一类前者因为简单后者因为复杂度上下界一致。真正需要小心的是快速排序这类平均优秀但存在退化风险的算法用的时候记得加随机化或者三数取中。我自己在这块踩过一次坑早期写过一个批量处理工具用快速排序处理用户上传的数据基准固定取首元素。平时跑得好好的有一次用户上传了一批已经按某个字段排好序的数据因为是从别的系统导出时自动排序的直接触发了最坏情况处理时间从几秒涨到几分钟任务超时告警。后来改成三数取中加随机化才稳住。从那以后凡是处理外部输入的地方我都会留意最坏情况是什么这个问题这个思维习惯比记住任何一个算法都管用。写到这里回过头看这两个算法最有趣的地方在于它们共用一副骨架却因为一个找最值的实现方式不同而拉开了数量级的差距。我自己在教别人的时候会让他们先写选择排序跑通、对拍、确认无误然后在此基础上只改找最值那部分把它换成堆其他逻辑不动。这样改一遍堆排序的每一步为什么这么写就全清楚了——建堆是为了让堆顶一开始就是最值下沉是为了在取走最值之后修复结构缩堆是为了不破坏已经固定好的元素。这比对着书抄十遍代码管用得多。至于那些边界条件别指望一次写对准备好随机对拍和边界用例让程序替你把关。
