选择排序到堆排序：从O(n²)到O(n log n)的进阶之路-北京尧图网络

1. 先从“选择”这件事说起很多人在学习排序算法的时候会把选择排序当成入门级的“开胃菜”觉得它太简单了看一眼就会。但真正让我对排序算法产生系统认知的恰恰是把这个“简单”的选择排序和堆排序放到一起去理解的那一刻。你要知道堆排序本质上就是选择排序的进阶形态它们的底层逻辑是一脉相承的都是“不断从未排序部分选出最大或最小元素放到已排序部分的末尾”只不过选择排序靠线性扫描来找极值堆排序靠堆这种数据结构来高效找极值。这个区别非常关键理解了它你就同时掌握了两个算法而且能更深入理解“数据结构如何优化算法复杂度”这个核心命题。这篇文章我会把选择排序和堆排序拆开来从原理到代码从复杂度到面试常考的循环不变量证明再到实际工程中怎么选型系统地讲一遍。适合正在准备面试的开发者、刚入门数据结构与算法的学生以及写业务代码但想补一补基本功的朋友。我会用C语言作为实现语言跟你平时接触到的教材风格保持一致看完你就能手写这两种排序并且能够回答关于它们的绝大多数追问。2. 选择排序看似简单坑其实不少2.1 核心逻辑与直观理解选择排序的基本思路就是一句话每一轮从未排序区间中找出最小值把它放到已排序区间的末尾。举个具体例子假设有一个数组[64, 25, 12, 22, 11]第一轮扫描整个数组找到最小值11和第一个位置的64交换结果是[11, 25, 12, 22, 64]。此时11已经位于正确位置我们把它看作已排序部分。第二轮扫描剩余部分[25, 12, 22, 64]找到最小值12和第二个位置也就是索引1的25交换结果为[11, 12, 25, 22, 64]。以此类推每一轮都让一个元素归位直到整个数组有序。这个算法好理解到什么程度你甚至可以不用写代码拿一副扑克牌就能模拟把牌摊开每次选出最小的一张放到最前面重复操作。它的思路直白到几乎不会有人理解错。C语言实现如下void selection_sort(int arr[], int n) { for (int i 0; i n - 1; i) { int min_idx i; for (int j i 1; j n; j) { if (arr[j] arr[min_idx]) { min_idx j; } } if (min_idx ! i) { int temp arr[i]; arr[i] arr[min_idx]; arr[min_idx] temp; } } }注意外层循环的条件是i n - 1不是i n。当n - 1个元素都放到了正确位置剩下的最后一个元素自然是有序的不需要再处理。这是一个很细节但值得注意的点很多初学的人会在这里多算了一轮虽然不影响正确性但会多做无用功。2.2 为什么选择排序有两层循环很多人问过冒泡排序、插入排序也都是两重循环为什么选择排序的时间复杂度一定是O(n^2)而且无法通过提前退出机制优化到更低的复杂度关键在于选择排序的“扫描”是无条件的。冒泡排序如果在某一轮没有发生任何交换可以提前终止插入排序如果当前元素比前一个元素大可以提前结束本轮。但选择排序不一样即使数组已经有序你仍然需要扫描完整轮来“确认”当前区间的最小值就是第一个元素。换句话说选择排序的最优时间复杂度、平均时间复杂度和最坏时间复杂度全部都是O(n^2)。比较次数方面选择排序是固定的n(n-1)/2次比较。交换次数最多是n-1次这也是选择排序的两个优点之一交换次数少对交换成本高的场景比如元素是很大的结构体有优势思路简单实现无脑不容易出错。缺点是无论数据怎么样比较次数都固定不像插入排序那样在近乎有序的数据上能跑到O(n)。2.3 正确性证明循环不变量怎么用CLRS《算法导论》里讲选择排序的时候会用到循环不变量很多自学的人在这里容易卡住。我用自己的话给你讲明白。循环不变量是一个在循环每次迭代前后都保持成立的性质。对于选择排序我们建立这样的不变量在处理第i轮循环之前数组的前i个位置索引0到i-1已经包含了整个数组中最小的i个元素并且它们已经有序。用这个不变量来证明算法正确性分三步初始化当i 0前0个位置自然是“包含最小的 0 个元素”不变量成立。保持假设在第i轮开始时前i个元素已经是全局最小的i个元素且有序。内层循环从i1到n-1扫描找到当前未排序部分的最小值。这个最小值一定是整个剩余数组中的最小元素因此它大于等于前i个元素中的任意一个。把它的索引记为min_idx与arr[i]交换后索引0到i这前i1个位置就是全局最小的i1个元素而且依然有序。下一轮i增加为i1不变量继续成立。终止当循环结束时i n-1前n-1个位置包含了全局最小的n-1个元素且有序剩下的最后一个元素只能是最大的那个所以整个数组有序。证明完毕。这段证明在面试中出现的频率很高尤其是“选择排序的循环不变量证明”这个问题很多人知道答案但说不清楚。关键在于说透两点一是“未排序部分扫描出的最小值必定是全局剩余最小”二是“前 i 个元素的有序性在交换后依然保持”。抓住这两点面试官就会认可你对算法的理解不是背书而是真的懂了。3. 选择排序的进阶从O(n^2)到O(n log n)3.1 核心瓶颈在哪选择排序慢慢在“找最小值”这一步上。每一轮要扫描整个未排序区间才能确定一个最小值的位置扫描一遍是O(n)要做n轮所以总共是O(n^2)。那么问题来了能不能用一种数据结构来维护未排序区间的最小值使得每一轮查询最小值的时间复杂度降到O(log n)如果可以总复杂度就能变成O(n log n)。答案就是堆。堆是一种特殊的完全二叉树分为大顶堆和小顶堆。大顶堆的特点是每个节点的值都大于等于它的左右子节点的值所以堆顶元素一定是整个堆中的最大值。小顶堆反之堆顶是最小值。如果我们维护一个小顶堆每次从堆顶取出的就是当前最小值取出并调整堆的时间复杂度是O(log n)总共执行n次就是O(n log n)。这就是堆排序的底层逻辑一句话概括用堆来加速选择排序的“选择”过程。这个思维跃迁非常重要。你写代码的时候可能不觉得数据结构有多重要但当你看到同样的选择逻辑仅仅因为换了一个“查找工具”就把复杂度从O(n^2)拉到了O(n log n)你对“算法逻辑数据结构”这句话就会有切肤之感。3.2 堆的基础操作上浮与下沉用 C 语言实现堆我们通常会用一个数组来模拟完全二叉树。对于索引从0开始的数组某个节点i的左孩子索引是2 * i 1右孩子索引是2 * i 2父节点索引是(i - 1) / 2堆的核心操作有两个堆化heapify和建堆build heap。堆化的场景是某个节点的左右子树都已经满足堆的性质但这个节点本身不满足。我们需要通过“下沉”操作让整个子树重新满足堆的性质。以大顶堆为例下沉操作的 C 代码void heapify(int arr[], int n, int i) { int largest i; int l 2 * i 1; int r 2 * i 2; if (l n arr[l] arr[largest]) { largest l; } if (r n arr[r] arr[largest]) { largest r; } if (largest ! i) { int temp arr[i]; arr[i] arr[largest]; arr[largest] temp; heapify(arr, n, largest); } }这段代码的含义是找到节点i、左孩子、右孩子三者中的最大值下标如果最大值不是当前节点就交换它们然后递归地对被交换下去的子树继续堆化。这里有一个新手常踩的坑堆化操作没有显式的“层数限制”它是靠递归自己终止的。如果传入的n不对或者下标计算边界没处理好很容易数组越界。所以每次递归前都要检查l n和r n这是硬条件少了任何一个程序都会出问题。上浮操作对应的是插入场景从小顶堆中插入元素时把新元素放到数组末尾然后不断和父节点比较如果比父节点小就交换直到满足堆性质。堆排序其实用不到上浮操作但理解上浮有助于你理解优先队列的实现。很多人在学堆排序时感觉吃力就是因为对这两种操作的区别没有形成清晰的认知建堆用下沉插入用上浮方向相反但都用“交换递归/循环”的方式修正结构。3.3 建堆为什么从n/2-1开始拿到一个无序数组我们怎么把它变成一个合法的堆答案是自底向上地调用heapify。代码是这样void build_heap(int arr[], int n) { for (int i n / 2 - 1; i 0; i--) { heapify(arr, n, i); } }为什么从n/2 - 1开始往前遍历而不是从0开始也不是从n-1开始这里要理解完全二叉树的性质所有叶子节点本身就已经是满足堆性质的单个节点。对于索引i的节点它的左孩子2*i1和右孩子2*i2有可能越界。当i n/2时它的左孩子索引2*i1 n说明它没有孩子是叶子节点。所以第一个非叶子节点的索引是n/2 - 1。从最后一个非叶子节点开始从右往左、从下往上依次 heapify就能保证在处理某个节点时它的左右子树已经是合法的堆了。这正好满足heapify的前提条件。举个例子数组[4, 10, 3, 5, 1]n 5第一个非叶子节点索引是5/2 - 1 1也就是值为10的节点。先对索引1做 heapify它的孩子是索引3值5和索引4值1最大值是10本身无需交换。然后处理索引0值4它的左孩子索引1值10、右孩子索引2值3最大值是10交换后数组变为[10, 4, 3, 5, 1]接着递归地对索引1再做 heapify此时4的孩子是5和1最大的是5交换后变为[10, 5, 3, 4, 1]。此时堆化完成堆顶是最大值10。建堆的时间复杂度不是O(n log n)而是O(n)。这个结论看起来很反直觉因为从代码上看你要对大约n/2个节点执行heapify而每次heapify是O(log n)相乘不就是O(n log n)吗问题的关键在于并不是所有节点的 heapify 都是 O(log n) 的。绝大部分节点位于树的底部它们下沉的高度很小。精确计算后会发现总的操作次数可以被归约为一个等比数列求和结果是O(n)。这个结论在面试中经常被当作追问考点你能答出“建堆是 O(n)”并不稀奇但能解释清楚为什么才是真正的加分项。3.4 堆排序的完整流程堆排序的思路也很简单直接把无序数组建成一个大顶堆此时堆顶是最大值。把堆顶元素和堆的最后一个元素交换这样最大值就到了数组末尾的正确位置。堆的大小减一对新的堆顶执行一次heapify重新调整为大顶堆。重复第 2 步和第 3 步直到堆中只剩一个元素。C 语言实现void heap_sort(int arr[], int n) { build_heap(arr, n); for (int i n - 1; i 0; i--) { int temp arr[0]; arr[0] arr[i]; arr[i] temp; heapify(arr, i, 0); } }执行过程我用一个具体案例走一遍。假设堆排序开始前的大顶堆是[10, 5, 3, 4, 1]数组长度为5。第一轮交换arr[0]和arr[4]数组变为[1, 5, 3, 4, 10]此时10已经归位。对前 4 个元素做 heapifyarr[0] 1下沉变成[5, 4, 3, 1, 10]。第二轮交换arr[0]和arr[3]数组变为[1, 4, 3, 5, 10]5归位。对前 3 个元素 heapify1下沉变成[4, 1, 3, 5, 10]。第三轮交换arr[0]和arr[2]数组变为[3, 1, 4, 5, 10]4归位。对前 2 个元素 heapify3下沉变成[3, 1, 4, 5, 10]。第四轮交换arr[0]和arr[1]数组变为[1, 3, 4, 5, 10]3归位。堆中只剩一个元素排序结束。最终结果是[1, 3, 4, 5, 10]排序正确。这样走一遍之后你会发现堆排序的核心代码其实非常短难的不是写出来而是理解每一步之后堆的结构发生了怎样的变化。建议你手头有纸的话自己画一棵树跟着每一轮交换后的数组状态重新画一个对应的完全二叉树亲眼看到最大值逐个“浮”到堆顶、然后被“扔”到数组末尾的过程。这个可视化过程一旦建立堆排序就永远不会忘了。4. 两种排序的复杂度对比和工程选型4.1 时间复杂度、空间复杂度和稳定性对照为了让你一屏看清楚我把这两种排序的核心指标整理成一个表算法平均时间复杂度最坏时间复杂度空间复杂度稳定性选择排序O(n^2)O(n^2)O(1)不稳定堆排序O(n log n)O(n log n)O(1)不稳定接着解释一下两个容易困惑的点。为什么选择排序不稳定不稳定是因为选择排序使用了“交换”而不是“移动”。举个例子数组[5a, 5b, 1]其中5a和5b是两个值相等的元素。第一轮扫描找到最小值1和第一个位置的5a交换结果为[1, 5b, 5a]。你看两个5的相对位置从原来的5a在前变成了5b在前相等元素的顺序被破坏了所以不稳定。为什么堆排序不稳定堆排序不稳定有两个原因。一是建堆过程中会破坏原有的相对顺序二是每次把堆顶和末尾元素交换时跨越了很多位置容易把相同元素的相对顺序打乱。最典型的例子是[5, 5, 1]建堆后可能变成[5, 5, 1]或[5, 1, 5]取决于子节点的大小关系排序过程中,交换位置可能跨越多个元素导致相同值的两个5相对顺序改变。所以堆排序天然不稳定这是它的内在属性没有任何实现技巧能改变这一点。4.2 数据规模与场景适配分析实际工程中该怎么选我的建议如下。数据量小比如 n 1000选择排序和堆排序都没有优势。这个量级下插入排序反而是更优的选择因为它实现简单、近乎有序时效率高、且稳定。选择排序唯一的优势在于交换次数少如果你的数据是大型结构体交换开销远大于比较开销那么选择排序可以考虑但这种情况场景比较罕见。数据量大且需要原地排序堆排序是很稳的选择。它不需要额外空间最坏情况也能保证O(n log n)。相比之下快速排序虽然平均性能也很强但有O(n^2)的最坏情况而且实现不当容易递归过深。如果你的系统对最坏情况时间有硬性要求堆排序比快速排序更让人安心。需要稳定性这两种都不能用直接考虑归并排序或插入排序。实时系统或嵌入式环境堆排序的O(1)空间复杂度非常友好。但要注意它的访问模式是跳跃式的父节点和孩子节点跨度大在缓存友好的场景下表现不如快速排序。这属于“理论上最优但不一定是实际最快”的典型例子。如果你不是在做操作系统内核或者特殊嵌入式任务日常业务开发里库函数内置的qsort或std::sort基本就够了不必自己手写堆排序。4.3 一个实际案例优先队列中的应用堆排序在日常开发里最广为人知的应用其实是优先队列。很多场景下我们并不需要对整个数组排序只是反复需要“当前最大或最小的元素”比如操作系统的任务调度、Dijkstra 最短路径算法、Top K 问题。这些场景如果用“每次全量排序”的思路做效率不堪设想用“维护一个堆只取堆顶”的思路做就能把每次取值的开销压缩到O(log n)。我曾经在项目中遇到一个实时推荐场景需要从几十万个候选物品中不停选出当前得分最高的物品但候选物品的得分会动态更新。这时候用堆排序的变体——索引堆或带位置映射的堆——就能高效处理更新操作。当然这是后话了但如果你能把堆排序的原理吃透在这个基础上去理解优先队列和索引堆会顺畅很多。5. 常见问题排查与实操心得5.1 写选择排序和堆排序时最容易犯的错问题一选择排序的比较条件写反了。很多人会写成if (arr[j] arr[min_idx])这样一来找的就不是最小值而是最大值了排序结果方向直接反。排查办法很简单打印出每一轮的min_idx和交换后的数组核对是否符合预期。问题二堆排序的 heapify 边界条件缺失。经常有人把if (l n)漏掉或者把n传成整个数组长度而不是当前堆的大小。堆排序里堆的规模是动态缩小的如果你在每一轮都传入原始n那已经被交换到数组末尾的“乱序元素”就会再次参与堆化导致排序出错。这是堆排序最隐蔽的 bug肉眼很难看出来。建议你在写完后专门用逆序数组测试一下如果结果顺序不对优先检查这一步。问题三建堆起始索引不对。有些人会从n-1开始向前遍历这样做也能得到正确的堆但效率低了下因为你对所有叶子节点都做了一次无用的 heapify。问题倒是不致命但会被面试官追问“为什么从 n/2 - 1 开始”回答不上来就容易减分。问题四数组索引从 0 还是从 1 开始。很多教材为了公式简洁习惯用从 1 开始的索引描述堆父节点是i/2孩子是2i和2i1但 C 语言实际实现是 0 基索引左右孩子是2i1和2i2。如果你照着伪代码抄很容易算错下标。我用过最笨也最有效的方法在自己代码里注释几行“索引 0 的左右孩子是 1 和 2索引 1 的孩子是 3 和 4”防止自己每次都要重新推导。5.2 面试和考试中的追问点总结从热词“clrs 选择排序循环不变量证明”也能看出来很多人是被教材里的严谨证明折磨过的。我建议你掌握下面这组常见追问基本能覆盖大多数面试场景选择排序是稳定的吗为什么举一个反例。选择排序的最好时间复杂度和最坏时间复杂度是多少为什么无法优化堆排序为什么不稳定建堆的时间复杂度是多少推导一下。heapify 的时间复杂度是多少什么时候调用堆排序和选择排序的关系是什么如果要找第 k 大的元素应该怎么做更高效对最后一道题的提示完整排序是O(n log n)但如果只需找出第k大的元素维护一个大小为k的小顶堆遍历一遍数组比当前堆顶大就替换并堆化时间复杂度是O(n log k)。这个思路就是堆排序思想在实际问题中的延伸能答出来会让面试官觉得你真的理解了堆的精髓。5.3 我的实操建议学排序算法我一直推荐的方法是在纸上手推一遍完整流程再在电脑上实现一遍再故意改错几个地方看结果会变成什么样子。手推能建立直觉实现能检验理解故意改错能帮你排查边界问题。这个方法适用于所有算法但对选择排序和堆排序尤其有效因为这两个算法的数据流比较直观出错时的现象也比较明确。另外我发现在写堆排序代码的时候统一使用“下沉”函数名sift_down比使用“堆化”heapify更容易减少误解因为堆化的含义在不同教材里略有差异。墙裂建议你在自己的代码模板里固定一个命名习惯这会让你在快速编码时减少认知负担。这两类排序虽然基础但它们是理解许多高级数据结构优先队列、索引堆、Dijkstra 优化等的地基。把地基打牢后面再往上盖楼你会走得更稳。

