1. 引言上篇博客我们聊了插入排序那种像打扑克牌一样把新牌一张张插到合适位置的感觉相信大家还记忆犹新。今天我们换个思路来聊聊另一种同样经典的基础排序算法——选择排序。如果说插入排序是边摸牌边整理那选择排序更像是挑最顺眼的先拿走。它的思路非常直观每一轮都从剩下的元素里挑出最小的那个放到前面去。就像我们在宿舍里整理书架每次都从乱堆里挑出最薄的一本书放到最左边一本一本排好。2. 选择排序的基本思想选择排序的核心思想可以用一句话概括每一轮从未排序区间中选出最小值放到已排序区间的末尾。具体来说假设我们有一个长度为 n 的数组排序过程分为 n-1 轮第 1 轮在全部 n 个元素中找出最小值与第 1 个位置交换第 2 轮在剩下的 n-1 个元素中找出最小值与第 2 个位置交换第 3 轮在剩下的 n-2 个元素中找出最小值与第 3 个位置交换……第 n-1 轮在剩下的 2 个元素中找出最小值与第 n-1 个位置交换。经过 n-1 轮之后最后一个元素自然就是最大值排序完成。2.1 一个直观的比喻想象你在整理一摞试卷要从乱序的卷子里按分数从低到高排好先扫一遍所有试卷找出分数最低的那张放到最上面再从剩下的试卷里找出分数最低的放到第二张的位置重复这个过程直到所有试卷排好。这个过程就是选择排序的生动写照——每次只做一件事找到当前最小的放到它该去的位置。2.2 动图3. 图解选择排序过程为了让大家看得更清楚我们用一个具体例子来走一遍完整流程。假设数组为[5, 3, 8, 1, 2]长度为 5需要 4 轮排序。第 1 轮在[5, 3, 8, 1, 2]中找最小值1与第 1 个元素5交换[1, 3, 8, 5, 2]第 2 轮在[3, 8, 5, 2]中找最小值2与第 2 个元素3交换[1, 2, 8, 5, 3]第 3 轮在[8, 5, 3]中找最小值3与第 3 个元素8交换[1, 2, 3, 5, 8]第 4 轮在[5, 8]中找最小值5与第 4 个元素5交换位置不变[1, 2, 3, 5, 8]排序完成可以看到每一轮结束后前面就多了一个已经排好序的元素。下面是整个过程的流程图否是是否输入待排序数组i 0在 i 到 n-1 区间找最小值下标 minIndexminIndex 是否等于 i?交换 arr[i] 与 arr[minIndex]无需交换i i 1i n-1?输出排序后数组4. 代码实现voidSwap(int*x,int*y)//交换两数据位置{inttemp*x;*x*y;*ytemp;}voidSelectSort(int*arr,intn)//简单选择排序{if(arrNULL||n1)return;//1.核心思想是在未排序数据中选出最大/小的值并与待交换数据交换位置与插入排序的差别之一就是插入排序比较过程中需要将元素后移直到遇到合适位置插入// 选择排序是先比较完然后将单趟最值与某值交换位置因此同样需要区分已排序和未排序区域for(inti0;in-1;i)//同样的防止越界{intmini;//2.定义当前最小值的位置for(intji1;jn;j)//3.寻找未排序数据中的最小值{if(arr[j]arr[min]){minj;//4.如果有就定义新的最小值的位置}}//5.比完以后得到本次最小值的位置与原本的最小值交换位置if(min!i){Swap(arr[min],arr[i]);}}}4.3 代码要点总结外层循环i表示已排序区间的末尾位置从 0 到 n-2内层循环j负责在未排序区间中扫描记录最小值下标min每一轮最多交换一次这是选择排序与冒泡排序的重要区别冒泡可能一轮交换多次。5. 复杂度分析5.1 时间复杂度最好情况O(n²)。即使数组已经有序内层循环依然要完整扫描未排序区间无法提前终止。最坏情况O(n²)。无论数据怎么分布比较次数都是固定的。平均情况O(n²)。具体来说比较次数恒为n(n-1)/2与数据初始顺序无关交换次数最多为n-1次每轮最多一次。5.2 空间复杂度空间复杂度O(1)只需要一个临时变量用于交换属于原地排序算法。5.3 稳定性分析选择排序是不稳定的。举个例子数组[5a, 5b, 1]两个 5 用 a、b 区分第一轮找到最小值1与第一个5a交换得到[1, 5b, 5a]此时两个 5 的相对顺序发生了改变。这一点在面试中经常被问到大家要特别注意。有同学会问如果把内层循环的比较条件从改成能否让选择排序变稳定答案是不能。选择排序的不稳定性根源在于交换操作而不是比较条件。即使你用让内层循环在遇到相等元素时也更新min下标也只是改变了选哪个相等元素的策略但交换本身依然可能破坏相对顺序。以数组[5, 6, 5, 0, 2, 0, 3]为例给相同元素编号[5a, 6, 5b, 0a, 2, 0b, 3]第 1 轮找最小值0a与第 1 个元素5a交换得到[0a, 6, 5b, 5a, 2, 0b, 3]。此时5a被换到了5b的后面两个 5 的相对顺序已被破坏而这一轮0a和0b的相对顺序反而保住了。第 2 轮在[6, 5b, 5a, 2, 0b, 3]中找最小值0b与第 2 个元素6交换得到[0a, 0b, 5b, 5a, 2, 6, 3]。这一轮0b又被换到了0a的后面两个 0 的相对顺序也被破坏了。可以看到即使能保证某一组相同元素的相对顺序也无法同时保证所有组的相对顺序。因为每一轮交换都会把当前最小值从后面直接跨越到前面跨越过程中会越过所有其他元素——包括与它值相同的元素。用时相等元素不会被选中相对顺序靠运气用时相等元素会被选中选最后一个虽然可能保住某一组的顺序但其他组的顺序照样会被交换破坏。所以只要选择排序采用交换来实现它就注定不稳定。要让选择排序变稳定必须改用插入的方式把最小值前面的元素整体后移再把最小值放进去而不是交换——但那样它就不再是经典的选择排序了。用循环不变量再证一遍上面的例子已经足够直观但如果你想让论证更严谨可以用循环不变量来证明无论比较条件用还是选择排序都不可能是稳定的。先回顾一下选择排序外层循环的不变量循环不变量在第i轮开始前即i次交换完成后数组的前i个位置已经排好序且它们恰好是原数组中最小的i个元素剩余n-i个元素仍在未排序区间[i, n-1]中。这个不变量在初始化i0时前 0 个元素自然有序、保持每轮把未排序区间的最小值放到i位置、终止in-1时前n-1个元素有序最后一个自然最大三个阶段都成立所以它保证了排序的正确性。但注意这个不变量只约束了哪些值被放到了前面完全没有约束相同值的相对顺序。它只保证前i个位置是最小的 i 个元素至于这些相等元素谁先谁后不变量一概不管。现在我们来证明不稳定。考虑任意一轮i设未排序区间[i, n-1]中存在两个相等的元素x和y且x在y的前面x的下标更小。这一轮要选出的最小值记为m分两种情况情况一m就是x或y本身。假设选中的是y即y是未排序区间的最小值且x与它相等。交换后y被放到位置i而x留在原地。由于x原本在y前面交换后y跑到了x的前面两者相对顺序被破坏。情况二m是另一个更小的元素。此时m会被交换到位置i而x、y的相对位置在这一轮保持不变。但注意这一轮没有破坏它们不代表后面不会破坏。在后续某一轮i当x或y成为未排序区间的最小值被选中并交换到前面时就会发生情况一破坏它们的相对顺序。换句话说只要存在两个相等的元素且它们不是同一轮被同时选中选择排序每轮只选一个最小值永远不可能同时选中两个那么迟早有一轮会把其中一个跨越到另一个的前面。这正是选择排序交换实现的本质缺陷。所以结论是循环不变量只能证明选择排序排对了却无法证明它排得稳。稳定性需要的是相等元素相对顺序不变这一条额外约束而选择排序的交换操作天然无法保证这一点。这也解释了为什么面试中稳定性和正确性是两个独立的问题——一个算法可以正确但不稳定。6. 选择排序 vs 插入排序上篇我们学了插入排序这里把两者放在一起对比方便大家记忆对比维度选择排序插入排序基本思路每轮选最小值放前面每轮把新元素插入到合适位置最好时间复杂度O(n²)O(n)已有序时最坏时间复杂度O(n²)O(n²)交换次数最多 n-1 次最多 n(n-1)/2 次稳定性不稳定稳定适用场景交换成本高、数据量小数据基本有序、数据量小小贴士如果交换两个元素的代价很大比如元素是复杂对象选择排序的交换次数少反而可能比插入排序更合适但如果数据基本有序插入排序凭借提前终止的优势会快很多。7. 常见面试考点选择排序虽然简单但面试官经常从它入手考察基础功底手写代码要求在白板上写出完整实现注意边界条件i n-1和j n。稳定性判断能举出反例说明它不稳定。复杂度推导能说出比较次数恒为n(n-1)/2。优化思路能否想到同时找最大值和最小值的优化版本每轮找最大和最小可减少一半轮次。与其它排序对比能清晰说出选择、插入、冒泡三者的区别。8. 总结选择排序是算法入门路上绕不开的一块基石。它的思想朴素而优雅——每次只做一件最简单的事重复 n-1 次就能完成整个排序。回顾一下今天的关键点核心思想每轮从未排序区间选最小值放到已排序区间末尾时间复杂度无论好坏都是 O(n²)空间复杂度O(1)原地排序稳定性不稳定与插入排序相比交换次数更少但无法利用数据的有序性。下篇博客我打算写冒泡排序把这三个 O(n²) 的基础排序放在一起做个对比