★ FEATURED ARTICLE 初学排序算法时很多人第一个接触的不是快排也不是归并而是选择排序。理由很简单它最贴近人类本能——在一堆数里挑最小的放到最前面再挑剩下里面最小的放到第二个位置如此反复。听上去没有一丁点门槛。但恰恰是这种“一眼看懂”的算法等真正动手写代码、分析复杂度、回答面试官追问的时候才会发现里面有不少容易忽略的细节。这篇文章把选择排序从思路、代码、稳定性、复杂度到变体全部拆开讲适合正在学数据结构的初学者也适合准备算法面试、想补排序基础的人。1. 选择排序到底在“选”什么先弄懂定位与交换的分工直接给结论选择排序每一轮只做两件事——在未排序区间里定位最小值的位置然后把它交换到未排序区间的最前面。注意“定位”和“交换”的分工这是理解这个算法的关键也是它和冒泡排序最本质的区别。1.1 用一组数字走一遍完整过程假设数组初始状态是[29, 10, 14, 37, 13]总共5个元素。第一轮未排序区间是下标0到4全数组。从头扫描找到最小值10它在下标1。把下标0的29和下标1的10交换数组变成[10, 29, 14, 37, 13]。此时下标0已经是全局最小值接下来不用再管它。第二轮未排序区间是下标1到4即[29, 14, 37, 13]。在剩余部分里找最小值13它在下标4。把下标1的29和下标4的13交换数组变成[10, 13, 14, 37, 29]。第三轮未排序区间是下标2到4即[14, 37, 29]。找最小值14它本来就在下标2所以不需要交换数组不动。第四轮未排序区间是下标3到4即[37, 29]。找最小值29在下标4把下标3的37和下标4的29交换数组变成[10, 13, 14, 29, 37]。到第五轮只剩下一个元素不需要再排。总共就做了4轮有效工作。这个例子告诉我们一件事选择排序的比较次数和数组初始顺序完全无关该比多少次就比多少次。这一点在后面复杂度章节会重点说。1.2 为什么说它是“定位排序”不是“比较排序”冒泡排序的重点在“交换”它的逻辑是一趟趟地把大的元素往后推比较和交换发生在扫描过程中。插入排序的重点也在“比较和移动”它拿着当前元素向前找插入点。而选择排序的重点在于“找到最小值的位置”整个内层循环的使命只有一个——更新最小值所在的下标。这句话听起来像文字游戏但对代码编写有直接影响。你可以观察一个典型写法内层循环里只做if (a[j] a[minIndex]) minIndex j;不做任何交换。真正的交换是在内层循环结束之后才执行一次。也就是说无论这轮扫描遇到多少个比当前最小值更小的元素都只是更新下标数据本身在扫描期间纹丝不动。这种“先定位、后交换”的设计带来两个直观好处。第一交换次数被压到了理论最低每一轮最多交换一次整体最多 n-1 次交换。第二逻辑容易验证你完全可以把“找最小值”这一步独立抽出来对单测确认下标找对了再去看交换有没有问题。实际教学和工程调试里这个特点非常省心。2. 代码拆解标准实现、容易写错的“变异版”、Python参考算法思路讲完了必须落到代码。我见过很多初学者在“写对”这个层面上反复挣扎问题基本都出在循环边界和交换时机上。2.1 标准C语言实现与边界设计解析void selection_sort(int a[], int n) { for (int i 0; i n - 1; i) { int minIndex i; // 假设当前首元素就是最小值 for (int j i 1; j n; j) { // 从 i 的下一个位置开始扫描 if (a[j] a[minIndex]) { minIndex j; // 发现更小值仅更新下标 } } if (minIndex ! i) { // 最小值不在原位才交换 int tmp a[i]; a[i] a[minIndex]; a[minIndex] tmp; } } }三个地方需要特意解释。外层循环为什么是i n - 1而不是i n因为当i n - 2时内层循环会处理最后一个未排序位置n - 1把这轮之后数组就已经有序。等到i n - 1数组只剩最后一个元素没有必要再选一遍它天然处于正确位置。所以外层跑 n-1 轮就够了。内层循环为什么从j i 1开始因为a[i]是当前未排序区间的第一个元素我们已经假设它是最小值扫描只需要从它后面开始。如果从i开始虽然不影响正确性但会让minIndex先和自己比一次属于毫无意义的冗余比较。交换前为什么要加if (minIndex ! i)因为如果这一轮找到的最小值恰好就在当前首元素的位置交换自己和自己没有任何意义。这个判断是个小优化也避免了一些调试时让人困惑的“我明明没动它它怎么变了”的问题。2.2 一个常见的“变异版”边找边换问题出在哪里下面这段代码是很多初学者容易写出来的for (int i 0; i n - 1; i) { for (int j i 1; j n; j) { if (a[j] a[i]) { int tmp a[i]; a[i] a[j]; a[j] tmp; } } }表面上排序结果是对的数组确实能被排成升序但它已经不是标准的选择排序了。问题在于每当发现一个比a[i]小的元素就立刻交换。这会导致元素被反复换来换去最坏情况下交换次数接近 O(n²)而不是标准选择的 O(n)。举个例子数组[5, 4, 3, 2, 1]第一轮i0时这个写法会把 5、4 交换然后把 4、3 交换再把 3、2 交换最后把 2、1 交换一轮下来交换了4次。而标准选择排序第一轮只扫描一遍找到最小值1然后交换一次得到[1, 4, 3, 2, 5]。这种“变异版”的本质是选择排序和冒泡排序的杂交产物它保留了两者各自的缺点——有冒泡的频繁交换也有选择的多次扫描——却丢掉了选择排序“每轮最多交换一次”的核心优点。如果在面试里写出这段面试官很容易判断你对选择排序的理解停留在“看个大概”的层面。2.3 Python版本参考Python 更适合快速验证思路代码和 C 几乎一一对应def 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]: min_idx j if min_idx ! i: arr[i], arr[min_idx] arr[min_idx], arr[i]用 Python 有个额外的好处可以直接用arr[i], arr[min_idx] arr[min_idx], arr[i]这种交换语法不用担心临时变量。但底层逻辑依然不变——先定位后交换。3. 稳定性问题为什么相同元素会被换跑“选择排序不稳定”这句话几乎任何一本教材都会写但很多人只是背结论没真正搞明白“为什么”。这一节用例子把它彻底讲透。3.1 不稳定的完整发生过程稳定性指的是数组中值相等的两个元素在排序完成后相对顺序保持不变。看这个例子[5a, 3, 5b, 2, 8]。我用 5a 和 5b 区分两个值相同的5其中 5a 原本在下标05b 原本在下标2排序前 5a 在 5b 前面。第一轮选择排序在[5a, 3, 5b, 2, 8]中找到最小值2它在下标3。标准流程把下标0的 5a 和下标3的 2 交换数组变成[2, 3, 5b, 5a, 8]。注意看交换之后 5a 跑到了下标35b 还是在下标2。两个值相等的5相对顺序从“5a 在 5b 前”变成了“5b 在 5a 前”。稳定性被打破。3.2 一个小改动能让它变稳定吗这个问题值得认真回答。有一种思路是当a[j] a[minIndex]时才更新minIndex相等不更新。这样在遇到相同值时minIndex会停留在最靠前的那个位置看上去能避免把靠后的相同值换到前面。遗憾的是这个改动只能处理部分情况不能从根上解决问题。回到上面的例子第一次交换发生时被换走的不是“两个5之间的相对位置竞争”而是 5a 和最小值2之间的直接交换。5a 被换到了数组末尾附近5b 却留在原处无论当时怎么选minIndex这轮交换本身就会撕裂相同元素的相对顺序。如果要让选择排序变得稳定需要配合额外的链表结构或者复杂的数组搬移让相同值不被粗鲁的直接交换打乱。这样做实现成本陡增而且复杂度并没有任何改善所以工程上没人会这么做。面试里遇到“为什么它不稳定”能分析到“因为跨距离直接交换会把相同元素的位置关系打断”这个层面就已经很扎实了。4. 复杂度对比选择、冒泡、插入谁在什么场景更划算很多初学者把三种 O(n²) 排序当成差不多的一家人实际上它们的常数因子和敏感特性差别不小。理解这些差别才能在具体场景里做对选型。4.1 选择排序的复杂度拆开看比较次数每一轮都要扫描整个未排序区间第一轮比较 n-1 次第二轮 n-2 次最后一轮1次总比较次数恒定为 1 2 ... (n-1) n(n-1)/2。这个数字和输入数据是否有序没有任何关系。交换次数每一轮最多交换一次如果加上了minIndex ! i的判断最好情况数据已经有序下交换次数为0最坏情况为 n-1。哪怕去掉那个判断交换次数也是严格小于 n 的。所以选择排序的核心特征可以概括为比较次数恒定交换次数极少。这个特征在数据元素个头很大、交换代价远高于比较代价的场景里非常值钱。4.2 三种基础排序横向对比排序算法最好时间复杂度平均时间复杂度最坏时间复杂度比较次数是否受数据影响交换/移动开销稳定性选择排序O(n²)O(n²)O(n²)否恒为 n(n-1)/2少至多 n-1 次交换不稳定冒泡排序O(n)带优化O(n²)O(n²)受数据有序度影响多频繁交换稳定插入排序O(n)O(n²)O(n²)受数据有序度影响中移动次数与逆序对相关稳定这张表里最值得注意的两条信息。第一条冒泡排序和插入排序的比较次数不是固定的。数据越有序它们需要做的比较越少特别是插入排序在近乎有序的数据上可以达到 O(n)而选择排序无论数据多有序都老实巴交地扫描完整趟。这是选择排序的劣势。第二条交换移动次数的差异恰好反过来。选择和插入都是移动次数少的但插入排序的最坏移动量和元素逆序对数量成正比最坏也是 O(n²)选择排序的最坏交换次数也只有 n-1这在“交换一次代价极高”的场景下是决定性的优势。4.3 什么时候选它才划算我实际见过一个典型的适合使用选择排序的场景数组中每个元素都是一个体积较大的结构体比如几百字节的记录而排序依据只是其中某个 int 字段。这时候在内存里交换两个完整结构体的开销非常大。如果直接把结构体指针排个序排序逻辑又没法直接对内存块做随机重排。在这种前提下选择排序每轮只做一次交换的特点就变得很有价值——它能把最坏情况下的写操作次数压到最低。反过来如果排序对象是int[]这种小元素数组或者数据本身已经接近有序就别选选择排序了插入排序明显更好。另外请注意工业级排序框架里不会单独用选择排序做大数组排序它的主要价值在于教学、小规模数据、以及作为堆排序的思维基础。5. 从选择排序长出来的两个变体二元选择与堆排序大O复杂度一样不代表算法就走到头了。选择排序的思路上还能继续做文章最有意义的两个方向是“一轮选两个”和“借助堆结构”。5.1 二元选择排序每一轮同时选出最大值和最小值基本思路是每轮扫描同时维护minIndex和maxIndex然后把最小值交换到未排序区间的左端left把最大值交换到右端right之后left、right--。这样一轮能定下两个元素的终位外层循环从 n/2 轮减到 n/2 轮比较总次数大约从 n(n-1)/2 降到 n(n-1)/4常数因子少了一半。但这个优化隐藏着一个很容易踩的坑最大值和最小值的交换会互相干扰。看这段代码void double_selection_sort(int a[], int n) { int left 0, right n - 1; while (left right) { int min_pos left; int max_pos left; for (int j left 1; j right; j) { if (a[j] a[min_pos]) min_pos j; if (a[j] a[max_pos]) max_pos j; } // 先把最小值放到左端 if (min_pos ! left) { swap(a, left, min_pos); } // 如果最大值原本就在 left它已经被换到了 min_pos 的位置 if (max_pos left) { max_pos min_pos; } // 再把最大值放到右端 if (max_pos ! right) { swap(a, right, max_pos); } left; right--; } }关键在if (max_pos left) max_pos min_pos;这一行。为什么需要它因为第一步交换时如果最大值恰好位于当前区间的左端left它会被当成“临时存放地”换到min_pos那里去。如果不修正max_pos第二步就可能把一个已经不是最大值的元素放到右端。这个细节在笔试手写代码时非常容易漏是二元选择排序最经典的边界陷阱。不过实话实说二元选择排序只是把常数因子减小复杂度依然是 O(n²)。做对性能优化是有意义的但也别期待它能逆袭快排。5.2 堆排序选择排序思路的高级形态选择排序每轮找最小值需要完整扫描一遍复杂度 O(n)所以整个算法是 O(n²)。如果我们能让“找最小值”这个操作变快就能直接提升整个排序算法的效率。堆排序做的事情正是如此先用 n 个元素构建一个堆让最小值或最大值在 O(log n) 时间内被提取出来再通过下沉操作维持堆结构。连续取 n 次最小值总复杂度就是 O(n log n)。从这个角度看堆排序就是选择排序的进阶版它把“线性扫描找最小值”升级成了“对数级维护堆顶”。理解了这层血缘关系你会更容易记住堆排序的两个关键细节建堆是 O(n)而不是 O(n log n)因为可以用自底向上的下沉建堆取出堆顶后的下沉操作是 O(log n)。有了选择排序这张“底图”堆排序的定位就不再是凭空冒出来的神秘算法。6. 实操中高频踩坑点与一点教学建议最后这部分是我在实际带新人、看同学写代码时反复遇到的高频问题挨个列出来能帮你少走弯路。6.1 坑一内层循环起点写错写j 0而不是j i 1这是最经典的错误。后果是每一轮都把整个数组重新扫一遍连已经排好序的前缀区域都不放过。虽然结果大概率还是对的但无谓的比较次数增加而且当minIndex选到前面已经有序的位置时还会把已经放好的元素又重新和后面交换一遍导致整个数组被打乱。判断标准很简单内层循环的起点必须跟随外层下标。6.2 坑二忘记每轮重置 minIndex有人会在函数开头写int minIndex 0;然后放在外层循环外面。第一轮没问题第二轮开始minIndex还是上一轮找到的那个全局最小值下标就会造成混乱。正确的写法是minIndex在外层循环体内、内层循环之前初始化为当前轮次的i。6.3 坑三只看结果不管过程我见过不少同学写完排序后只用一句“反正输出是对的”来验收。对于学习阶段更推荐的做法是加断言、加日志观察每一轮结束后的数组状态。比如 C 语言调试时每轮交换后打印一次数组就能非常直观地看到最小值一个一个归位的过程。一旦某一轮结果不合法立刻就能定位问题出在定位阶段还是交换阶段。6.4 教学建议先画图再写码讲选择排序的时候我一般会让对方先在纸上画出每一轮“扫描到哪里、minIndex 更新了几次、最终换的是谁”至少手动跑通一个长度5的例子再动笔写代码。这个“先定位后交换”的直觉一旦建立代码写错的可能性会大幅降低。对自学者来说也可以用 Python 在循环里插print(arr, min_idx)观察每一轮的状态效果是一样的。选排序这个家伙论性能不如快排归并论适应性不如插入排序但它结构简单、思想干净是理解“复杂度分析”和“算法演进”的最佳起点之一。把它的机制彻底吃透再去看堆排序、锦标赛排序思路会顺很多。
阅读完成 · 觉得有帮助？
