1. 每天二十分钟的算法课为什么会先拿选择排序开刀很多朋友问过我一个问题你说“每日一算法”第一道题为什么不是二分查找不是链表反转偏偏是看起来最没技术含量的选择排序我的回答很简单因为选择排序是唯一一个从第一行代码起就强制你理解两个核心概念的算法——循环边界和区间维护。别的排序你一上来可以背模板但选择排序背不了它的逻辑太直观了只要理解一遍你手上就多了一把衡量所有其他排序的尺子。这个系列我计划连续更新三个月定位是给有一定编程基础、但没系统学过算法的同学准备的。选排序算法作为起点是因为它在时间复杂度上是最朴素的O(n²)级别实现路径最短但能牵扯出的知识点却一点都不少稳定性、原地算法、比较次数与交换次数、部分排序优化……后面再学冒泡、插入、归并、快排甚至堆排序你都能站在选择排序的肩膀上去理解它们。2. 手推整轮选择排序把“最小的挑出来丢前面”做到位2.1 核心思想每一轮锁定一个最终位置选择排序的思路用一句话说就是在未排序的区间里找出最小的元素把它放到这个区间的起始位置然后把区间起始位置向后挪一位重复操作直到整个数组有序。这句话看起来跟冒泡很像但有一个本质区别冒泡排序是“相邻元素两两比较大的慢慢往后浮”一趟内可能发生很多次交换选择排序是“每轮只找最小值的下标找到后最多交换一次”。这个区别直接影响了两种算法的性能画像后面我会具体算这笔账。我用一个具体例子手推一遍。假设有一个数组[29, 10, 14, 37, 13]第1轮i0处理区间是下标0到4先假设最小元素在下标0也就是29。从下标1开始逐个比较10小于29更新最小下标为114大于10不动37大于10不动13大于10且小于29但仍大于10所以最小下标保持为1。本轮结束最小下标是1对应元素10。将下标0的元素29与下标1的元素10交换数组变成[10, 29, 14, 37, 13]。此时位置0已经确定它就是整个数组的最小值以后不再参与任何比较。第2轮i1处理区间是下标1到4数组当前为[10, 29, 14, 37, 13]只看[29, 14, 37, 13]。假设最小值在29下标1从下标2开始比较14小于29更新最小下标为237大于14不动13小于14更新最小下标为4。本轮最小下标是4对应元素13。把29与13交换数组变成[10, 13, 14, 37, 29]。此时位置1确定它是剩余区间的最小值13。第3轮i2处理区间是下标2到4当前[10, 13, 14, 37, 29]只看[14, 37, 29]。假设最小值在14下标2从下标3开始比较37大于14不动29大于14不动。最小下标就是2元素14已经在正确位置上不需要交换。位置2确定。第4轮i3处理区间是下标3到4当前[10, 13, 14, 37, 29]只看[37, 29]。37与29比较最小下标更新为4。交换37与29数组变成[10, 13, 14, 29, 37]。位置3确定最后一个位置4自然有序排序结束。5个元素只需要4轮最后一个元素不用处理因为当剩下两个元素时处理完前一个后一个的位置也就自动确定了。这个“n-1轮”的结论很多人写代码的时候会记错成n轮后面我会在踩坑环节专门讲。2.2 代码实现Python与C的两种写法理解了手推过程代码就只是把手动步骤翻译成循环。我用最直白的Python写一个def selection_sort(arr): n len(arr) for i in range(n - 1): # 只需要 n-1 轮 min_idx i # 假设当前区间第一个元素最小 for j in range(i 1, n): # 在剩余区间里找真实的最小值下标 if arr[j] arr[min_idx]: min_idx j if min_idx ! i: # 最小值不在当前位才交换 arr[i], arr[min_idx] arr[min_idx], arr[i] return arrC版本也很简单这里我用模板函数写一版方便直接处理不同数据类型#include vector template typename T void selectionSort(std::vectorT arr) { size_t n arr.size(); for (size_t i 0; i 1 n; i) { size_t minIdx i; for (size_t j i 1; j n; j) { if (arr[j] arr[minIdx]) { minIdx j; } } if (minIdx ! i) { std::swap(arr[i], arr[minIdx]); } } }两个版本的核心逻辑完全一致外层循环控制“当前要确定哪个位置”内层循环在未排序区间中做遍历找最小。注意我在交换前加了一个判断if min_idx ! i这个不是性能优化而是为了减少无意义的自我交换——虽然两个相同的变量交换也不会有问题但加了这层判断调试时看到的是更干净的轨迹。2.3 稳定性的坑相等元素会被“悄悄换位”选择排序有一个容易被忽视的性质它是不稳定排序。什么意思我用一个经典例子演示一下。注意看这个数组[5, 8, 5, 2]我故意让两个5同时出现。第一轮找最小值时从下标1开始比较8大于5不动第二个5与第一个5相等所以也不会更新最小下标最后遇到2更新最小下标为3。交换下标0的5和下标3的2之后数组变成[2, 8, 5, 5]看到问题了吗原来的第一个5我用红色标记的那个被换到了下标3而第二个5落在了下标2。两个等值元素的相对位置发生了变化——这就是“不稳定”的定义。如果排序对象只是数字这种不稳定没有影响。但如果排序的是对象比如按成绩排序的学生列表成绩相同的两个学生原本按姓名排列的顺序被打乱了这在某些业务场景下就是不可接受的。为什么选择排序会不稳定根源在于“跨度大的交换”你拿很远位置上的元素与当前位元素交换跳过了中间所有等值元素自然可能越过它们的相对顺序。3. 复杂度背后的取舍选择排序为什么“稳但是慢”3.1 无论数组是否有序比较次数都是铁打的O(n²)这是选择排序最“耿直”的地方它的比较次数不随输入数据的有序程度而改变。第一轮要比较n-1次第二轮n-2次第三轮n-3次……累计下来[ (n-1) (n-2) \dots 1 \frac{n(n-1)}{2} ]也就是说对于一个长度为n的数组无论它原本是乱的、反序的、还是已经有序的选择排序都比较固定规模的次数。这一点跟冒泡排序有本质区别——冒泡排序在数组基本有序时可以通过“本轮没有发生交换就提前结束”来大幅减少比较而选择排序因为每一轮必须确认“剩余区间的真正最小值在哪里”无法跳过任何一次比较。所以它的时间复杂度是稳定的O(n²)最好情况、最坏情况、平均情况全部一样。用大O记号写出来就是情况时间复杂度最优情况数组已有序O(n²)平均情况O(n²)最坏情况倒序O(n²)很多人觉得“数组有序时算法应该快一点”这在选择排序身上不成立。有序只能让它少做交换不能让它少做比较。3.2 交换次数少比冒泡强在“元素搬运”成本相比之下选择排序在交换次数上的表现相当优秀。每一轮最多发生一次交换整个排序过程最多交换n-1次如果最小值恰好就在当前位置那一轮连交换都省了。冒泡排序的交换则频繁得多最坏情况下每轮都要冒泡总交换次数是O(n²)级别。假设数组长度是10000选择排序最多交换9999次而冒泡排序可能交换接近5000万次。这个差距在实际系统中非常明显。如果数组里存放的不是简单的整数而是体积庞大的对象或结构体交换一次意味着内存中挪动大量数据此时交换次数少就成了压倒性的优势。我当年在学校机房用Turbo C写学生管理系统每条记录几百个字节排序一万条数据选择排序能明显感觉到比冒泡快原因就在这。空间复杂度方面选择排序只借助一个临时变量做交换额外空间是O(1)属于原地排序。这一点在内存受限的嵌入式环境下很宝贵。3.3 与其他排序算法的横向对比它站在哪个位置我把选择排序放进排序家族里做个对照这样更容易理解它的定位排序算法平均时间复杂度最坏复杂度空间复杂度稳定性选择排序O(n²)O(n²)O(1)不稳定冒泡排序O(n²)O(n²)O(1)稳定插入排序O(n²)O(n²)O(1)稳定归并排序O(n log n)O(n log n)O(n)稳定快速排序O(n log n)O(n²)O(log n)不稳定堆排序O(n log n)O(n log n)O(1)不稳定注意这里每一列都不是“越好越好”而是要结合场景看。比如插入排序在数组基本有序时效率极高几乎是O(n)归并排序时间上很稳但要付出O(n)的辅助空间快速排序虽然有最坏O(n²)的风险但实践中平均表现优秀。选择排序在这张表里的角色是时间上不算快但交换代价极低、空间占用极小、实现逻辑极简。如果说排序算法是一个工具箱选择排序就是那把不吃保养、不容易失灵的老扳手——不一定最高效但一定可靠。4. 不要小看“笨”算法选择排序的真实应用场景与变种4.1 什么时候该用它数据量小和交换代价高的场景很多人学完O(n²)级别的排序后会产生一种错觉这些算法除了考试没有任何价值。实际上工程里处处需要排序大型排序框架的“底座”往往就是简单排序。举个很典型的场景当数据量小于某个阈值时高级排序算法会“降级”用插入排序或选择排序。Java的Arrays.sort对长度小于47的数组用的是插入排序很多内核实现同理——因为递归切分小数组带来的函数调用开销比直接O(n²)暴力排序还要大。选择排序在小数组上虽然不如插入排序那么快插入排序在接近有序时表现更好但它没有“移动元素腾位置”的额外操作对数组实现来说反而更直接。另一个场景是记录体积大、交换成本高。回想我在学校写的那个学生管理系统每条记录几百字节如果用冒泡去频繁交换光内存拷贝就够呛用选择排序每轮只做一次交换总交换次数线性增长这就把“比较”和“搬运”解耦了——比较是CPU操作便宜搬运是内存操作贵。再有就是嵌入式场景。单片机内存常常只有几十KB一次完整排序可能连临时数组都开不出来这时候原地排序是硬性要求。选择排序代码量小逻辑简单不容易引入隐藏bug对讲求稳定性的嵌入式固件来说反而是个稳妥选择。4.2 双向选择排序一次循环同时找出最大值和最小值觉得普通选择排序每轮只确定一个位置太浪费可以做个简单的优化每一轮同时找最小值和最大值分别放到未排序区间的两端这样每轮能确定两个元素的位置总轮数减少一半。def double_selection_sort(arr): n len(arr) left, right 0, n - 1 while left right: min_idx left max_idx left for i in range(left, right 1): if arr[i] arr[min_idx]: min_idx i if arr[i] arr[max_idx]: max_idx i # 最小值放到左端 arr[left], arr[min_idx] arr[min_idx], arr[left] # 如果最大值本来在 left 位置上面交换后它被移走了要修正索引 if max_idx left: max_idx min_idx # 最大值放到右端 arr[right], arr[max_idx] arr[max_idx], arr[right] left 1 right - 1 return arr这个变种有个经典大坑交换最小值之后最大值的位置可能发生变化。如果最大值刚好在left位置第一轮交换会把最大值和最小值对调此时max_idx就失效了必须把它指向被交换后的位置也就是min_idx变成了新的max_idx位置。这个坑我踩过不止一次调试了半小时才发现是索引修正的问题。双向选择的比较次数仍然是O(n²)常数上减少了大约一半实际测试下来数据量在几万以内时感觉更明显再大就无所谓了反正O(n²)的天花板摆在那。4.3 堆排序与锦标赛排序选择排序的精神续作如果你理解了选择排序的核心是“每轮从剩余元素里找最小”那你就已经握住了一把理解更高级算法的钥匙堆排序本质上就是选择排序的升级版。选择排序慢在“每次找最小都要从头扫一遍”扫描成本O(n)要扫n轮所以是O(n²)。堆排序做了一个关键优化用一个二叉堆维护剩余区间的数据取最小值的时间降为O(log n)所以总复杂度降为O(n log n)。跟选择排序一样堆排序也是不稳定的原地排序。如果当年你学堆排序时觉得“诶这思路怎么似曾相识”恭喜你这不是巧合它就是选择排序的亲儿子。类似的还有锦标赛排序也叫树形选择排序把找最小值的比较过程组织成一颗锦标赛树第一轮找最小值需要n-1次比较后续每轮只需O(log n)次。代价是额外空间多一些。从选择排序这个原点出发你顺着“如何更快地找最小值”这条线走下去就能自然推导出half the排序算法家族的进化史。5. 那些年我在选择排序上踩过的坑排查链路与避坑清单5.1 内外层循环边界写错导致越界或漏排这是初学者最容易犯的错误。我见过几种典型写法# 错误写法1外层循环到 n for i in range(n): # 当 i n-1 时内层 range(n, n) 为空没问题 # 但多跑一轮没有任何意义 # 错误写法2内层循环从 0 开始 for j in range(0, n): # 这样会把已经排好的部分重新考虑进去逻辑错误推荐的外层边界是range(n - 1)。为什么不是range(n - 2)因为当i走到n-2时区间只剩两个元素下标n-2与n-1。这一轮内层循环会比较这两个元素完成排序后下标n-1自然就是最大的所以没有必要再为最后一个位置单独跑一轮。内层起始位置是i 1这很重要。如果从i开始数组的第i个元素会跟自己比较一次不影响结果但浪费一次比较。如果从0开始会把已排定的前缀区间重新扫一遍虽然不影响最终结果已排定的最小值不会被替换掉但白白增加了比较次数而且语义就完全错了。5.2 min_idx忘记更新排序结果永远是原数组这个问题看起来蠢但真的会反复出现。尤其是当你习惯用“找最大值”写内层循环时容易漏掉更新下标def wrong_selection_sort(arr): n len(arr) for i in range(n - 1): min_idx i for j in range(i 1, n): if arr[j] arr[min_idx]: pass # 忘记赋值min_idx j arr[i], arr[min_idx] arr[min_idx], arr[i] return arr这段代码跑完数组一点变化都没有。因为min_idx永远等于i每轮都在做自我交换。排查这种问题的建议是先打印每一轮min_idx的值再打印交换后的数组两步就能定位。我自己总结的调试诀窍是给选择排序加一个“轮次日志”像这样def selection_sort_with_log(arr): n len(arr) for i in range(n - 1): min_idx i for j in range(i 1, n): if arr[j] arr[min_idx]: min_idx j print(f第{i}轮: 最小元素 {arr[min_idx]} 在位置 {min_idx}) arr[i], arr[min_idx] arr[min_idx], arr[i] print(f交换后: {arr}) return arr眼睛能看到的执行轨迹比任何调试工具都直观特别适合学习阶段。5.3 稳定性问题引起的业务Bug一个真实项目经历我之前在做一个简易比赛成绩表时用选择排序按成绩倒序排选手列表结果发现两组成绩相同的人每次跑出来的先后顺序不一样。第一反应是“排序函数写随机了”排查了很久才发现问题出在校验码使用的对象顺序上。比赛系统里每个选手对象包含姓名、组别、成绩。后台要求成绩相同的选手按报名时间先后显示。我用选择排序实现按成绩降序它确实把成绩排好了但两个成绩同为80分的人由于选择排序的不稳定性在排序过程中数组里的相对顺序被打乱了——分组校验时后台一直按“原始顺序”比对两边就对不上了。最后的解决方案也很简单对这类需要保持顺序的场景改用稳定排序算法比如归并排序或插入排序或者在排序前先把原始顺序存入对象字段作为次级排序键。这个案例给我的教训是学排序时不能只背“稳定不稳定”这个结论要真的想清楚不稳定意味着什么样的业务影响。5.4 找不到那个“提前终止”的开关刚学完冒泡的人接触选择排序常常会下意识地找“这轮没交换就可以提前退出”的优化点。但选择排序没有这个退路原因前面已经说过每轮必须完整扫描剩余区间才能确认最小值一轮不交换只能说明最小值恰好在首位不能说明数组整体有序。举个例子数组[1, 2, 3, 5, 4]第一轮找最小发现1已经在正确位置不交换。如果据此认为数组有序直接退出那后边的5和4就永远不会被纠正。这个理解上的坎一定要迈过去否则你会在选择排序的实现里写出一个看似合理实则错误百出的提前退出分支。6. 从选择排序出发我的每日算法学习路径建议6.1 把复杂度分析当成第一优先学动作先学解剖学。我的建议是每学一个算法先不看代码实现先在纸上把三个问题写清楚这个算法的最坏时间复杂度是多少空间复杂度是多少是否稳定记住答案之后再问自己一句为什么以选择排序为例如果被问“为什么比较次数固定”你能回答出“因为每一轮必须遍历剩余区间才能找到全局最小值”这个理解就到位了。这样的理解比背十遍代码都管用——因为它能迁移。后来你学堆排序时“为什么堆化的比较更少”就变成同一个问题的子问题堆把“找最小”从O(n)降到了O(logn)。6.2 刷题与面试中选择排序会怎么考不夸张地说我在面试中至少遇到过三次和选择排序相关的题目一种是直接手写排序最常见的是“写一个原地排序不要用库函数”这时候写选择排序是最稳的因为代码逻辑简单没有递归没有辅助数据结构几乎不可能写崩。一种是变种题比如“求数组中第k小的元素”。暴力解法是完整排序再取下标进阶解法是用堆最优解法是快速选择。但从暴力解法出发你能想到的中间形态就是——跑k轮选择排序第k轮结束时位置k-1上的元素就是第k小的元素。这个思路虽然不够快但在题目要求“只能交换相邻元素”或“限制内存”时它可能就是你唯一能写出来的解法。还有一种是关于数据流的场景比如“如何在不断插入新数据的场景下维护前10大元素”。如果数据总量少选择排序的思路完全够用数据量大时你应该换成堆。但核心理解路径是一样的选择排序让你理解“维护K个最大元素”的朴素做法堆排序则是它的优化形态。6.3 每日一算法的节奏安排与休息日最后分享一点我自己的坚持经验。每天只投入20到30分钟三周可以把这个系列的核心排序算法过完重点是不要贪多。一天吃透一个算法比一天看五个算法然后全部忘记有价值得多。我从这个项目里收获最大的其实不是记住了多少算法的实现而是养成了一个拆解问题的习惯拿到问题先问复杂度、问边界条件、问稳定性再动手写代码。这个习惯远比我背下来的那些模板值钱。如果你正在读这篇文章我建议你拿纸笔把今天的数组手推一遍在纸上画完交换过程再打开编辑器敲一遍代码。手推这一步不能跳因为它建立的是对循环边界的肌肉记忆。真正写代码时边界条件要靠这种记忆来兜底。明天我会在这个系列里讲插入排序。如果你已经把选择排序的代码写熟练了到时候你会看到一个很有意思的对比插入排序在几乎有序的数组上表现惊人而选择排序无论输入如何都保持匀速。同为O(n²)级别吃相同的大O但行为模式完全不同——这正是算法的有意思之处。