排序算法写到第二章选择排序这个题目其实挺尴尬——几乎所有教材都会讲它但真到工程里手写它的人少得可怜。我最早也把它当成教科书里的过客直到有一次碰到写操作代价特别高的场景才回过头认真读了一遍它的交换次数特性。更有意思的是选择排序和堆排序根本就是同一条思路的两端前者用线性扫描在当前区间里找最值后者用堆这种结构把找最值的代价从 O(n) 压到 O(log n)。把这两个东西放在一起讲比单独讲任何一个都清楚因为你能够看到同一个动机在不同数据结构上开出的两朵花。这篇内容适合刚学完冒泡、想搞清楚为什么还需要堆的朋友也适合写了两年代码但一直靠语言内置排序函数、没细想过底层差异的开发者。我会把代码、手算推演、实测数据和踩过的坑都摆出来跟着敲一遍基本就能吃透。1. 选择这个动作本身值得单独拆一章1.1 一次交换引出的核心假设选择排序的原始想法非常朴素既然最终要的是有序序列那我每一轮就确定一个位置的最终归属。第一轮在[0, n-1]里找出最小的元素放到下标 0第二轮在[1, n-1]里找最小放到下标 1一直做到只剩最后一个元素它自然就是最大的不需要再处理。这个过程的本质是把排序这个大问题拆成了 n 次求区间最小值的小问题。这里藏着一个很关键的假设求区间最小值必须扫一遍整个区间。这个假设在无序数组上是对的没有额外信息你确实没法跳过任何一个元素。但正是这个假设决定了普通选择排序的天花板——每轮 O(n) 的查找乘以 n 轮就是雷打不动的 O(n²)。后面堆排序要做的所有事情本质上就是想办法打破这个假设如果我提前维护好一种结构让取最小值和删除最小值都变成 O(log n)那整体就降到 O(n log n) 了。所以我在给新人讲这段的时候习惯先不讲代码先问一句你觉得选择排序慢在哪一行大部分人会说双重循环嘛这个回答等于没说。真正慢的地方是内层那次线性扫描——它每一轮都在重复做大量已经做过的工作。比如第一轮扫完你其实已经知道第二小的元素大概在什么范围但选择排序把这个信息全扔了第二轮从头再扫一遍。堆排序不扔它把比较的结果沉淀到树形结构里这就是两者最根本的分野。1.2 比较次数恒定这件事比想象中重要普通选择排序有一个非常特殊的性质比较次数与输入数据的初始状态完全无关永远是 n(n-1)/2 次。不管你给我一个已经排好的数组、一个逆序数组还是一个随机数组比较次数一模一样一次不多一次不少。这一点跟冒泡、插入这些能提前退出的算法有本质区别——冒泡在已经有序的数组上只需要一轮扫描就能发现没有交换直接结束插入排序在近乎有序的数据上几乎退化成 O(n)。这个性质听起来像缺点你没法利用数据的有序性加速但在某些场景下反而是优点执行时间是确定的、可预测的。如果这段排序跑在一个对时间抖动敏感的流程里比如某个硬实时的采样处理环节你最怕的就是平时 3 毫秒偶尔 30 毫秒。选择排序虽然没有快的时候但它也没有慢的时候最坏和最好一致。这个特性在一般业务开发里几乎用不上但在嵌入式、驱动、以及一些对确定性有要求的批处理里是能拿出来说事的。与之配套的另一个数字是交换次数最多 n-1 次最少 0 次。每一轮最多交换一次如果最小值本来就在位置上那就一次都不换。对比冒泡排序冒泡在最坏情况下的交换次数是 n(n-1)/2 量级两者差了整整一个数量级。这就是我在开头提到的那个写操作代价高的场景——当一次写入的成本远高于一次读取时典型如某些存储介质、某些只能整块刷新的硬件寄存器交换次数少是实打实的优势。1.3 三个特别容易写错的地方写选择排序的代码短但错法五花八门。我总结下来最高频的是这三个第一内层循环的起点。写成for j in range(i, n)其实不会错但多做了一次自己跟自己比较属于无害的浪费写成range(i1, n)更干净。可有人会写成range(0, n)那就变成每轮都在全数组里找最小值然后把找到的最小值往前搬逻辑上看起来能跑实际上会把已经排好的前缀打乱。第二交换的时机。正确做法是内层循环只记录下标循环结束后再统一交换一次。我见过有人在内层循环里一发现更小的就立刻交换那样每轮可能交换很多次交换次数直接退化到 O(n²)选择排序最大的优势瞬间消失。第三边界轮数。外层只需要跑 n-1 轮第 n 轮剩下的那个元素必然是最大的。跑满 n 轮不会出错但最后一轮是纯粹的空转。另外当 n ≤ 1 时range(n-1)在各种语言里的表现要留意Python 里range(0)是空迭代安全C 里如果写成for (int i 0; i n - 1; i)且 n 是无符号类型n0 时n-1会回绕成一个巨大的数直接越界崩溃。提示凡是涉及n - 1作为循环上界的代码只要 n 有可能小于 1就要单独判一次边界不要指望循环条件帮你兜住。2. 把普通选择排序写扎实从基础版到双向版2.1 一份可以直接拿去用的基础实现先上代码Python 版本逻辑最直白def selection_sort(a): n len(a) for i in range(n - 1): min_idx i for j in range(i 1, n): if a[j] a[min_idx]: min_idx j if min_idx ! i: a[i], a[min_idx] a[min_idx], a[i] return a这段代码里有两个细节值得单独说。min_idx初始化为i而不是某个哨兵值是为了保证即使内层循环一次都没更新交换判断也能正确工作if min_idx ! i这个判断看起来多余但它省掉的是自己跟自己交换这种无意义操作在 Python 里a[i], a[i] a[i], a[i]会走完整的元组打包解包流程虽然不是性能瓶颈但语义上表明这个位置已经就位读代码的人一眼能看懂。如果要改成 C 或者 Java注意比较函数和交换函数别写成外部调用在没有内联优化的情况下函数调用开销会把内层循环拖慢好几倍。我自己第一次用 C 写的时候就是因为把swap写成了独立函数跑出来比预期慢了一大截后来改成宏或者直接内联写三行赋值速度立刻恢复正常。2.2 双向选择一次扫描定两个位置普通选择排序每轮只确定一个位置有点浪费——既然已经扫了一遍区间顺手把最大值也记下来一次就能定两个位置。这就是双向选择排序有人叫鸡尾酒选择排序def selection_sort_bidir(a): n len(a) left, right 0, n - 1 while left right: min_idx, max_idx left, right for j in range(left, right 1): if a[j] a[min_idx]: min_idx j if a[j] a[max_idx]: max_idx j a[left], a[min_idx] a[min_idx], a[left] # 关键如果最大值原本在 left 位置交换后它已经被挪到 min_idx if max_idx left: max_idx min_idx a[right], a[max_idx] a[max_idx], a[right] left 1 right - 1 return a这段代码里那个if max_idx left的修正是我见过最多人漏掉的一行。原因很直观假设最大值正好在下标left上你先做了一次a[left]和a[min_idx]的交换最大值就被搬到了min_idx的位置此时再拿max_idx还指向left去跟right交换换过去的是最小值而不是最大值结果整个数组乱套。这种 bug 的可怕之处在于它不是每次都触发只在特定排列下出错小数据量测试很容易漏过去。双向版本的理论比较次数是n²/4量级比单向往少了一半左右因为外层只跑 n/2 轮。但实际收益没那么大内层循环里每次迭代要做两次比较而不是一次分支预测的压力也更大。我在随机数组上实测过n2000 时双向版本大概快 20% 到 30%远没有理论上的两倍。所以这属于知道有这么回事就行别指望它是银弹的优化。2.3 小数组实测数据与真实感受我手上这台日常开发机跑了一组简单的计时Python 实现随机整数数组每组重复三次取中位数量级参考即可数据规模普通选择排序双向选择排序堆排序n 1000约 0.042 s约 0.031 s约 0.004 sn 5000约 1.05 s约 0.78 s约 0.025 sn 10000约 4.2 s约 3.1 s约 0.055 sn 20000约 17 s约 12.4 s约 0.12 s看这张表能明显感受到 O(n²) 和 O(n log n) 的差距在扩大n 翻倍时选择排序的耗时翻了四倍堆排序只翻了一倍多。n10000 是个分水岭这时候选择排序已经需要肉眼可见的等待而堆排序还在眨眼就完的范围内。不过我更想强调一个容易被忽略的结论n 小于 30 左右的时候选择排序和堆排序的差距小到没意义。这时候循环本身的开销、函数调用、语言解释器的固定成本才是主导因素。有些标准库的排序实现里会对小数组切到插入排序其实选择排序在小数组上也不是不能用只是插入排序在近乎有序的数据上更占便宜综合下来更划算。3. 堆排序不是凭空冒出来的从线性找最值推演到树形找最值3.1 瓶颈那一行的替代方案回到第 1 节的那个问题选择排序慢在内层那次从头扫一遍找最小值。有没有一种数据结构能让我在 O(log n) 的时间里拿到最小值同时删除最小值也只要 O(log n)有堆。堆的直觉其实来自一个很生活化的观察。假设你要在一堆人里反复挑出最矮的那个最笨的办法是每次都重新排队数一遍。但如果这些人按身高排成一棵树每个节点都比自己的孩子矮那么最矮的人必然在树根拿走之后只需要把最底下的人提到根上然后让他沿着更矮的孩子往下挪挪几步就重新满足条件了。这个往下挪的过程走的路径长度就是树的高度也就是 log₂n 左右。一千万个元素树高也就 23 层几次比较的事。这就是堆排序相对于选择排序的全部秘密用空间上的组织换时间上的查找。而且它是原地组织不需要额外数组所有结构信息都藏在元素的相对位置上这也是它比建一棵正经二叉搜索树再中序遍历省内存的地方。3.2 完全二叉树用数组存索引关系必须背下来堆在逻辑上是一棵完全二叉树物理上就是一个数组。完全二叉树的定义可以简单理解为除了最后一层上面每一层都是满的最后一层从左往右连续填。这个性质保证了它能被紧凑地映射进数组一点空隙都没有。映射规则就是三条我在白板上给学生画过无数遍下标为i的节点左孩子在下标2i 1右孩子在下标2i 20 基下标下标为i的节点i 0父节点在(i - 1) // 2最后一个非叶子节点在n // 2 - 1最容易踩的坑是拿 1 基下标的公式写 0 基代码。教材上常见的写法是左孩子 2i右孩子 2i1父节点 i/2那是假设数组从下标 1 开始、下标 0 空着不用。如果直接抄进 0 基的代码里症状是排序结果整体错位、部分元素不动非常迷惑。我自己第一次写堆的时候就在这上面卡了半小时后来养成习惯写完先拿 n4 的小数组手工验一遍索引。用 n4 验数组下标 0、1、2、3。n // 2 - 1 1所以非叶子节点是 0 和 1。节点 0 的孩子是 1 和 2节点 1 的孩子是 3。最后一个节点 3 是节点 1 的左孩子没错。这个手算步骤只要二十秒能省掉大量调试时间。3.3 下沉操作整个堆排序里唯一需要动脑的地方堆排里所有操作最终都归结为一个动作下沉sift down。给定一个节点如果它有孩子比它大大顶堆语境就跟最大的那个孩子交换然后继续在交换后的位置上重复直到没有孩子比它大或者已经到叶子了。拿一个具体数组推演一遍[4, 6, 8, 5, 7, 9, 1]n7从最后一个非叶节点7//2 - 1 2开始往前处理。i2值 8孩子是下标 5 的 9 和下标 6 的 1最大是 9交换 →[4, 6, 9, 5, 7, 8, 1]。8 挪到下标 5它没有孩子停。i1值 6孩子是下标 3 的 5 和下标 4 的 7最大是 7交换 →[4, 7, 9, 5, 6, 8, 1]。6 挪到下标 4没有孩子停。i0值 4孩子是下标 1 的 7 和下标 2 的 9最大是 9交换 →[9, 7, 4, 5, 6, 8, 1]。4 挪到下标 2它有孩子下标 5 的 8 和下标 6 的 1最大是 8交换 →[9, 7, 8, 5, 6, 4, 1]。4 挪到下标 5没有孩子停。最终[9, 7, 8, 5, 6, 4, 1]。验一遍0 的孩子 7 和 8都小于 9 ✓1 的孩子 5 和 6都小于 7 ✓2 的孩子 4 和 1都小于 8 ✓。堆成立。这段推演我建议每个学堆的人都老老实实在纸上走一遍比看十遍代码有用。走完之后你对为什么下沉只需要沿着一条路径走这件事会有肌肉记忆——因为交换只发生在当前节点和它的某个孩子之间另一棵子树根本没有被触碰它的堆性质天然还成立。4. 堆排序的两段式结构建堆与排序阶段4.1 自底向上建堆为什么是 O(n) 而不是 O(n log n)很多人第一次看到建堆代码会觉得循环里套了一个下沉下沉是 log n那建堆不就是 O(n log n) 吗这是最典型的误判。真相是自底向上建堆是 O(n)推导过程值得写清楚因为面试和实际判断复杂度的时候经常用到。设堆的高度为 h log₂n。第 k 层从叶子往上数叶子层 k0有大约 n/2^(k1) 个节点每个节点下沉最多走 k 步。总代价是各层代价之和S Σ (n / 2^(k1)) · k, k 0 到 log₂n (n/2) · Σ k / 2^k而Σ k/2^k从 k0 到无穷的极限是 2。所以 S ≤ (n/2) · 2 n。总代价是线性量级。直觉上的解释更重要绝大多数节点都在底层而底层节点的下沉代价几乎为零。n 个节点里有一半是叶子它们一步都不用走四分之一在倒数第二层最多走一步。真正走满 log n 步的只有根节点一个。所以整体代价被大量便宜的节点摊平了。这和n 个节点每个都走 log n 步是完全不同的分布。这个结论有个直接推论建堆比排序阶段便宜得多。堆排序总耗时里排序阶段占大头。所以如果你只是需要一个优先队列、并不要求完全有序建完堆就可以收工成本是线性的。4.2 排序阶段换尾、缩域、再下沉建好大顶堆之后堆顶就是全局最大值。排序阶段的套路是固定的三步循环把堆顶a[0]和当前堆的最后一个元素a[end]交换最大值就此落到了它的最终位置堆的有效范围缩小 1end - 1刚放到末尾的元素不再参与后续操作对新的堆顶执行一次下沉恢复堆性质这个过程从end n-1一路走到end 1每轮确定一个元素总共 n-1 轮每轮下沉 O(log n)所以排序阶段是 O(n log n)。我在前面那个[9, 7, 8, 5, 6, 4, 1]上接着走两轮第一轮交换 a[0] 和 a[6] →[1, 7, 8, 5, 6, 4, 9]有效范围变成前 6 个。对下标 0 下沉孩子是 7 和 8最大是 8交换 →[8, 7, 1, 5, 6, 4, 9]1 落到下标 2它的孩子只有下标 5 的 4下标 6 已经超出有效范围4 1交换 →[8, 7, 4, 5, 6, 1, 9]1 到叶子停。第二轮交换 a[0] 和 a[5] →[1, 7, 4, 5, 6, 8, 9]有效范围前 5 个。下沉孩子是 7 和 4最大 7交换 →[7, 1, 4, 5, 6, 8, 9]1 到下标 1孩子是 5 和 6最大 6交换 →[7, 6, 4, 5, 1, 8, 9]1 到下标 4无孩子停。可以看到每轮都把一个元素钉死在末尾末尾的有序区从右往左稳定增长。这也是堆排序不需要额外空间的原因——有序区就利用数组尾部原地生长。4.3 完整代码以及为什么要在参数里传 sizedef sift_down(a, i, size): while True: left 2 * i 1 right left 1 largest i if left size and a[left] a[largest]: largest left if right size and a[right] a[largest]: largest right if largest i: return a[i], a[largest] a[largest], a[i] i largest def heap_sort(a): n len(a) for i in range(n // 2 - 1, -1, -1): sift_down(a, i, n) for end in range(n - 1, 0, -1): a[0], a[end] a[end], a[0] sift_down(a, 0, end) return asift_down必须接收size参数这是堆排序实现里最容易被简化掉、也最不能简化的一环。如果不传 size、直接用len(a)判断孩子是否存在那么排序阶段下沉时会把已经排好序的尾部元素又拖回堆里症状是数组末尾的几个元素反复变化跑完结果不对。我调试过这个 bug第一次看的时候完全懵——明明建堆是对的为什么排出来乱序打印每轮的下沉过程才发现问题。用迭代而不用递归也是刻意的选择。递归版本写起来更短但每层下沉都要压一次栈帧n 大时虽然深度只有 log n不至于爆栈但函数调用开销在 Python 里相当可观。改成while True加手动更新i之后我这边测下来大概能快 15% 左右。C 语言里用循环更是必须的编译器不一定能帮你把尾递归优化掉。5. 两者的横向对比别只看大 O5.1 比较次数和交换次数的真实账本大 O 只能告诉你增长趋势不能告诉你同一个量级下的实际差异。我把几个关键指标列一下以 n 为规模指标普通选择排序堆排序时间复杂度最好/最坏/平均全部 O(n²)全部 O(n log n)比较次数恒为 n(n-1)/2约 2n log₂n 量级交换次数最多 n-1最少 0建堆阶段约 n/2排序阶段 n-1额外空间O(1)O(1)稳定性不稳定不稳定对初始顺序的敏感度完全不敏感基本不敏感是否原地是是拿 n1000 具体算一下。选择排序比较次数固定 499500 次堆排序建堆阶段比较次数不超过 2n2000 次排序阶段每轮下沉平均走 log₂1000 ≈ 10 层、每层最多两次比较总计约 2×1000×10 20000 次实际会少一些因为大部分下沉走不到底。两者相差 20 倍以上。这个倍数就是 O(n²) 和 O(n log n) 在 n1000 这个具体点上的具象值比空谈复杂度有说服力得多。交换次数上选择排序反而占优——它最多 n-1 次堆排序光排序阶段就要 n-1 次加上建堆的交换总量是选择排序的三到四倍。在写操作极贵的场景下这个差异是能实测出来的。5.2 缓存友好性纸面赢家未必跑得快这一条是我觉得最有意思的部分。理论上堆排序完胜但你要是拿它跟快速排序比会发现堆排序经常跑不过快排甚至有时候只比归并快一点原因不在复杂度在内存访问模式。选择排序的内层循环是从头到尾顺序扫一遍这是对 CPU 缓存最友好的访问方式——预取器能准确预测下一个地址数据一条一条被拉进缓存行几乎不浪费。堆排序则完全相反下沉时从下标 i 跳到 2i1再跳到 4i3跳的步长随层数指数增长每次跳跃大概率落在不同的缓存行上。n 大了以后堆顶附近的访问基本全是缓存不命中而 CPU 等一次内存的时间能执行上百条指令。所以你会看到一个有点反直觉的现象在小规模数据上选择排序的实际耗时可能接近甚至优于堆排序尽管复杂度差一个量级。因为这时候数据全在 L1/L2 缓存里跳转的代价还没显现出来而堆排序的常数因子每次下沉两次比较、一次交换反而更重。我在 n16 到 n32 这个区间实测过Python 下两者经常打成平手有时候选择排序还快一点。当然这跟解释器开销关系很大换成 C 语言测试交叉点大概在 n40 到 n60 之间。提示判断一个排序算法实际快不快永远不能只看复杂度。数据规模、缓存层级、元素类型值类型还是引用类型、语言的运行时特性都会改变结论。实测是最低成本的确权方式。5.3 什么情况下我会选它俩选择排序真正说得上话的场景元素数量很小几十个以内而且代码里不想引入额外依赖手写一个十行版本最省事交换或写入的代价远远高于比较比如写的是某种只能整块更新的硬件状态或者写日志、写网络包的场景需要一个运行时间高度确定的排序不允许出现意外的长尾延迟教学和面试场景用来对比说明为什么数据结构能改变复杂度堆排序真正说得上话的场景内存极度受限、不允许递归、不允许额外分配缓冲区但又需要 O(n log n)。堆排序是原地 O(n log n) 里最省心的一个需要最坏情况也有保证的 O(n log n)。快速排序虽然有随机化版本但理论上仍存在退化可能而堆排序的最好最坏平均都是 O(n log n)只需要前 k 个最值。这时候根本不用全排维护一个大小为 k 的堆即可复杂度 O(n log k)当 k 远小于 n 时非常划算。这个技巧在从海量数据里挑最大的 100 个找数据流的中位数这类问题上用得极多需要优先队列语义的地方。定时器调度、任务排队、图算法里的最短路、合并多个有序序列背后都是堆顺便说一句关于稳定性的注意事项两者都是不稳定的也就是相等元素的相对顺序在排序后可能改变。选择排序不稳定的原因很直接——它把最小值直接甩到前面去中间那些和最小值相等的元素就被跨越了。堆排序不稳定的原因在排序阶段堆顶元素被换到末尾这一下跨越大半个数组必然打乱相等元素的相对次序。如果业务上要求保持原有顺序比如先按时间排好、再按优先级稳定排序这两个都不能用得用归并排序或者给每个元素加上原始下标做二次比较。举个堆排序不稳定的具体例子数组[3a, 3b, 1]a、b 用来标记两个相等元素 3 的原始顺序。建堆后是[3a, 3b, 1]已满足大顶堆。排序阶段第一轮交换 a[0] 和 a[2] →[1, 3b, 3a]有效范围前两个下沉 1 时跟 3b 交换 →[3b, 1, 3a]。第二轮交换 a[0] 和 a[1] →[1, 3b, 3a]。结果两个 3 的顺序变成了 b 在前 a 在后原顺序被破坏了。这个例子只有三个元素特别好记。6. 几个真实的排查过程以及我踩过之后改掉的习惯6.1 排序结果部分正确九成是 size 参数没管住那是我第一次写堆排序建堆阶段验证过没问题但整体排完总是后段几个元素不对。当时的排查顺序记一下这个链路对类似问题都适用第一步单独测建堆函数。用[4, 6, 8, 5, 7, 9, 1]跑一遍对比手算结果[9, 7, 8, 5, 6, 4, 1]一致说明建堆逻辑没问题问题在排序阶段。第二步打印每一轮交换和下沉之后的数组。第一轮正常第二轮正常到某一轮突然发现有个本该冻结在末尾的元素又动了。这就锁定了方向有效范围没有正确收缩。第三步回看sift_down。果然孩子是否存在的判断用的是2*i1 len(a)而不是 size。已排序的尾部被当成了堆的一部分刚钉好的元素被重新卷进来比较于是又被换走了。改成传 size 之后立刻正确。排查这类问题的方法论很简单分段验证。堆排序天然分成两个阶段先把第一阶段验证干净再专心查第二阶段不要一上来就盯着全流程。另外强烈建议写一个堆性质校验函数随时能插进代码里检查def is_heap(a, size): for i in range(size // 2): left, right 2 * i 1, 2 * i 2 if left size and a[left] a[i]: return False if right size and a[right] a[i]: return False return True建堆后assert is_heap(a, n)每轮下沉后assert is_heap(a, end)。这两个断言一旦加上上面那个 bug 十秒内就会暴露。我在任何需要写堆的场合都会先把这个函数贴进去省下的调试时间远超写它的成本。6.2 把建堆写成自顶向下之后性能掉了一截还有一个坑是我自己聪明过头踩的。当时想着既然插入元素是往堆尾加再上浮那建堆也可以从空堆开始一个个把元素插进去调用上浮——逻辑上完全正确出来的也是合法堆。跑出来的结果没错但速度明显慢。原因在于自顶向下建堆的复杂度是 O(n log n) 而不是 O(n)。每个新插入的元素都从叶子位置开始往上浮平均要浮 log n 层n 个元素累计就是 n log n。而自底向上建堆里绝大多数节点只需要下沉零到一步。n10000 的时候两者的操作次数差好几倍实测下来建堆耗时差了三倍左右。这个教训我记到现在看起来等价的写法复杂度可能差一个量级。所以每次写堆相关代码建堆一定用for i in range(n // 2 - 1, -1, -1)这个自底向上的形式不用犹豫。6.3 索引公式混用手工验算比调试快十倍第三个坑是 1 基和 0 基公式混用前面提过一次这里展开说说排查手法。症状通常很怪能排出一部分但整体不是有序的而且元素看起来没有丢失只是位置错乱。这时候空想是没有用的我的做法是拿 n4 或 n5 的最小数组在纸上画出树形和数组下标的对应关系然后逐行对比代码里的索引计算公式。具体验算清单就三条下标 0 的左右孩子是不是 1 和 2下标 1 的孩子是不是 3 和 4n≥5 时最后一个非叶子节点是不是n//2 - 1。三条里只要有一条对不上就是公式错了。我现在的习惯是写堆代码时在注释里直接写一行# 0-based: child 2i1, 2i2; parent (i-1)//2边写边看比事后调试便宜太多。6.4 关于要不要手写的一点个人看法业务代码里手写堆排序的机会确实不多标准库基本都有性能也调得比我好。但有两类场合我坚持自己写一是需要前 k 大/前 k 小的流式处理标准排序帮不上忙必须自己维护一个大小为 k 的堆二是需要在下沉过程中插入自定义逻辑比如按某个复合 key 比较、或者下沉时顺带记录统计信息这时候把堆的骨架握在自己手里最方便。我个人的体会是堆这一块的知识真正值钱的地方不在排序本身而在优先队列这个抽象。你把下沉和上浮两个动作练熟之后会发现大量看起来不相关的问题——任务调度、合并有序链表、带权图的路径查找、数据流的中位数——底层都是同一个动作。选择排序则是理解这一切的起点它把每轮确定一个最值这个思路讲得足够裸裸到你能清楚看到瓶颈在哪里然后才有动力去找一个更好的结构来替代那一层线性扫描。这一层递进关系比记住两个算法各自的复杂度数字有用得多。
排序算法写到第二章选择排序这个题目其实挺尴尬——几乎所有教材都会讲它但真到工程里手写它的人少得可怜。我最早也把它当成教科书里的过客直到有一次碰到写操作代价特别高的场景才回过头认真读了一遍它的交换次数特性。更有意思的是选择排序和堆排序根本就是同一条思路的两端前者用线性扫描在当前区间里找最值后者用堆这种结构把找最值的代价从 O(n) 压到 O(log n)。把这两个东西放在一起讲比单独讲任何一个都清楚因为你能够看到同一个动机在不同数据结构上开出的两朵花。这篇内容适合刚学完冒泡、想搞清楚为什么还需要堆的朋友也适合写了两年代码但一直靠语言内置排序函数、没细想过底层差异的开发者。我会把代码、手算推演、实测数据和踩过的坑都摆出来跟着敲一遍基本就能吃透。1. 选择这个动作本身值得单独拆一章1.1 一次交换引出的核心假设选择排序的原始想法非常朴素既然最终要的是有序序列那我每一轮就确定一个位置的最终归属。第一轮在[0, n-1]里找出最小的元素放到下标 0第二轮在[1, n-1]里找最小放到下标 1一直做到只剩最后一个元素它自然就是最大的不需要再处理。这个过程的本质是把排序这个大问题拆成了 n 次求区间最小值的小问题。这里藏着一个很关键的假设求区间最小值必须扫一遍整个区间。这个假设在无序数组上是对的没有额外信息你确实没法跳过任何一个元素。但正是这个假设决定了普通选择排序的天花板——每轮 O(n) 的查找乘以 n 轮就是雷打不动的 O(n²)。后面堆排序要做的所有事情本质上就是想办法打破这个假设如果我提前维护好一种结构让取最小值和删除最小值都变成 O(log n)那整体就降到 O(n log n) 了。所以我在给新人讲这段的时候习惯先不讲代码先问一句你觉得选择排序慢在哪一行大部分人会说双重循环嘛这个回答等于没说。真正慢的地方是内层那次线性扫描——它每一轮都在重复做大量已经做过的工作。比如第一轮扫完你其实已经知道第二小的元素大概在什么范围但选择排序把这个信息全扔了第二轮从头再扫一遍。堆排序不扔它把比较的结果沉淀到树形结构里这就是两者最根本的分野。1.2 比较次数恒定这件事比想象中重要普通选择排序有一个非常特殊的性质比较次数与输入数据的初始状态完全无关永远是 n(n-1)/2 次。不管你给我一个已经排好的数组、一个逆序数组还是一个随机数组比较次数一模一样一次不多一次不少。这一点跟冒泡、插入这些能提前退出的算法有本质区别——冒泡在已经有序的数组上只需要一轮扫描就能发现没有交换直接结束插入排序在近乎有序的数据上几乎退化成 O(n)。这个性质听起来像缺点你没法利用数据的有序性加速但在某些场景下反而是优点执行时间是确定的、可预测的。如果这段排序跑在一个对时间抖动敏感的流程里比如某个硬实时的采样处理环节你最怕的就是平时 3 毫秒偶尔 30 毫秒。选择排序虽然没有快的时候但它也没有慢的时候最坏和最好一致。这个特性在一般业务开发里几乎用不上但在嵌入式、驱动、以及一些对确定性有要求的批处理里是能拿出来说事的。与之配套的另一个数字是交换次数最多 n-1 次最少 0 次。每一轮最多交换一次如果最小值本来就在位置上那就一次都不换。对比冒泡排序冒泡在最坏情况下的交换次数是 n(n-1)/2 量级两者差了整整一个数量级。这就是我在开头提到的那个写操作代价高的场景——当一次写入的成本远高于一次读取时典型如某些存储介质、某些只能整块刷新的硬件寄存器交换次数少是实打实的优势。1.3 三个特别容易写错的地方写选择排序的代码短但错法五花八门。我总结下来最高频的是这三个第一内层循环的起点。写成for j in range(i, n)其实不会错但多做了一次自己跟自己比较属于无害的浪费写成range(i1, n)更干净。可有人会写成range(0, n)那就变成每轮都在全数组里找最小值然后把找到的最小值往前搬逻辑上看起来能跑实际上会把已经排好的前缀打乱。第二交换的时机。正确做法是内层循环只记录下标循环结束后再统一交换一次。我见过有人在内层循环里一发现更小的就立刻交换那样每轮可能交换很多次交换次数直接退化到 O(n²)选择排序最大的优势瞬间消失。第三边界轮数。外层只需要跑 n-1 轮第 n 轮剩下的那个元素必然是最大的。跑满 n 轮不会出错但最后一轮是纯粹的空转。另外当 n ≤ 1 时range(n-1)在各种语言里的表现要留意Python 里range(0)是空迭代安全C 里如果写成for (int i 0; i n - 1; i)且 n 是无符号类型n0 时n-1会回绕成一个巨大的数直接越界崩溃。提示凡是涉及n - 1作为循环上界的代码只要 n 有可能小于 1就要单独判一次边界不要指望循环条件帮你兜住。2. 把普通选择排序写扎实从基础版到双向版2.1 一份可以直接拿去用的基础实现先上代码Python 版本逻辑最直白def selection_sort(a): n len(a) for i in range(n - 1): min_idx i for j in range(i 1, n): if a[j] a[min_idx]: min_idx j if min_idx ! i: a[i], a[min_idx] a[min_idx], a[i] return a这段代码里有两个细节值得单独说。min_idx初始化为i而不是某个哨兵值是为了保证即使内层循环一次都没更新交换判断也能正确工作if min_idx ! i这个判断看起来多余但它省掉的是自己跟自己交换这种无意义操作在 Python 里a[i], a[i] a[i], a[i]会走完整的元组打包解包流程虽然不是性能瓶颈但语义上表明这个位置已经就位读代码的人一眼能看懂。如果要改成 C 或者 Java注意比较函数和交换函数别写成外部调用在没有内联优化的情况下函数调用开销会把内层循环拖慢好几倍。我自己第一次用 C 写的时候就是因为把swap写成了独立函数跑出来比预期慢了一大截后来改成宏或者直接内联写三行赋值速度立刻恢复正常。2.2 双向选择一次扫描定两个位置普通选择排序每轮只确定一个位置有点浪费——既然已经扫了一遍区间顺手把最大值也记下来一次就能定两个位置。这就是双向选择排序有人叫鸡尾酒选择排序def selection_sort_bidir(a): n len(a) left, right 0, n - 1 while left right: min_idx, max_idx left, right for j in range(left, right 1): if a[j] a[min_idx]: min_idx j if a[j] a[max_idx]: max_idx j a[left], a[min_idx] a[min_idx], a[left] # 关键如果最大值原本在 left 位置交换后它已经被挪到 min_idx if max_idx left: max_idx min_idx a[right], a[max_idx] a[max_idx], a[right] left 1 right - 1 return a这段代码里那个if max_idx left的修正是我见过最多人漏掉的一行。原因很直观假设最大值正好在下标left上你先做了一次a[left]和a[min_idx]的交换最大值就被搬到了min_idx的位置此时再拿max_idx还指向left去跟right交换换过去的是最小值而不是最大值结果整个数组乱套。这种 bug 的可怕之处在于它不是每次都触发只在特定排列下出错小数据量测试很容易漏过去。双向版本的理论比较次数是n²/4量级比单向往少了一半左右因为外层只跑 n/2 轮。但实际收益没那么大内层循环里每次迭代要做两次比较而不是一次分支预测的压力也更大。我在随机数组上实测过n2000 时双向版本大概快 20% 到 30%远没有理论上的两倍。所以这属于知道有这么回事就行别指望它是银弹的优化。2.3 小数组实测数据与真实感受我手上这台日常开发机跑了一组简单的计时Python 实现随机整数数组每组重复三次取中位数量级参考即可数据规模普通选择排序双向选择排序堆排序n 1000约 0.042 s约 0.031 s约 0.004 sn 5000约 1.05 s约 0.78 s约 0.025 sn 10000约 4.2 s约 3.1 s约 0.055 sn 20000约 17 s约 12.4 s约 0.12 s看这张表能明显感受到 O(n²) 和 O(n log n) 的差距在扩大n 翻倍时选择排序的耗时翻了四倍堆排序只翻了一倍多。n10000 是个分水岭这时候选择排序已经需要肉眼可见的等待而堆排序还在眨眼就完的范围内。不过我更想强调一个容易被忽略的结论n 小于 30 左右的时候选择排序和堆排序的差距小到没意义。这时候循环本身的开销、函数调用、语言解释器的固定成本才是主导因素。有些标准库的排序实现里会对小数组切到插入排序其实选择排序在小数组上也不是不能用只是插入排序在近乎有序的数据上更占便宜综合下来更划算。3. 堆排序不是凭空冒出来的从线性找最值推演到树形找最值3.1 瓶颈那一行的替代方案回到第 1 节的那个问题选择排序慢在内层那次从头扫一遍找最小值。有没有一种数据结构能让我在 O(log n) 的时间里拿到最小值同时删除最小值也只要 O(log n)有堆。堆的直觉其实来自一个很生活化的观察。假设你要在一堆人里反复挑出最矮的那个最笨的办法是每次都重新排队数一遍。但如果这些人按身高排成一棵树每个节点都比自己的孩子矮那么最矮的人必然在树根拿走之后只需要把最底下的人提到根上然后让他沿着更矮的孩子往下挪挪几步就重新满足条件了。这个往下挪的过程走的路径长度就是树的高度也就是 log₂n 左右。一千万个元素树高也就 23 层几次比较的事。这就是堆排序相对于选择排序的全部秘密用空间上的组织换时间上的查找。而且它是原地组织不需要额外数组所有结构信息都藏在元素的相对位置上这也是它比建一棵正经二叉搜索树再中序遍历省内存的地方。3.2 完全二叉树用数组存索引关系必须背下来堆在逻辑上是一棵完全二叉树物理上就是一个数组。完全二叉树的定义可以简单理解为除了最后一层上面每一层都是满的最后一层从左往右连续填。这个性质保证了它能被紧凑地映射进数组一点空隙都没有。映射规则就是三条我在白板上给学生画过无数遍下标为i的节点左孩子在下标2i 1右孩子在下标2i 20 基下标下标为i的节点i 0父节点在(i - 1) // 2最后一个非叶子节点在n // 2 - 1最容易踩的坑是拿 1 基下标的公式写 0 基代码。教材上常见的写法是左孩子 2i右孩子 2i1父节点 i/2那是假设数组从下标 1 开始、下标 0 空着不用。如果直接抄进 0 基的代码里症状是排序结果整体错位、部分元素不动非常迷惑。我自己第一次写堆的时候就在这上面卡了半小时后来养成习惯写完先拿 n4 的小数组手工验一遍索引。用 n4 验数组下标 0、1、2、3。n // 2 - 1 1所以非叶子节点是 0 和 1。节点 0 的孩子是 1 和 2节点 1 的孩子是 3。最后一个节点 3 是节点 1 的左孩子没错。这个手算步骤只要二十秒能省掉大量调试时间。3.3 下沉操作整个堆排序里唯一需要动脑的地方堆排里所有操作最终都归结为一个动作下沉sift down。给定一个节点如果它有孩子比它大大顶堆语境就跟最大的那个孩子交换然后继续在交换后的位置上重复直到没有孩子比它大或者已经到叶子了。拿一个具体数组推演一遍[4, 6, 8, 5, 7, 9, 1]n7从最后一个非叶节点7//2 - 1 2开始往前处理。i2值 8孩子是下标 5 的 9 和下标 6 的 1最大是 9交换 →[4, 6, 9, 5, 7, 8, 1]。8 挪到下标 5它没有孩子停。i1值 6孩子是下标 3 的 5 和下标 4 的 7最大是 7交换 →[4, 7, 9, 5, 6, 8, 1]。6 挪到下标 4没有孩子停。i0值 4孩子是下标 1 的 7 和下标 2 的 9最大是 9交换 →[9, 7, 4, 5, 6, 8, 1]。4 挪到下标 2它有孩子下标 5 的 8 和下标 6 的 1最大是 8交换 →[9, 7, 8, 5, 6, 4, 1]。4 挪到下标 5没有孩子停。最终[9, 7, 8, 5, 6, 4, 1]。验一遍0 的孩子 7 和 8都小于 9 ✓1 的孩子 5 和 6都小于 7 ✓2 的孩子 4 和 1都小于 8 ✓。堆成立。这段推演我建议每个学堆的人都老老实实在纸上走一遍比看十遍代码有用。走完之后你对为什么下沉只需要沿着一条路径走这件事会有肌肉记忆——因为交换只发生在当前节点和它的某个孩子之间另一棵子树根本没有被触碰它的堆性质天然还成立。4. 堆排序的两段式结构建堆与排序阶段4.1 自底向上建堆为什么是 O(n) 而不是 O(n log n)很多人第一次看到建堆代码会觉得循环里套了一个下沉下沉是 log n那建堆不就是 O(n log n) 吗这是最典型的误判。真相是自底向上建堆是 O(n)推导过程值得写清楚因为面试和实际判断复杂度的时候经常用到。设堆的高度为 h log₂n。第 k 层从叶子往上数叶子层 k0有大约 n/2^(k1) 个节点每个节点下沉最多走 k 步。总代价是各层代价之和S Σ (n / 2^(k1)) · k, k 0 到 log₂n (n/2) · Σ k / 2^k而Σ k/2^k从 k0 到无穷的极限是 2。所以 S ≤ (n/2) · 2 n。总代价是线性量级。直觉上的解释更重要绝大多数节点都在底层而底层节点的下沉代价几乎为零。n 个节点里有一半是叶子它们一步都不用走四分之一在倒数第二层最多走一步。真正走满 log n 步的只有根节点一个。所以整体代价被大量便宜的节点摊平了。这和n 个节点每个都走 log n 步是完全不同的分布。这个结论有个直接推论建堆比排序阶段便宜得多。堆排序总耗时里排序阶段占大头。所以如果你只是需要一个优先队列、并不要求完全有序建完堆就可以收工成本是线性的。4.2 排序阶段换尾、缩域、再下沉建好大顶堆之后堆顶就是全局最大值。排序阶段的套路是固定的三步循环把堆顶a[0]和当前堆的最后一个元素a[end]交换最大值就此落到了它的最终位置堆的有效范围缩小 1end - 1刚放到末尾的元素不再参与后续操作对新的堆顶执行一次下沉恢复堆性质这个过程从end n-1一路走到end 1每轮确定一个元素总共 n-1 轮每轮下沉 O(log n)所以排序阶段是 O(n log n)。我在前面那个[9, 7, 8, 5, 6, 4, 1]上接着走两轮第一轮交换 a[0] 和 a[6] →[1, 7, 8, 5, 6, 4, 9]有效范围变成前 6 个。对下标 0 下沉孩子是 7 和 8最大是 8交换 →[8, 7, 1, 5, 6, 4, 9]1 落到下标 2它的孩子只有下标 5 的 4下标 6 已经超出有效范围4 1交换 →[8, 7, 4, 5, 6, 1, 9]1 到叶子停。第二轮交换 a[0] 和 a[5] →[1, 7, 4, 5, 6, 8, 9]有效范围前 5 个。下沉孩子是 7 和 4最大 7交换 →[7, 1, 4, 5, 6, 8, 9]1 到下标 1孩子是 5 和 6最大 6交换 →[7, 6, 4, 5, 1, 8, 9]1 到下标 4无孩子停。可以看到每轮都把一个元素钉死在末尾末尾的有序区从右往左稳定增长。这也是堆排序不需要额外空间的原因——有序区就利用数组尾部原地生长。4.3 完整代码以及为什么要在参数里传 sizedef sift_down(a, i, size): while True: left 2 * i 1 right left 1 largest i if left size and a[left] a[largest]: largest left if right size and a[right] a[largest]: largest right if largest i: return a[i], a[largest] a[largest], a[i] i largest def heap_sort(a): n len(a) for i in range(n // 2 - 1, -1, -1): sift_down(a, i, n) for end in range(n - 1, 0, -1): a[0], a[end] a[end], a[0] sift_down(a, 0, end) return asift_down必须接收size参数这是堆排序实现里最容易被简化掉、也最不能简化的一环。如果不传 size、直接用len(a)判断孩子是否存在那么排序阶段下沉时会把已经排好序的尾部元素又拖回堆里症状是数组末尾的几个元素反复变化跑完结果不对。我调试过这个 bug第一次看的时候完全懵——明明建堆是对的为什么排出来乱序打印每轮的下沉过程才发现问题。用迭代而不用递归也是刻意的选择。递归版本写起来更短但每层下沉都要压一次栈帧n 大时虽然深度只有 log n不至于爆栈但函数调用开销在 Python 里相当可观。改成while True加手动更新i之后我这边测下来大概能快 15% 左右。C 语言里用循环更是必须的编译器不一定能帮你把尾递归优化掉。5. 两者的横向对比别只看大 O5.1 比较次数和交换次数的真实账本大 O 只能告诉你增长趋势不能告诉你同一个量级下的实际差异。我把几个关键指标列一下以 n 为规模指标普通选择排序堆排序时间复杂度最好/最坏/平均全部 O(n²)全部 O(n log n)比较次数恒为 n(n-1)/2约 2n log₂n 量级交换次数最多 n-1最少 0建堆阶段约 n/2排序阶段 n-1额外空间O(1)O(1)稳定性不稳定不稳定对初始顺序的敏感度完全不敏感基本不敏感是否原地是是拿 n1000 具体算一下。选择排序比较次数固定 499500 次堆排序建堆阶段比较次数不超过 2n2000 次排序阶段每轮下沉平均走 log₂1000 ≈ 10 层、每层最多两次比较总计约 2×1000×10 20000 次实际会少一些因为大部分下沉走不到底。两者相差 20 倍以上。这个倍数就是 O(n²) 和 O(n log n) 在 n1000 这个具体点上的具象值比空谈复杂度有说服力得多。交换次数上选择排序反而占优——它最多 n-1 次堆排序光排序阶段就要 n-1 次加上建堆的交换总量是选择排序的三到四倍。在写操作极贵的场景下这个差异是能实测出来的。5.2 缓存友好性纸面赢家未必跑得快这一条是我觉得最有意思的部分。理论上堆排序完胜但你要是拿它跟快速排序比会发现堆排序经常跑不过快排甚至有时候只比归并快一点原因不在复杂度在内存访问模式。选择排序的内层循环是从头到尾顺序扫一遍这是对 CPU 缓存最友好的访问方式——预取器能准确预测下一个地址数据一条一条被拉进缓存行几乎不浪费。堆排序则完全相反下沉时从下标 i 跳到 2i1再跳到 4i3跳的步长随层数指数增长每次跳跃大概率落在不同的缓存行上。n 大了以后堆顶附近的访问基本全是缓存不命中而 CPU 等一次内存的时间能执行上百条指令。所以你会看到一个有点反直觉的现象在小规模数据上选择排序的实际耗时可能接近甚至优于堆排序尽管复杂度差一个量级。因为这时候数据全在 L1/L2 缓存里跳转的代价还没显现出来而堆排序的常数因子每次下沉两次比较、一次交换反而更重。我在 n16 到 n32 这个区间实测过Python 下两者经常打成平手有时候选择排序还快一点。当然这跟解释器开销关系很大换成 C 语言测试交叉点大概在 n40 到 n60 之间。提示判断一个排序算法实际快不快永远不能只看复杂度。数据规模、缓存层级、元素类型值类型还是引用类型、语言的运行时特性都会改变结论。实测是最低成本的确权方式。5.3 什么情况下我会选它俩选择排序真正说得上话的场景元素数量很小几十个以内而且代码里不想引入额外依赖手写一个十行版本最省事交换或写入的代价远远高于比较比如写的是某种只能整块更新的硬件状态或者写日志、写网络包的场景需要一个运行时间高度确定的排序不允许出现意外的长尾延迟教学和面试场景用来对比说明为什么数据结构能改变复杂度堆排序真正说得上话的场景内存极度受限、不允许递归、不允许额外分配缓冲区但又需要 O(n log n)。堆排序是原地 O(n log n) 里最省心的一个需要最坏情况也有保证的 O(n log n)。快速排序虽然有随机化版本但理论上仍存在退化可能而堆排序的最好最坏平均都是 O(n log n)只需要前 k 个最值。这时候根本不用全排维护一个大小为 k 的堆即可复杂度 O(n log k)当 k 远小于 n 时非常划算。这个技巧在从海量数据里挑最大的 100 个找数据流的中位数这类问题上用得极多需要优先队列语义的地方。定时器调度、任务排队、图算法里的最短路、合并多个有序序列背后都是堆顺便说一句关于稳定性的注意事项两者都是不稳定的也就是相等元素的相对顺序在排序后可能改变。选择排序不稳定的原因很直接——它把最小值直接甩到前面去中间那些和最小值相等的元素就被跨越了。堆排序不稳定的原因在排序阶段堆顶元素被换到末尾这一下跨越大半个数组必然打乱相等元素的相对次序。如果业务上要求保持原有顺序比如先按时间排好、再按优先级稳定排序这两个都不能用得用归并排序或者给每个元素加上原始下标做二次比较。举个堆排序不稳定的具体例子数组[3a, 3b, 1]a、b 用来标记两个相等元素 3 的原始顺序。建堆后是[3a, 3b, 1]已满足大顶堆。排序阶段第一轮交换 a[0] 和 a[2] →[1, 3b, 3a]有效范围前两个下沉 1 时跟 3b 交换 →[3b, 1, 3a]。第二轮交换 a[0] 和 a[1] →[1, 3b, 3a]。结果两个 3 的顺序变成了 b 在前 a 在后原顺序被破坏了。这个例子只有三个元素特别好记。6. 几个真实的排查过程以及我踩过之后改掉的习惯6.1 排序结果部分正确九成是 size 参数没管住那是我第一次写堆排序建堆阶段验证过没问题但整体排完总是后段几个元素不对。当时的排查顺序记一下这个链路对类似问题都适用第一步单独测建堆函数。用[4, 6, 8, 5, 7, 9, 1]跑一遍对比手算结果[9, 7, 8, 5, 6, 4, 1]一致说明建堆逻辑没问题问题在排序阶段。第二步打印每一轮交换和下沉之后的数组。第一轮正常第二轮正常到某一轮突然发现有个本该冻结在末尾的元素又动了。这就锁定了方向有效范围没有正确收缩。第三步回看sift_down。果然孩子是否存在的判断用的是2*i1 len(a)而不是 size。已排序的尾部被当成了堆的一部分刚钉好的元素被重新卷进来比较于是又被换走了。改成传 size 之后立刻正确。排查这类问题的方法论很简单分段验证。堆排序天然分成两个阶段先把第一阶段验证干净再专心查第二阶段不要一上来就盯着全流程。另外强烈建议写一个堆性质校验函数随时能插进代码里检查def is_heap(a, size): for i in range(size // 2): left, right 2 * i 1, 2 * i 2 if left size and a[left] a[i]: return False if right size and a[right] a[i]: return False return True建堆后assert is_heap(a, n)每轮下沉后assert is_heap(a, end)。这两个断言一旦加上上面那个 bug 十秒内就会暴露。我在任何需要写堆的场合都会先把这个函数贴进去省下的调试时间远超写它的成本。6.2 把建堆写成自顶向下之后性能掉了一截还有一个坑是我自己聪明过头踩的。当时想着既然插入元素是往堆尾加再上浮那建堆也可以从空堆开始一个个把元素插进去调用上浮——逻辑上完全正确出来的也是合法堆。跑出来的结果没错但速度明显慢。原因在于自顶向下建堆的复杂度是 O(n log n) 而不是 O(n)。每个新插入的元素都从叶子位置开始往上浮平均要浮 log n 层n 个元素累计就是 n log n。而自底向上建堆里绝大多数节点只需要下沉零到一步。n10000 的时候两者的操作次数差好几倍实测下来建堆耗时差了三倍左右。这个教训我记到现在看起来等价的写法复杂度可能差一个量级。所以每次写堆相关代码建堆一定用for i in range(n // 2 - 1, -1, -1)这个自底向上的形式不用犹豫。6.3 索引公式混用手工验算比调试快十倍第三个坑是 1 基和 0 基公式混用前面提过一次这里展开说说排查手法。症状通常很怪能排出一部分但整体不是有序的而且元素看起来没有丢失只是位置错乱。这时候空想是没有用的我的做法是拿 n4 或 n5 的最小数组在纸上画出树形和数组下标的对应关系然后逐行对比代码里的索引计算公式。具体验算清单就三条下标 0 的左右孩子是不是 1 和 2下标 1 的孩子是不是 3 和 4n≥5 时最后一个非叶子节点是不是n//2 - 1。三条里只要有一条对不上就是公式错了。我现在的习惯是写堆代码时在注释里直接写一行# 0-based: child 2i1, 2i2; parent (i-1)//2边写边看比事后调试便宜太多。6.4 关于要不要手写的一点个人看法业务代码里手写堆排序的机会确实不多标准库基本都有性能也调得比我好。但有两类场合我坚持自己写一是需要前 k 大/前 k 小的流式处理标准排序帮不上忙必须自己维护一个大小为 k 的堆二是需要在下沉过程中插入自定义逻辑比如按某个复合 key 比较、或者下沉时顺带记录统计信息这时候把堆的骨架握在自己手里最方便。我个人的体会是堆这一块的知识真正值钱的地方不在排序本身而在优先队列这个抽象。你把下沉和上浮两个动作练熟之后会发现大量看起来不相关的问题——任务调度、合并有序链表、带权图的路径查找、数据流的中位数——底层都是同一个动作。选择排序则是理解这一切的起点它把每轮确定一个最值这个思路讲得足够裸裸到你能清楚看到瓶颈在哪里然后才有动力去找一个更好的结构来替代那一层线性扫描。这一层递进关系比记住两个算法各自的复杂度数字有用得多。
