排序算法这玩意是数据结构绕不过去的坎。面试考、笔试考、工作中写业务代码不怎么用到但一写中间件就全回来了。我见过不少人在堆排序上栽跟头对着一堆诡异的下标推导怀疑人生。也有一些人觉得选择排序太简单没啥好讲可真要让他写一遍不是边界写错就是循环条件搞反。这篇我就把选择排序和堆排序摊开讲。这俩本质上是同一条思路的两个阶段——每轮从中选出最优解放到正确位置。区别只在于“选”的手法和“选”的成本。我尽量按照实际动手写代码的顺序来讲中间会穿插CLRS那套循环不变量的证明思路也会给出完整的C语言实现。篇幅可能有点长但如果你能沉下心一口气读完再用半小时把代码敲一遍这几块骨头基本就啃下来了。1. 内容整体设计与思路拆解1.1 选择排序到底在“选”什么选择排序的思路极其朴素每一轮从未排序区间里挑一个最小或最大元素把它放到已排序区间的末尾。重复n-1次整个数组就有序了。这个策略有个非常直观的生活类比你有一堆散乱的扑克牌每次都从里面翻出最小的那张放到手里牌堆的底端然后从剩下的牌里再翻最小的一张接着放。这个过程不涉及任何元素跳跃式插入也没有“交换链式”的连锁反应每一步都清清楚楚找到一个最小的送它归位。用白话说就是在第1轮扫描整个数组找到最小值把它的位置和第0个位置交换。在第2轮从第1个位置开始往后扫找到最小值把它的位置和第1个位置交换。依此类推第i轮从下标i开始扫描到末尾找到最小值和下标i交换。到这一步为止代码框架非常简单。但如果你只是背下这个流程过两天就忘了。真正值得琢磨的是为什么第i轮只需要扫描i之后的部分答案藏在循环不变量的思想里。在CLRS《算法导论》里对选择排序的循环不变量是这样描述的在每一轮迭代开始前子数组A[0..i-1]已经是有序的且其中的每个元素都不大于子数组A[i..n-1]中的任何元素。这个不变量是理解选择排序正确性的钥匙。初始时i0A[0..-1]是空数组条件自然成立。每轮结束时我们将A[i..n-1]中的最小元素放到A[i]位置于是A[0..i]有序且不大于剩余部分下一轮的初始条件重新成立。到in-1时整个数组有序。这个证明思路非常严密也解释了后面堆排序的优化方向。1.2 堆排序同一思路的升级版选择排序的痛点太明显了——每一轮找最小值都是线性扫描O(n)所以总复杂度必然是O(n²)。堆排序就是在这个“找最小值”的动作上动了刀它把“每轮线性扫描n-i个元素”升级为“用二叉堆维护当前最小值O(log n)时间取出”。于是总体复杂度从O(n²)降到了O(n log n)。这个设计思路值得好好体会一下。程序员解决问题往往不是凭空发明新流程而是对旧流程的某个瓶颈环节做结构性优化。选择排序的瓶颈是“找最小元素太慢”堆排序就在这个环节上做文章先把整个数组调整成一个“最小堆”父节点值不大于子节点这样堆顶天然就是全局最小值。取出堆顶后把数组最后一个元素挪到堆顶再执行一次“向下调整”就能让剩余元素重新满足堆性质。如此循环n-1次排序完成。这里有一个特别容易被忽略的地方堆排序使用的堆结构并不是像std::priority_queue那样用malloc出来的独立结构而是直接把原数组原地整理成堆。这是堆排序最大的魅力之一——O(1)的额外空间复杂度连一个临时数组都不用。它完全靠数组下标之间的关系来表示一棵完全二叉树下标i的父节点是(i-1)/2左孩子是2i1右孩子是2i2。所以看堆排序不要把它当成一个“神秘的堆的数据结构”它就是“用数组模拟完全二叉树”加上“选择排序的框架”。一旦你把这个映射关系印在脑子里下面代码里的每个下标运算都有了实感。1.3 为什么这两个算法值得放在一起学很多人学排序是散点式地学今天冒泡明天插入后天快排每个算法孤立地背代码。但学算法最忌讳的就是孤立记忆——你很快就忘了而且一旦忘了就完全不会推。我的建议是把选择排序和堆排序当成一条演化链来学。选择排序每轮线性扫描找最小值。堆排序用堆结构加速“找最小值”这个操作。这样你记住的就不只是两段代码而是一个“怎么优化算法瓶颈”的思维模型。以后你看到任何“每次都要取最值”的问题第一反应就是“能不能用堆来加速”这就触及了算法学习的核心价值。2. 核心细节解析与实操要点2.1 选择排序的实现从索引边界说起先给一段最基础的C语言实现。#include stdio.h void swap(int *a, int *b) { int tmp *a; *a *b; *b tmp; } void selection_sort(int arr[], int n) { int i, j, min_idx; for (i 0; i n - 1; i) { min_idx i; for (j i 1; j n; j) { if (arr[j] arr[min_idx]) { min_idx j; } } if (min_idx ! i) { swap(arr[i], arr[min_idx]); } } }这段代码需要关注三个边界细节。第一外层循环只需要到n-2。因为当i走到倒数第二个位置时最后剩下的那个元素必然是全局最大不需要再扫描。很多人写i n多循环一轮虽然不影响正确性最后一轮min_idx等于自己swap不交换但这是思路不清晰的表现。第二内层循环从i1开始j的终止条件是j n而不是j n-1这个就是数组下标习惯两者等价但写成j n更符合C语言的常规。第三min_idx必须在每轮外层循环开始时重新初始化成i。它记录的是“当前找到的最小元素的下标”而不是值本身。用一个变量存值然后直接交换位置会丢失索引信息这是新手最容易犯的错。2.2 为什么选择排序“交换次数是0到n-1”选择排序有一个常被人忽视的优点它的交换次数最多是n-1次。因为每一轮外层循环最多做一次交换把最小值放到位置i。即使数组完全逆序你也就是交换n-1次。这意味着什么如果你要排序的元素是“交换代价极其昂贵”的数据结构比如数组元素是巨大的结构体或者交换有副作用选择排序在交换次数这一点上吊打插入排序和冒泡排序。冒泡排序最坏情况下交换次数接近n²/2插入排序移动次数也是O(n²)级别而选择排序无论数据怎么分布比较次数永远是n(n-1)/2交换次数永远是O(n)。所以这产生了一个反直觉的结论在“比较便宜、交换贵”的场景下选择排序其实是个不错的选择。比如你对一组大型结构体按某个小字段排序不想搞复杂的索引排序先排下标数组再按序抽取那么直接排结构体本身时选择排序能有效控制交换造成的开销。不过同样因为这个特性选择排序属于不稳定排序。稳定性问题是实际工程中筛选排序算法的重要依据后面第4部分我展开讲。2.3 堆排序的建堆过程先理解“堆化”堆排序的核心是一个操作heapify向下调整。它的作用是假设某个节点的左右子树都已经满足堆性质但这个节点本身可能不满足比如它比自己的子节点大那就把它和较小或较大的子节点交换然后递归向下调整直到它落到正确位置。建堆是从最后一个非叶子节点开始从下到上逐个执行heapify。最后一个非叶子节点的下标怎么算如果数组长度为n最后一个元素的父节点就是(n-2)/2因为最后一个元素下标是n-1父节点是(n-1-1)/2。举例数组长度10最后一个非叶子节点下标是4数组长度11还是4。这一块经常有人写错建议直接记住结论for (int i n / 2 - 1; i 0; i--)来建堆。你可能会有疑问为什么不从下标0开始向下调整而是从后往前因为heapify的前提是“左右子树已经是堆”。叶子节点本身天然是堆只有自己一个元素从最后一个非叶子节点开始就能保证每次调用heapify时它的左右子树都已经调整过了。这和动态规划的“自底向上填表”是一个思路。建堆的复杂度需要注意很多人以为建堆是O(n log n)其实精确计算下来是O(n)。直观的原因是随着下标的减小每个节点heapify的成本随之降低。靠近根部的节点调整次数多但数量少靠近叶子的节点调整次数少甚至为1但数量多。这个反直觉的结论在《算法导论》里有完整证明用的方法是求和一个几何级数的上界。面试中问到“为什么建堆是O(n)”时能把这个直观说法讲清楚就很不错了——每个元素下沉的路径长度随着它离叶子的距离缩短大部分元素都离叶子很近所以总代价线性级。2.4 堆排序完整代码升序排列用大顶堆有些初学者会困惑一个问题升序排序堆顶应该是最小值吗堆排序的常规实现恰恰相反——升序排序用的是大顶堆。你每轮把堆顶最大值换到数组末尾然后缩小堆范围把剩下的部分重新堆化。最大值从末尾开始往前填最后得到的就是升序数组。如果你用小顶堆确实每轮能取出最小值但取出后最小值必须放到结果数组的前面这就需要额外O(n)的存储空间。为了节省空间原地排序我们接受“逆序弹出”的方案用大顶堆。完整C语言实现如下。#include stdio.h void swap(int *a, int *b) { int tmp *a; *a *b; *b tmp; } // 向下调整使得arr[0..n-1]中以root为根的子树满足大顶堆性质 void sift_down(int arr[], int n, int root) { int largest root; int left 2 * root 1; int right 2 * root 2; if (left n arr[left] arr[largest]) { largest left; } if (right n arr[right] arr[largest]) { largest right; } if (largest ! root) { swap(arr[root], arr[largest]); sift_down(arr, n, largest); } } void heap_sort(int arr[], int n) { // 建堆从最后一个非叶子节点开始自底向上调整 for (int i n / 2 - 1; i 0; i--) { sift_down(arr, n, i); } // 一个个从堆顶取出最大元素放到数组末尾 for (int i n - 1; i 0; i--) { swap(arr[0], arr[i]); sift_down(arr, i, 0); } }这段代码要特别注意第26行和第34行第26行sift_down(arr, n, i)的n是完整数组长度因为建堆时所有元素都在堆内第34行sift_down(arr, i, 0)的堆边界缩小了因为末尾i位置已经放上了最终元素不再参与堆调整。很多人把这两处的边界写混导致排序结果出现“末尾元素被重新交换到前面”的诡异bug。2.5 递归和迭代的选择上面的sift_down用的是递归写法思路清晰工程上建议改成迭代。原因倒不完全是栈溢出——堆的深度是O(log n)n如果是一亿深度也就27层左右来递归的栈压力根本不算大。真正的原因是递归写法每次调用时函数栈开销虽然不致命但在排序这种高频循环里多点函数调用开销也是白花花的性能。迭代写法的逻辑和递归完全等价可读性反而更高。void sift_down_iter(int arr[], int n, int root) { while (1) { int largest root; int left 2 * root 1; int right 2 * root 2; if (left n arr[left] arr[largest]) { largest left; } if (right n arr[right] arr[largest]) { largest right; } if (largest root) { break; } swap(arr[root], arr[largest]); root largest; } }两种写法我建议你都想一想、敲一遍。递归版本更贴近“heapify”的数学定义适合用来理解迭代版本更适合落地使用。面试时如果要求手写堆排序建议直接写迭代版本少几个函数调用栈也少招人问“递归深度会不会溢出”这种扩展问题。3. 实操过程与核心环节实现3.1 用CLRS循环不变量视角再看选择排序第2部分给的代码是能跑的但如果你想彻底搞懂它我强烈建议你照着CLRS的套路走一遍循环不变量的三步证明。这是把代码从“背下来”变成“推导出来”的分水岭。初始化当i0时子数组A[0..-1]为空。空数组当然有序而且“其中任何元素不大于A[0..n-1]中任何元素”这个命题是空洞成立的不存在这样的元素所以不变量成立。保持假设某轮开始时A[0..i-1]有序且都不大于剩余的A[i..n-1]。内层循环会在A[i..n-1]中找到最小元素的下标min_idx。把A[min_idx]和A[i]交换后A[i]现在是剩余部分的最小值而A[i-1]已排序部分的最大值不大于A[i]。因此A[0..i]有序且其中的元素都不大于新的剩余部分A[i1..n-1]下一轮的不变量成立。终止当in-1时A[0..n-2]有序并且它们都不大于A[n-1]。于是整个数组有序。这个证明里最精妙的地方在于“剩余部分”这个集合的定义随i变化。它帮你随时把握住一个核心事实选择排序每一轮只保证一个元素落到最终位置之前放好的元素绝对不会再被动过。这和插入排序截然不同插入排序每轮会“挤动”已排序区间来腾位置。3.2 手动模拟堆排序一轮流程光看证明容易飘来手推一轮堆排序把下标和值都摆出来。假设数组是[4, 10, 3, 5, 1]长度为5。第一步建堆。最后一个非叶子节点下标是5/2-11对应元素10。它的左孩子是下标3值5右孩子是下标4值110比两者都大不需要调整。接着看下标0元素4左孩子下标1值10右孩子下标2值3最大的是10于是交换4和10数组变成[10, 4, 3, 5, 1]。但交换后下标1的4可能还违反堆性质继续调整它的左孩子下标3值5右孩子下标4值1最大是5交换4和5数组变成[10, 5, 3, 4, 1]。此时堆结构是大顶堆。排序开始i4交换堆顶10和末尾1数组变成[1, 5, 3, 4, 10]堆范围缩小到前4个元素对堆顶1做sift_down。1的左孩子5、右孩子3最大是5交换得到[5, 1, 3, 4, 10]继续调整1的左孩子是4下标3右孩子越界交换1和4得到[5, 4, 3, 1, 10]。前4个元素重新成堆数组末尾10已经就位。i3交换堆顶5和下标3的1数组变成[1, 4, 3, 5, 10]堆范围是前3个元素。调整堆顶1左孩子4、右孩子3交换1和4得到[4, 1, 3, 5, 10]。前3个元素成堆。i2交换堆顶4和下标2的3数组变成[3, 1, 4, 5, 10]堆范围是前2个元素。调整堆顶3左孩子1不变。i1交换堆顶3和下标1的1数组变成[1, 3, 4, 5, 10]排序完成。手动推一遍你对“堆排序的每一轮做了什么”会有极强的感知。你会发现堆排序的交换次数在前几轮看起来毫无章法但每一轮堆顶元素都会被放到它最终该在的位置。3.3 复杂度分析选择排序看比较数堆排序看堆化路径选择排序的比较次数是固定的n(n-1)/2不随数据分布变化。不管数据是本身就有序的还是完全逆序的每轮都要完整扫描剩余区间。这导致了它缺乏“自适应”特性——即便你给它一个已经排好的数组它依然要做同样的比较量。这个特性有时候是缺点没利用输入数据的有序性有时候是优点最坏情况也不会恶化到比n²级别更多。交换次数前文已提最多n-1次。堆排序的时间复杂度拆成两部分建堆O(n)。n-1次“交换向下调整”每次调整最坏O(log n)所以是O(n log n)。综合就是O(n log n)。注意堆排序是“最坏情况也是O(n log n)”的排序算法这点比快速排序要强——快速排序最坏是O(n²)比如已经有序的数据配合糟糕的枢纽元选择。当然快排在工程实践上依然是默认王者原因涉及缓存局部性、常数因子和随机化手段这在第4部分细说。堆排序的额外空间复杂度是O(1)这是它的巨大优势。很多内存受限的嵌入式环境、驱动模块内部排序都会倾向用堆排序而不是归并排序就因为它不需要额外数组。3.4 用C语言完整跑一遍并验证把选择排序和堆排序放在同一个demo程序里对比验证#include stdio.h #include stdlib.h void print_array(int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); } int main() { int arr1[] {64, 25, 12, 22, 11}; int n1 sizeof(arr1) / sizeof(arr1[0]); int arr2[] {64, 25, 12, 22, 11}; int n2 sizeof(arr2) / sizeof(arr2[0]); selection_sort(arr1, n1); printf(selection sorted: ); print_array(arr1, n1); heap_sort(arr2, n2); printf(heap sorted: ); print_array(arr2, n2); return 0; }输出应该都是11 12 22 25 64。如果你改一下入参比如传一个完全降序的数组{5, 4, 3, 2, 1}或者传一个带重复值的数组{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}看看两组算法输出是否稳定一致能进一步帮你排查实现中的边界问题。说到调试我强烈建议你写一个小的随机测试框架生成足够多的随机数组分别调用selection_sort和heap_sort然后和C标准库的qsort结果对比任何不一致都说明你的实现有bug。这一步是工程级验证不是学校作业级的“跑一个用例就交差”。我用这种方法抓到过自己在sift_down边界条件上的一个隐蔽错误眼看输出99%有序但最后一个元素错位。4. 常见问题与排查技巧实录4.1 选择排序是稳定排序吗为什么不是稳定排序。先解释稳定性如果数组中有两个相等元素排序后它们的相对顺序保持不变这种算法就叫稳定的。选择排序每轮会选中剩余区间中的最小值并把它和当前i位置元素交换。问题就出在这个“交换”上——它可能把一个靠前的元素直接换到后面去。举例数组[5a, 3, 5b, 1]其中5a、5b我是用来区分两个值相等的5。第一轮找到最小值1下标3和下标0的5a交换数组变成[1, 3, 5b, 5a]。你看本来5a在5b前面排序后5b跑到5a前面了相对顺序被破坏。选择排序的稳定性问题在工程上会导致一个连锁反应如果你先按“部门”排序再按“薪资”排序希望薪资相同的记录依然保持部门排序的结果那么第二趟排序算法必须稳定。选择排序做不到所以这种“多关键字排序”场景下你会换用归并排序或插入排序。4.2 堆排序也不是稳定排序原因不同堆排序的不稳定性来自两个层面一是父子节点交换时可能跨越多个位置。大顶堆堆顶元素和数组末尾元素交换时如果堆里还有另一个与堆顶等值的元素它可能被换到前面也可能留在原地相对顺序没法控制。二是sift_down过程中一个节点往下“沉”时可能经过若干与它等值的节点把它们顶到上面去。比如大顶堆里有个节点值是5它往下沉时路过另一个值为5的兄弟节点为了维持堆结构两者的相对位置就会变动。所以堆排序虽然时间复杂度漂亮、原地排序但一旦涉及“相同关键字顺序要保留”的需求它直接出局。4.3 堆排序 vs 快速排序为什么工程上快排才是默认选择你要是看过各种排行榜会发现C标准库的qsort、C的std::sort底层都不是堆排序而是快排的变体某些情况下混入插入排序。这是为什么第一缓存局部性。快排的分区操作是对数组进行连续扫描访问模式是线性的CPU缓存命中率很高。堆排序的访问模式是跳跃式的——你总是在下标i、2i1、2i2这些地方跳来跳去缓存命中率差得多。现代计算机的瓶颈早已不是算法复杂度而是内存访问模式。第二常数因子。堆排序每轮sift_down平均需要比较2到3次找左孩子、右孩子的最大值而快排每轮只需要比较1次。n趋于无穷大时堆排序的2nlog₂n和快排的1.39nlog₂n差距在基准常数上就已经体现出来了。第三最坏情况规避。快排最坏O(n²)但这个最坏情况通常可以通过随机化枢纽元来避免到“几乎不会发生”。堆排序的最坏情况就是平均情况但如果常数因子差这个保证意义就打了折扣。所以堆排序的应用场景主要集中在需要最坏情况保证且内存极度有限、不希望有额外数组分配的场景。比如实时系统、嵌入式内核里的某些排序模块。其余的通用排序快排和归并是主流。4.4 建堆用“从下往上”和“从上往下”有什么区别有读者可能会问建堆能不能从下标0开始逐个sift_down能但那样复杂度会退化到O(n log n)而不是O(n)。原因是从根开始调整时你没法保证子节点已经满足堆性质每个节点都可能在向下沉的过程中多次穿越整个树高。而反过来从底部开始每个节点的调整路径短总代价低。这个差别在处理百万级数据时非常明显。4.5 递归堆化的栈溢出与性能我在真机上测过对一个100万随机整数排序递归堆化和迭代堆化的时间差大约在10%到20%之间。几十毫秒对单次排序无所谓但如果你在一个循环中调用无数次排序差距就累积起来了。另外有个冷知识堆排序在数据“已经接近有序”时表现并不比乱序好多少。因为它每轮总要重新堆化而堆化的代价和当前堆的层数强相关数据分布对堆高度的影响很有限。堆排序对输入数据的“适应性”几乎为零这是它不如插入排序“见好就收”的地方。4.6 查找最小值还是最大值的细节堆排序里如果你要降序排序逻辑就要反过来——用小顶堆每轮把最小值放到末尾。实现上只需要把所有比较运算符从大于号改成小于号即可。我见过有人为了省这点改动强行在降序时还维持大顶堆然后按索引逆序输出结果数组输出倒是降序但堆结构不伦不类下一步维护时必然踩坑。想清楚你要的是升序还是降序再决定堆的类型别偷懒。5. 从选择到堆一个思维模型的延伸把选择排序和堆排序打通后你可以把这个思维模型迁移到很多算法问题上。最经典的是Top K问题要从10亿个数里找出最大的前100个如果先全排序复杂度是O(n log n)但用最小堆维护当前Top 100每来一个新数只要比堆顶大就替换堆顶并重新堆化复杂度是O(n log k)k固定为100时几乎等于O(n)。这就是堆排序思维的直接应用。另一个应用是“动态数据流的中位数”维护一个大顶堆存较小的一半数据一个小顶堆存较大的一半数据新元素来了就判断该进哪边必要时调整两边堆的大小差异。这也是堆结构的经典场景。所以我劝你学算法的时候不要背代码而是去抓“这个结构在解决什么瓶颈问题”。选择排序告诉你“线性扫描找最小值是低效的”堆排序告诉你“树形结构可以把最值查询优化到log级别”。带着这个思维去刷题你会发现自己对很多数据结构的理解都更上了一层。我在讲面试培训时经常问学生一个问题给你一个流式数据要求随时都能取出当前数据的中位数你的方案是什么能做出这个题的人几乎都先懂堆排序的原理。排序算法学得好不好不在于能不能默写代码而在于能不能把里面的思想迁移到新问题上。6. 写在最后的一些小经验排序算法是那种看起来简单但非常检验“工程细致度”的东西。我见过不少资深开发者在面试时手写堆排序翻车原因就是sift_down的边界条件和递归退出条件没有理清楚。给你一个查漏补缺清单我面试前也会拿它自测选择排序的外层循环结束条件是n-1还是n为什么可以到n-1而不是n内层循环的起始下标是i1还是i如果从i开始会有什么影响多比较一次不改变结果但浪费堆排序里n/2-1是怎么来的如果不是偶数长度这个公式还成立吗sift_down的终止条件是什么什么时候可以安全退出堆排序的swap之后为什么缩小堆范围从i开始而不是i1这些问题如果你能一口气回答出来说明你是真的理解了不是背的。最后分享一个我的调试技巧写排序算法时不要用大数组测试用{3, 3, 3}、{2, 1}、{1, 2}、{}这种极端小用例起步。等小用例全通过再用随机大数组和标准库对比。一个空数组就能逼出很多实现里的“非空假设”bug——如果你的排序函数一上来就访问arr[0]空数组直接就崩了。数据结构和算法这条路没有捷径但可以走得更聪明。把选择排序和堆排序当成一条线来学你会发现很多在其他地方零散见过的东西——二叉堆、优先队列、堆化、Top K——全都串起来了。这就是我写这篇长文的初衷。