到O(n log n)的本质与C语言实现)
排序算法是数据结构课里绕不开的第一道坎，其中选择排序和堆排序又特别容易被人割裂成两个独立知识点来学。选择排序用两层循环一遍一遍挑最小值，堆排序则借助二叉堆在 O(log n) 时间内选出最大元素，看起来就是选择排序的“加速版”。但如果你真把这两个算法放在一起看，会发现堆排序本质上就是选择排序的一次提速改造——只是把“扫描剩余区间找最小值”换成了“用堆维护当前最值”。这篇文章我会用 C 语言把两个算法完整过一遍，把 CLRS 里经常考的循环不变量证明拆开讲清楚，再给出实测过的数据规模和耗时对比，最后聊几个我在实际工程里踩过的坑，希望能让正在啃《算法导论》或准备面试的朋友少走弯路。
1. 先看懂选择排序到底在“选”什么
1.1 两层循环的本质：每一轮只干一件事
选择排序的思想可以直接压缩成一句话：把数组看成“已排序区”和“未排序区”，每一轮从未排序区挑出一个最小值，放到已排序区的末尾。外层循环i从 0 走到n-2，内层循环在a[i+1..n-1]里找比当前候选更小的元素，记下它的下标minIdx。扫描结束后，把a[i]和a[minIdx]交换。
注意一个关键点：内层循环不是“发现更小就立刻交换”，而是只更新下标。最小值是在整轮扫描结束后才最终确定的，交换只发生在每一轮外层循环的末尾。这样做的直接好处是交换次数被压得很低，每一轮最多产生一次交换。
用生活里的例子来理解，选择排序就像你在货架上挑苹果：你先把第一个苹果拿在手里作为基准，沿着货架一路看过去，只要看到更小的就记住它的位置。走完一整排后，再把手里这个基准苹果放到它该去的地方。整个过程里你并没有一路把苹果换来换去，你只是“记住”了最小的那个。
1.2 用一个例子走一遍完整过程
拿一个常见的小数组[5, 2, 4, 6, 1, 3]来手动跑一遍，理解会更直观：
数组：[5, 2, 4, 6, 1, 3] i=0：扫描 a[1..5]，最小值是 a[4]=1，交换 a[0] 与 a[4] → [1, 2, 4, 6, 5, 3] i=1：扫描 a[2..5]，最小值是 a[1]=2，不需要交换 → [1, 2, 4, 6, 5, 3] i=2：扫描 a[3..5]，最小值是 a[5]=3，交换 a[2] 与 a[5] → [1, 2, 3, 6, 5, 4] i=3：扫描 a[4..5]，最小值是 a[5]=4，交换 a[3] 与 a[5] → [1, 2, 3, 4, 5, 6] i=4：扫描 a[5]，只剩一个元素，结束可以看到，当i=1时，因为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 和很多算法教材讲的证明套路是三步：初始化、保持、终止。
初始化：外层循环从i=0开始，此时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]的右边，前面依然有序；并且它正好是全局第i+1小的元素，所以a[0..i]包含了前i+1个最小的元素。a[i+1..n-1]则包含剩余元素。不变量对下一轮i+1依然成立。
终止：外层循环结束时，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 的节点都没有孩子（它们的2i+1或2i+2都超过了 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、2i+1、2i+2之间跳来跳去，尤其在建堆和下沉阶段，越是树的上层，下标跨度越大，缓存命中率越差。这也是为什么在大部分“平均情况”下，快速排序的实测速度往往优于堆排序，尽管它们同样能达到 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*i+2写成了2*i+1，或者堆排序主循环把siftDown的堆大小参数传成了固定n。写完之后，再拿一个长度为 2 和长度为 3 的数组快速验证一遍边界，确认没问题再交给考官或提交运行。这个花一分钟的小动作，能帮你避开堆排序脚本里最常见的一类事故。
