到O(n log n)的本质与C语言实现)
排序算法是数据结构课里绕不开的第一道坎其中选择排序和堆排序又特别容易被人割裂成两个独立知识点来学。选择排序用两层循环一遍一遍挑最小值堆排序则借助二叉堆在 O(log n) 时间内选出最大元素看起来就是选择排序的“加速版”。但如果你真把这两个算法放在一起看会发现堆排序本质上就是选择排序的一次提速改造——只是把“扫描剩余区间找最小值”换成了“用堆维护当前最值”。这篇文章我会用 C 语言把两个算法完整过一遍把 CLRS 里经常考的循环不变量证明拆开讲清楚再给出实测过的数据规模和耗时对比最后聊几个我在实际工程里踩过的坑希望能让正在啃《算法导论》或准备面试的朋友少走弯路。1. 先看懂选择排序到底在“选”什么1.1 两层循环的本质每一轮只干一件事选择排序的思想可以直接压缩成一句话把数组看成“已排序区”和“未排序区”每一轮从未排序区挑出一个最小值放到已排序区的末尾。外层循环i从 0 走到n-2内层循环在a[i1..n-1]里找比当前候选更小的元素记下它的下标minIdx。扫描结束后把a[i]和a[minIdx]交换。注意一个关键点内层循环不是“发现更小就立刻交换”而是只更新下标。最小值是在整轮扫描结束后才最终确定的交换只发生在每一轮外层循环的末尾。这样做的直接好处是交换次数被压得很低每一轮最多产生一次交换。用生活里的例子来理解选择排序就像你在货架上挑苹果你先把第一个苹果拿在手里作为基准沿着货架一路看过去只要看到更小的就记住它的位置。走完一整排后再把手里这个基准苹果放到它该去的地方。整个过程里你并没有一路把苹果换来换去你只是“记住”了最小的那个。1.2 用一个例子走一遍完整过程拿一个常见的小数组[5, 2, 4, 6, 1, 3]来手动跑一遍理解会更直观数组[5, 2, 4, 6, 1, 3] i0扫描 a[1..5]最小值是 a[4]1交换 a[0] 与 a[4] → [1, 2, 4, 6, 5, 3] i1扫描 a[2..5]最小值是 a[1]2不需要交换 → [1, 2, 4, 6, 5, 3] i2扫描 a[3..5]最小值是 a[5]3交换 a[2] 与 a[5] → [1, 2, 3, 6, 5, 4] i3扫描 a[4..5]最小值是 a[5]4交换 a[3] 与 a[5] → [1, 2, 3, 4, 5, 6] i4扫描 a[5]只剩一个元素结束可以看到当i1时因为a[1]2本身就是剩余区间的最小值所以不需要交换。这说明选择排序在代码里最好加一个if (minIdx ! i)的判断避免对已经有序的位置做无意义的写操作。这个细节对性能影响不大但如果排序的是结构体或者指针数组避免多余交换是很有意义的。1.3 复杂度初步比较是“点菜”交换是“上菜”选择排序的比较次数是固定的第一轮要比较n-1次第二轮n-2次直到最后一轮 1 次总数是(n-1) (n-2) ... 1 n(n-1)/2这个数字和输入数据是否有序完全无关。即使数组已经是升序排列选择排序依然会老老实实比较这么多轮。交换次数则不同每一轮最多交换一次所以最多是n-1次。我用“点菜”和“上菜”来比喻这两笔开销比较只是读取数据、做判断相当于翻菜单交换才是真正动数据相当于把菜端上桌。在普通整数数组里翻菜单和端菜的成本差不多但在某些场景下比如你要排序的是大型结构体、数据库记录对象、或者每次交换都会触发额外开销的数据那么交换一次的代价可能比比较十次还高。所以选择排序常被拿来作为“低交换次数”排序的代表这也是它在 O(n²) 家族里没有被彻底丢弃的重要原因。但同时也要记住选择排序是一个不稳定排序。典型的例子[5a, 5b, 2]第一轮选出 2 与 5a 交换变成[2, 5b, 5a]两个相等的 5 的相对顺序就变了。如果你在给“对象数组按某个字段排序”时会依赖稳定性的场景选择排序并不合适。2. 用循环不变量给选择排序“验身”CLRS 式三步证明2.1 先把循环不变量这句话说清楚很多人看到“循环不变量”四个字就发怵其实它就是把“算法为什么是对的”翻译成一局话在每次外层循环开始之前有哪些事实是必定成立的。只要这个事实在循环开始前成立、每轮循环后依然成立、循环结束时又恰好能推出整个数组有序算法就一定是正确的。对选择排序来说这个不变量可以写成在第i轮循环开始前a[0..i-1]已经包含原始数组中最小的i个元素并且已经按升序排列a[i..n-1]中存放的是剩余的所有元素。注意这里说的“包含最小的 i 个元素”比单纯说“a[0..i-1] 已经排好序”要强得多。它保证了前面这一段不仅内部有序而且在全局意义上也是“最终就该待在前面”的那几个元素后面不可能再冒出比它们小的数。2.2 初始化、保持、终止一步步来CLRS 和很多算法教材讲的证明套路是三步初始化、保持、终止。初始化外层循环从i0开始此时a[0..-1]是空数组。空数组当然满足“已包含最小的 0 个元素”这个条件同时a[0..n-1]包含全部剩余元素不变量成立。保持假设第i轮循环开始前不变量成立。这时a[0..i-1]已经是全局最小的i个元素且有序。第i轮的内层循环在a[i..n-1]中找到了最小值min下标是minIdx然后把a[minIdx]与a[i]交换。关键推理在这因为a[0..i-1]已经包含了前i个最小的元素所以剩余区间里的任意元素都不小于a[i-1]也就是说剩余区间的最小值min也不小于a[i-1]。交换完成后a[i]存的就是剩余区间的最小值它被放在a[i-1]的右边前面依然有序并且它正好是全局第i1小的元素所以a[0..i]包含了前i1个最小的元素。a[i1..n-1]则包含剩余元素。不变量对下一轮i1依然成立。终止外层循环结束时i已经推进到n-1。按照循环条件a[0..n-2]已经包含前n-1个最小的元素且已经有序。那么剩下的最后一个位置a[n-1]必然就是整个数组的最大值。于是a[0..n-1]整体有序算法正确性得证。2.3 证明的副产品看清选择排序的“天花板”这个证明不是在做无用功它直接揭示了选择排序的两个性格比较次数恒定、交换次数很少。正是因为“每一轮选择都必须在剩余区间里完整扫描一遍”所以无论输入是乱序还是接近有序比较次数都是n(n-1)/2。这意味着选择排序不具备自适应性对一个几乎排好序的数组它的运行时间不会因此下降。这跟插入排序形成了鲜明对比插入排序碰到基本有序的数据每轮几乎只比较一两次复杂度能接近 O(n)。所以当你评估是否使用选择排序时需要理解它的“天花板”它在交换成本高的场景有价值但它永远不会因为输入有序而变快。3. 从“扫一遍找最小”到“用堆找最大”堆排序靠什么提速3.1 选择排序真正的瓶颈不在交换在查找前面算了选择排序的总工作量大约由两部分组成比较找最小值n(n-1)/2次数量级 O(n²)交换移动数据最多n-1次数量级 O(n)。当n到十万级别时比较次数高达约 50 亿而交换次数只有十万次。真正的瓶颈显然在于“如何在剩余区间里快速找到最小值”。如果每一轮都要从头到尾扫描那无论如何都会停留在 O(n²)。于是问题变成有没有一种结构能让我们在多次“取走最小值/最大值”的操作里不需要每次重新扫描整个数组堆就是这样一种结构。它通过事先记录部分比较结果把“找最值”的成本分摊到了树的层级上。3.2 堆是一个会自我维护的“半排序结构”先复习一下最大堆的定义它是一棵完全二叉树并且每个父节点的值都不小于它的子节点。这个性质叫堆序。由于根节点永远是整棵树的最大值所以“取最大值”这个操作在堆里是 O(1) 就能读到的。但堆排序不只是要“读”最大值还要“取出并移除”最大值。移除根节点后为了维持堆的完全二叉树结构和堆序需要把数组最后一个元素放到根上然后做一次“下沉调整”。这个调整只会沿着一条从根到叶子的路径走路径长度是树的高度也就是 O(log n)。每一轮排序只需要一次下沉调整所以整体复杂度从 O(n²) 降到了 O(n log n)。用句大白话总结堆是一只提前做了功课的“无序区管理器”它替排序算法记住了“当前最大元素在哪”不需要每轮重新满数组找。3.3 为什么原地排序最终选了“大根堆”堆既可以是小根堆也可以是大根堆。为什么堆排序通常都是先把数组建成大根堆而不是小根堆这得从“排序结果的方向”来解释。我们的目标是升序排列也就是最终数组从左到右从小到大。大根堆的根是最大值把它交换到数组末尾后这个最大值就被“冻结”在最后一个位置下次再把第二大值交换到倒数第二个位置依此类推。于是数组尾部逐步堆积的就是“最大的那些数”前面剩下来的是尚未排序的区域最终得到从小到大排列的结果。如果使用小根堆也能原地完成排序但每一轮取出的最小值会跑到数组尾部去最终你会得到从大到小排列的数组。同样能排方向却和常规需求相反。因此教科书和常见实现里统一采用“大根堆 升序”的组合是为了让交换出去的值正好待在它最终的位置上不需要再二次移动。4. 堆排序三个阶段详解建堆、堆化、倒序收尾4.1 从数组到堆为什么建堆要从 n/2-1 开始堆排序的第一步是把无序数组堆化。数组下标从 0 开始父子节点的关系是父节点下标 (i - 1) / 2 左孩子下标 2 * i 1 右孩子下标 2 * i 2建堆的思路是从最后一个非叶子节点开始自底向上地做“下沉调整”。为什么要从n/2 - 1开始而不是从n-1开始因为下标大于n/2 - 1的节点全部是叶子节点。叶子节点没有子节点不满足“父亲大于等于孩子”这种需要调整的事天然就是合法堆的一部分不需要任何处理。举个例子数组长度是 10下标为 5、6、7、8、9 的节点都没有孩子它们的2i1或2i2都超过了 9所以从下标10/2 - 1 4开始往前倒着处理把所有非叶子节点逐个下沉就能保证整棵树满足堆序。这个做法叫自底向上建堆整体时间复杂度是 O(n)不是 O(n log n)。注意别跟“从堆顶不断插入元素”搞混那种自顶向下逐个插入的建堆方式才是 O(n log n)。4.2 堆化就是“下沉”不是“上浮”堆排序里最核心的小函数叫siftDown也叫maxHeapify它的任务是假设某个节点的左右子树都已经满足堆序但当前节点可能比某个子节点小需要让当前节点一步步“沉”到它该去的位置。具体步骤是找到当前节点、左孩子、右孩子三者中的最大值如果最大值就是当前节点那么以它为根的子树已经满足堆序直接结束如果最大值是某个孩子就把当前节点和孩子交换然后继续对交换后的那个孩子位置做同样的下沉操作。这里有个细节下沉过程中只需要沿着最大值的路径走不是两边同时走。因为左右子树都是合法的堆交换后只会破坏被交换的那一棵子树另一棵子树完全不受影响。所以单次下沉的复杂度是 O(log n)堆排序的排序阶段复杂度就是(n-1) * O(log n)整体 O(n log n)。4.3 排序阶段把堆顶“扔”到堆外建堆完成后数组a[0]是整个数组的最大值但剩下的数组还不是升序。排序阶段要做的是反复执行交换 a[0] 和 a[i] 堆大小减 1 对新的堆顶执行 siftDown其中i从n-1递减到1。每一轮交换后当前最大值被送到下标i这个位置以后不再参与任何堆操作相当于“堆外区域”。然后新的堆顶元素不知道大小需要用一次下沉把它归位。这个过程是不是很像选择排序选择排序是“每一轮在剩余区间里扫描出最小值放到开头”堆排序是“每一轮从堆这种数据结构里取出最大值放到末尾”方向相反但“把最值逐步冻结到边缘”的骨架是完全一致的。5. 手写 C 实现边界、坑位和实测数据5.1 选择排序的 C 语言实现先用标准的 C 代码把选择排序写出来#include stdio.h void selectionSort(int a[], int n) { int i, j, minIdx, tmp; for (i 0; i n - 1; i) { minIdx i; // 假设当前 i 就是最小值位置 for (j i 1; j n; j) { if (a[j] a[minIdx]) { minIdx j; } } if (minIdx ! i) { tmp a[i]; a[i] a[minIdx]; a[minIdx] tmp; } } }这个代码里最容易出错的地方有两个。第一个是minIdx忘记在每轮开头重置为i如果不重置上一轮的最小值下标会残留导致后续判断出现问题。第二个是交换前不判断minIdx ! i虽然结果没错但对于已经有序的数组每一轮都会做一次“自己和自己交换”的无效写操作。你要排序的是普通整数可能无感如果交换的是结构体数组这可能是性能杀手。5.2 堆排序的 C 语言实现堆排序代码有三个部分下沉函数、建堆函数、排序主循环。我用递归版本写siftDown逻辑最清晰// 对以 i 为根的子树做下沉调整n 是当前堆的有效大小 void siftDown(int a[], int n, int i) { int largest i; int left 2 * i 1; int right 2 * i 2; if (left n a[left] a[largest]) { largest left; } if (right n a[right] a[largest]) { largest right; } if (largest ! i) { int tmp a[i]; a[i] a[largest]; a[largest] tmp; siftDown(a, n, largest); // 继续下沉 } } // 自底向上建堆 void buildMaxHeap(int a[], int n) { int i; for (i n / 2 - 1; i 0; i--) { siftDown(a, n, i); } } void heapSort(int a[], int n) { int i, tmp; buildMaxHeap(a, n); for (i n - 1; i 0; i--) { tmp a[0]; a[0] a[i]; a[i] tmp; siftDown(a, i, 0); // 堆大小变成 i } }写这段代码时特别容易踩坑的是边界判断。第一left n和right n不能漏否则数组越界后可能在面试里拿到一个 Undefined Behavior第二排序循环里siftDown(a, i, 0)传入的不是n而是当前堆大小i因为a[i]已经属于已排序区不能被堆化逻辑再碰到。忘了这一个参数变化是堆排序实现出错的高发原因。如果担心递归写法在某些场景下的栈开销也可以改成迭代版。虽然堆的递归深度只有 O(log n)通常在几十层以内不会爆栈但迭代版更直观可控void siftDownIter(int a[], int n, int i) { while (1) { int left 2 * i 1; int right 2 * i 2; int largest i; if (left n a[left] a[largest]) { largest left; } if (right n a[right] a[largest]) { largest right; } if (largest i) { break; } int tmp a[i]; a[i] a[largest]; a[largest] tmp; i largest; } }5.3 实测对比n 到十万量级差距就开始离谱我在普通笔记本上用 C 语言、开启-O2优化分别对随机整数数组跑了选择排序和堆排序数据如下。注意绝对值受机器影响重点看量级差距数据规模选择排序耗时堆排序耗时选择排序比较次数堆排序比较次数10,000约 0.05 秒约 0.001 秒约 5000 万约 27 万100,000约 2.1 秒约 0.01 秒约 50 亿约 340 万1,000,000太慢没继续跑约 0.12 秒约 5000 亿约 4000 万看到这个表你就能直观理解 O(n²) 和 O(n log n) 的差别了。选择排序在十万数据量时已经明显卡顿堆排序还在眨眼之间跑完。这里比较次数只是一个数量参考实际堆排序的比较次数会根据数据分布和堆结构略有浮动但量级不会变。6. 现实中怎么选堆排序不一定总赢选择排序也不是废物6.1 别急着说 O(n²) 一定输堆排序的时间复杂度看起来全面碾压选择排序但在数据量很小的时候优势并没有你想象中那么大。堆排序每次下沉要计算左右孩子下标、做两到三次比较和可能的分支跳转同时访问数组位置是跳跃的选择排序的内层循环只是顺序扫描每次比较极其简单。我实测过当n只有二三十个元素时选择排序和堆排序的耗时差距根本无法感知堆排序反而可能因为初始化堆的额外循环写操作更多表现稍差。这也是为什么很多工业级排序实现里在递归快排的“小数组尾部”不是继续用快排而是切到插入排序或简单排序常数因子在小规模时比渐近复杂度更起作用。所以当你只需要排几个或十几个元素时选择排序这种逻辑简单、没有额外堆结构调整的算法完全可以胜任。6.2 稳定性和缓存局部性两个常被忽略的维度堆排序有最坏情况 O(n log n)、原地排序的优点但它的短板非常明显不稳定、缓存不友好。先说不稳定。堆排序在堆化和交换过程中会把相同关键字的元素位置打乱。比如排序[5a, 5b, 2]第一次从堆顶拿最大值 5 的时候到底拿的是 5a 还是 5b 完全取决于堆结构无法保证稳定。如果排序的对象是已经按“时间”排好序的数据现在想按“优先级”再排一次并希望同优先级内部保持时间顺序堆排序就直接淘汰了。再说缓存。选择排序和插入排序的访问模式是从左往右顺序扫描对 CPU 缓存非常友好堆排序是二叉树逻辑映射到数组上的访问下标总是在i、2i1、2i2之间跳来跳去尤其在建堆和下沉阶段越是树的上层下标跨度越大缓存命中率越差。这也是为什么在大部分“平均情况”下快速排序的实测速度往往优于堆排序尽管它们同样能达到 O(n log n) 级别。堆排序的“稳健”体现在最坏情况不退化而不是常数因子优越。下面这张表可以帮你快速记住这些排序的主要差异排序算法平均复杂度最坏复杂度原地稳定缓存友好选择排序O(n²)O(n²)是否较友好堆排序O(n log n)O(n log n)是否较差插入排序O(n²)O(n²)是是很友好快速排序O(n log n)O(n²)是否友好归并排序O(n log n)O(n log n)否是外部存储友好6.3 这两个算法在工程里的真实归宿说句实在话我在真实业务代码里很少直接调用“裸”的选择排序归并排序和快排才是通用排序的主力。但这并不代表这两个算法不值得掌握。选择排序的真正价值更多在于“交换次数极低”和“实现极简单”。在嵌入式环境、核心代码教学、以及排序对象是被包装过的昂贵资源时它依然有适用空间。堆排序就更不用说了它背后那棵堆结构几乎无处不在操作系统的优先级队列、网络包调度、Top-K 问题、std::priority_queue全是堆在发光。堆排序本身往往是“堆”这个数据结构的附带产物理解了siftDown你就等于理解了优先队列删除堆顶之后再调整的核心过程。最后再分享一个我自己的习惯手写堆排序之前先把父节点、左孩子、右孩子的下标公式写在草稿纸角落。不要小看这一步很多次面试或笔试里代码逻辑全对最后挂在2*i2写成了2*i1或者堆排序主循环把siftDown的堆大小参数传成了固定n。写完之后再拿一个长度为 2 和长度为 3 的数组快速验证一遍边界确认没问题再交给考官或提交运行。这个花一分钟的小动作能帮你避开堆排序脚本里最常见的一类事故。
