很多人学排序算法时会有一个困惑：明明代码只有几行，为什么每次自己写出来都是错的？
我觉得选择排序很适合作为第二个算法来学。上一篇用二分查找把大O表示法讲清楚了，大家已经知道 O(log n) 和 O(n) 的区别；到了选择排序，正好把循环、比较、交换这三件事叠加在一起。它的思路一句话就能说完：每一轮从剩下的元素里挑出最小的，放到已排序部分的末尾。这句话听起来太简单了，但真到实现时，容易在“记录最小值位置”还是“直接记录最小值”之间栽跟头。
这篇文章我把选择排序从思路到代码、从复杂度到稳定性全部拆开讲。不管你是刚接触算法的大学生、准备面试的开发者，还是只是想把排序讲明白给同事听，看完都能有一条清晰的线。
1. 为什么先从“选择”入手：核心思路与场景映射
1.1 生活场景：反复挑出最小的牌
选择排序的核心是“选择”，不是“交换”。想象一下你面前有一堆乱序的牌，你每次在里面找最小的一张，拿起来放到左边；然后在剩下的牌里再找最小的一张，放在上一张右边。重复这个过程，左边就形成了一个从小到大排好的序列。这就是选择排序最朴素的样子。
程序里要实现“找最小”这件事，不是真的拿在手里，而是用一个变量记录最小值的下标。我刚开始教别人的时候，总会强调：不要用 min_val 直接记录值，而要记录 min_index。因为最后做交换的时候，你光有值是不够的，还得知道它在数组的哪个位置。这个细节虽然小，却直接关系到代码能不能写对。
1.2 和冒泡排序、插入排序的区别
很多教程喜欢把冒泡、选择、插入放在一起讲，因为它们的复杂度都是 O(n^2)。但三者的“节奏”完全不同：
- 冒泡排序：相邻两两比较，把大的逐步往后“冒”。比较次数相对固定，但交换次数多，最坏情况下接近 n^2/2。
- 插入排序：把当前元素往前插入到合适位置。它在数据基本有序时非常快，最好情况 O(n)。
- 选择排序：每轮固定找最小值，交换一次。交换次数始终只有 n-1，但比较次数固定为 n(n-1)/2，不会因为输入有序而变少。
这张表可以快速对照：
| 算法 | 比较次数（最坏） | 交换次数（最坏） | 稳定性 | 适合场景 |
|---|---|---|---|---|
| 冒泡排序 | 约 n^2/2 | 约 n^2/2 | 稳定 | 教学演示 |
| 选择排序 | n(n-1)/2 | n-1 | 不稳定（原地交换） | 交换代价高的场景 |
| 插入排序 | 约 n^2/2 | 约 n^2/4（逆序时偏高） | 稳定 | 小规模、基本有序 |
对萌新来说，记住一句话就够：选择排序最大的特点是“铁了心每轮只换一次”，所以交换次数是所有 O(n^2) 排序里面最少的。
2. 图解选择排序：每一步都留痕
2.1 一条数组的完整迭代过程
直接用例子说话。假设有一个数组 [5, 3, 6, 2, 10]，我们用“已排序边界 i”把数组分成两部分：[0, i-1] 是已经排好序的部分，[i, n-1] 是还没处理的区间。每一轮要做的事情就是：在未排序区间里找到最小值，换到 i 的位置。
第一轮，i=0。当前未排序区间是整个数组。我拿第一个元素 5 当最小，然后从 3 开始往后一个个比：3 比 5 小，更新最小值为 3 的位置；6 不比 3 小，跳过；2 比 3 小，再更新；10 不比 2 小，跳过。扫描结束后，最小值在下标 3，也就是元素 2。把下标 0 的 5 和下标 3 的 2 交换，数组变成 [2, 3, 6, 5, 10]。
第二轮，i=1。未排序区间从 3 开始。用 3 当最小，比较 6、5、10，都没有更小的，所以最小值下标就是 i 自己，做一次“自我交换”，数组不变。这一步看似没意义，却让代码逻辑统一：每轮都交换，不管是不是自己。
第三轮，i=2。未排序区间 [6, 5, 10]，比较后 5 更小，交换 6 和 5，得到 [2, 3, 5, 6, 10]。
第四轮，i=3。未排序区间只剩 [6, 10]，6 已经是最小，自我交换。数组有序。
写成表格更清楚：
| 轮数 i | 未排序区间 | 最小值下标 | 动作 | 数组状态 |
|---|---|---|---|---|
| 0 | [5,3,6,2,10] | 3 | 交换 5 和 2 | [2,3,6,5,10] |
| 1 | [3,6,5,10] | 1 | 自我交换 | [2,3,6,5,10] |
| 2 | [6,5,10] | 3 | 交换 6 和 5 | [2,3,5,6,10] |
| 3 | [6,10] | 3 | 自我交换 | [2,3,5,6,10] |
注意看第二轮和第四轮，最小值本来就在正确位置，但选择排序不会提前结束。这是它的一个特点：不管数据多有序，扫描一轮都不能省。
2.2 指针、哨兵和“最小值的家”
如果你用画图的方式去理解，可以把 i 看成“已排序区间的右边界”，这个边界左边的元素都不再动了；min_index 则是每轮里的“哨兵”，它一开始指向 i，然后被更小的元素不断“劫持”。等到内层循环结束，哨兵停在哪里，哪里就是这一轮最小值的家。
我画图时喜欢用两只手：左手放在 i 的位置，右手在整个未排序区间扫一遍，找到一个比左手当前指向更小的元素时，右手停住，左手走过去交换。然后左手向右挪一格，右手再次从头扫。这种“一左一右”的图解法，比单纯背代码直观太多。
这里需要提醒一个常见的理解误区：内层循环不是从 0 开始，而是从 i+1 开始。因为 i 前面的部分已经有序，不需要再比较。很多新手写成 for j in range(0, n)，虽然结果可能也对，但白白多做了 i 轮比较，而且不改变复杂度量级，却容易让代码语义混乱。
3. 代码实现：从伪代码到可运行版本
3.1 书里常见的“移出新列表”写法
如果你看过某些算法入门书，最开始的版本可能是这样：每次找出整个列表里的最小值，把它添加到新列表末尾，然后从原列表删除。这个思路和“在一堆牌里抽最小”一模一样，非常好懂。
伪代码大概是：
function selectionSort(arr): sorted = [] while arr 不为空: 找到 arr 中最小元素 min sorted.append(min) 从 arr 中删除 min return sorted这个写法强调“选择”而不是“交换”，对刚接触算法的朋友更友好。它的缺点是空间复杂度是 O(n)，因为要额外开一个新数组；而且删除操作本身需要移动元素，实际时间比理论上的 O(n^2) 还要多一些。所以工程里不太用这种方式，但它非常适合用来理解“每轮选一个最小”的核心思想。
3.2 工程上更常用的“原地交换”写法
我平时更推荐写成原地交换版本，因为空间省、逻辑也更紧凑。Python 代码：
def selection_sort(arr): n = len(arr) for i in range(n - 1): min_index = i for j in range(i + 1, n): if arr[j] < arr[min_index]: min_index = j arr[i], arr[min_index] = arr[min_index], arr[i] return arr如果用 JavaScript 写，差别也不大：
function selectionSort(arr) { for (let i = 0; i < arr.length - 1; i++) { let minIndex = i; for (let j = i + 1; j < arr.length; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]; } return arr; }这里最关键的一行是if arr[j] < arr[min_index]。它用的是严格小于，不是小于等于。用严格小于能避免在遇到重复元素时频繁更新最小值下标，虽然最终结果都是有序的，但交换次数会少一些，逻辑也更符合“我们只关心更小，不关心相等”。
3.3 为什么选择“交换”而不是“插入”
有读者会问：为什么找到最小值之后不做插入，而是交换？这和插入排序差在哪里？
交换的本质是把“当前坑位”和“最小值的位置”互换。选择排序不关心其他元素的相对位置，只要最小值到前面，被换走的元素去最小值原来的位置就行。这样每轮操作成本低，只需要一次赋值。而插入排序要把元素一个个往后挪，给待插入元素腾位置，这个挪动过程在面对逆序数据时非常费。选择排序牺牲了“移动次数少”中“比较次数多”的另一面，但交换次数确实是最少的。
我们再想想“新建列表”版本，它每次从原数组删除最小值，本质也是一种“移动”，只是删除和追加的操作被拆开了。就代码健壮性而言，原地交换不需要额外空间，还能原地返回，这也是为什么面试手写排序时，大家默认写原地版本。
4. 复杂度与稳定性：选择排序的“体面”和“硬伤”
4.1 复杂度拆解：比较次数是固定的
选择排序的特征是：不管原始数据是否有序，比较次数都完全相同。我们来算一下。外层循环要执行 n-1 轮。第一轮内层比较 n-1 次，第二轮比较 n-2 次，一直到最后一轮比较 1 次。总比较次数是：
(n-1) + (n-2) + ... + 1 = n(n-1)/2
这个式子展开后是 0.5n^2 - 0.5n，所以时间复杂度就是 O(n^2)。最好情况和最坏情况一样，都是 O(n^2)。它没有冒泡排序那种“如果没发生交换就提前退出”的优化空间，因为即使数组已经有序，你也必须扫描完未排序区间才能确定最小值确实在自己该在的位置。
交换次数则少得多：每轮最多交换一次，所以最多 n-1 次。这给了它一个独特的优点：如果排序元素是非常大的对象，交换成本很高，选择排序的换位开销可能比冒泡、插入都低。但要注意，这只是理论上的优势，实际工程里很少只为“交换次数少”去用它，因为有更快的排序。
空间复杂度方面，原地交换版本是 O(1)，只用了一个 min_index 变量。新建列表版本是 O(n)，因为额外开了一个等长数组。面试时如果问“选择排序的空间复杂度”，默认答 O(1) 即可，除非你明确说明用的是辅助列表版本。
4.2 稳定性陷阱：为什么交换会破坏相对顺序
稳定性是个很容易被忽略的概念。一个排序算法是稳定的，意味着两个相等元素的相对顺序在排序后保持不变。为什么重要？举个实际场景：一个待排序对象集，先按姓名排过一次，现在按分数排，如果排序不稳定，同分数的人姓名顺序可能被打乱。
原地交换的选择排序不稳定，原因就在交换本身。看个例子，数组 [5a, 3, 5b, 1]，5a 和 5b 的值相同，我加了下标来区分它们在原数组里的先后顺序。第一轮找到最小值 1，下标 3，然后把 5a 和 1 交换，数组变成 [1, 3, 5b, 5a]。这两个 5 的相对位置从“5a 在前”变成了“5b 在前”，顺序被破坏了。
所以如果你需要稳定排序，或者排序对象带有次要字段，选择排序不是首选。插入排序和归并排序在这方面更稳。
这里有个有趣的细节：用“新列表 + 删除最小值”的写法实现选择排序时，因为每次删除的是从前往后找到的第一个最小值，相等元素的相对顺序反而能保持住。但这个写法不是我们通常讨论的“原地选择排序”。做题和面试的时候，最好先和对方确认你写的是哪个版本。
5. 常见问题与排查技巧实录
5.1 空数组、单元素、重复元素怎么处理
我把几种边界情况单独拿出来说。空数组：外层循环 range(n-1) 在 n=0 时是 range(-1)，在 Python 里不会执行，直接返回空数组，没问题。单元素数组：外层循环同样不执行，返回原数组，也没问题。但如果用 while 循环实现，就要小心边界条件，别写成 while i < n 导致越界访问。
重复元素是选择排序最容易被问到的场景。比如 [2, 2, 1, 3]，第一轮找到 1，和下标 0 的 2 交换，得到 [1, 2, 2, 3]。两个 2 的相对顺序没有变，看似稳定，但换一个输入就不一定了。因为只要最小值出现在某个相等元素后面，交换就会把前面的相等元素换到后面去。所以判断稳定性不要只看单个用例，要看算法本质。
我的习惯是，写完排序后先跑几个用例：
- 空数组
[] - 单元素
[42] - 全相等
[7, 7, 7, 7] - 逆序
[5, 4, 3, 2, 1] - 含有负数和零
[0, -1, 3, -2, 5]
这几个用例能覆盖大多数手写错误。
5.2 一个常见 Bug：比较条件写成<=会怎样？
代码里如果把arr[j] < arr[min_index]写成arr[j] <= arr[min_index]，会发生什么？结果数组依然有序，因为只要发现“不更大”就更新下标，最后选到的还是最小或“最后一个最小”。对于重复元素比较多的情况，这会导致不必要的下标更新和交换，让排序过程更不稳定，但不会影响正确性。
另一个典型的错误是把内层循环写成从i开始。这样j == i时，arr[j] < arr[min_index]永远不成立（因为同一个元素不小于自己），不影响结果，但会多做一次无效比较。如果从i-1开始，就可能把已经排好的元素重新卷入比较，导致排序结果错误。写代码时，内层循环起点一定要是i + 1。
5.3 从“肉眼检查”到“用日志验证”
当你实在不知道哪一步出错时，别盯着代码干瞪眼。在每轮交换后打印数组状态，是最快的定位方式。比如加一行调试输出：
print(f"i={i}, min_index={min_index}, arr={arr}")这样你能看到每一轮数组的变化，哪怕只有一步不对，也能立刻定位到“找最小值”还是“交换”出了问题。我曾经见过一个同学写了半小时没找到 bug，最后用打印法一看，发现他把arr[i], arr[min_index] = arr[min_index], arr[i]写成了两个单独的赋值语句，没有用中间变量，导致交换被覆盖。这类问题靠肉眼真的很难看出来，日志一下就暴露了。
6. 变体、优化与向其他算法延伸
6.1 一次选出最大值和最小值：看起来很美
选择排序每轮只选一个最小值，外层要跑 n-1 轮。一个常见变体是每轮同时找最小值和最大值，分别放到数组两端。这样趟数大约减半，但每一趟要同时做两次扫描式比较。
实现时有个容易踩的坑：如果最大值正好位于最小值要被换走的位置，交换顺序必须仔细处理。比如先把最小值放到左边，发现最大值被换到了 min_index 位置，就要把“最大值下标”也改过去，否则第二步会把错误的元素放到右边。这个细节我见过很多人写错，包括我自己第一次写的时候也翻过车。
不过从复杂度看，这个优化对 O(n^2) 的量级没有实质帮助。比较次数反而可能在常数上增加，只是交换趟数减少。它适合作为思维拓展题，不适合生产中替代选择排序。
6.2 从选择排序到堆排序：找到一个“更聪明的选择”
选择排序慢，是因为它找最小值靠“全量扫描”。如果有一台机器能记住剩余元素的最小值，每次直接取出来，那就不用一遍遍扫了。堆排序就是沿着这个思路来的。它用堆这种数据结构把“找最小值”从 O(n) 降到 O(log n)，所以整体复杂度变成 O(n log n)。可以把选择排序看作“每次用线性扫描找最小值”的堆排序退化版。
理解这条脉络比背一堆结论有用。你以后再看到堆排序，就知道它不是凭空冒出来的，只是把选择排序里的“查找”换成了更快的数据结构。
6.3 什么时候我会真的用它？
说实话，日常工作里我几乎不用选择排序排真实数据。但有两个场景我会想到它。一是教学，用一个最没有技巧的算法建立“循环 + 比较 + 交换”的肌肉记忆。二是极端场景：待排序的元素非常大，交换的代价极高，而比较代价相对便宜，同时数据规模又小到不值得上更复杂的算法。这种情况下，选择排序固定 n-1 次交换的优势会稍微突出一些。
还有个容易被忽略的应用：在不需要完整排序、只需要反复取第 k 小元素的场景下，选择排序的“每次确定一个最小值”的思想可以扩展成“快速选择”的引子。不过这就超出本篇范围了。
写到这儿，我的建议是：不要因为选择排序“效率低”就跳过它。它够简单，适合用来练手；它又有一堆值得展开的坑，比如稳定性、比较次数固定、边界条件。即使你今后用不到，把它当作一把理解其他排序的钥匙，也是很划算的学习投资。最后再分享一个小技巧：画图时把已排序区间用下划线框起来，每次只盯着未排序区间看，你会发现自己很快就懂了选择排序的全过程。