选择排序到堆排序：从O(n²)到O(n log n)的进阶之路

相关推荐

SpringBoot+Vue疫情防控管理系统：从需求到部署的全栈开发详解

Oracle EBS总账外币业务全攻略：汇率设置、期末重估与月结避坑指南

CMap药物重定位分析：从基因表达签名到机制可视化

更多资讯

Trae 的 IDE 模式与 SOLO 模式 UI 布局镜像对称：从 TaoToken 统一 Key 看两种人机协作范式的配置差异

Kimi-K2.5走上了一条邪修之路：用MoE+Agent Swarm把WebGL/SVG渲染玩出花，TaoToken统一Key接入实测

Sky Hackathon力作：揭秘多角色智能朗读语音系统——让文字开口讲故事！

Codex 上手很简单，真正难的是知道什么时候不该用它：TaoToken 统一 Key 下的 AI 编程助手选型边界

GitHub 13 万星爬虫神器 Firecrawl，彻底免 Key 接入全网数据：把 MCP endpoint 改到 TaoToken

前端 H5 实战

今日更新

45个经典Linux面试题：从命令到网络排障的完整考点解析

SAP生产预留实战指南：MB21/MB23/MB25协同与MRP集成

编译原理实验：递归下降分析器消除左递归与避坑指南

本周精选

如何彻底离线使用 Laya-CoreML：Hugging Face 下载、缓存机制与 local_files_only 详解

基于1Panel 部署MySQL MCP 服务：TaoToken 统一 Key 接入与 config.toml 配置实战

崇州园区营销网站建设避坑指南：5大注意事项保备案安全

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？