前几天一个读者在群里说：十大排序算法里他唯独对选择排序特别不踏实，看别人代码每一步都懂，自己一写就总是越界。这问题其实太典型了。很多刚接触算法的人都有同感，因为选择排序的代码看起来就两层循环加一个交换，但正是那几个下标的边界，最容易翻车。这篇我把选择排序掰开揉碎讲清楚，核心逻辑用一句话概括就是：每轮从剩下的元素里挑一个最小值，放到前面。内容会包含文字图解式的过程推演、可直接运行的实现代码、复杂度分析，以及几个只有亲手写过一遍才会注意到的坑。不管你是零基础小白，还是准备面试想快速复习，都能从这里拿到可以直接用的结论。
1. 整体思路与设计拆解
1.1 一句话说清选择排序的核心逻辑
先拿打扑克举例。手里有一把乱序的牌，大多数人会怎么做？先从牌堆里找到最小的一张放到最左边，再从剩下的牌里找第二小的放到第二张位置，以此类推。等把所有牌都过一遍，整副牌就排好了。选择排序就是把这个过程写成代码。
计算机里的操作更具体，假设数组长度为 n，算法要跑 n-1 轮，每一轮做两件事：
- 在“当前未排序区间”里找到最小元素的下标。
- 把这个最小元素交换到该区间的第一个位置。
第一轮结束，数组第一个元素就是全局最小值；第二轮在剩下的 n-1 个元素里找最小值，放到第二个位置；第三轮继续……所以每一轮过后，数组前部会形成一个“已经排好的前缀”，后部是“仍在待处理的区间”。后面所有查询和比较，都只发生在待处理区间内。
这个思路的设计精髓就是“选择”两个字：每一轮主动选出一个最小值归位，而不是像冒泡那样一路比较一路交换。冒泡靠“相邻元素交换把大元素慢慢顶到最后”，选择排序则是“扫描一遍定位最小，然后一步到位”。这也是它名字的由来。
1.2 为什么先学选择排序
很多人一上来就学快速排序，结果被递归和基准值绕得晕头转向。我的建议是先把选择排序弄明白，再往后走。理由有三点。
第一，它几乎没有“前置知识”。只需要理解 for 循环、数组下标、比较大小，就能读懂整个算法。双层循环天然适合用来建立“外层控制轮次、内层控制遍历范围”的直觉，这个直觉后面学插入排序、冒泡排序都用得上。
第二，它是很多重要算法的“雏形”。堆排序本质上就是“每一轮选一个最值放到有序区”，只不过它用一个堆结构把“查找最小值”的耗时从 O(n) 优化到了 O(logn)。如果选择排序都理解不透，学堆排序会更吃力。
第三，它作为面试题出现的概率也不低。面试官往往不是考你会不会背代码，而是问“这个算法稳定吗”“最坏情况复杂度是多少”“能不能优化”。这些我都会在后面逐个讲清楚，学完这篇，相关的追问基本都能接住。
1.3 选择排序与冒泡排序，别再傻傻分不清
初学者最容易把选择排序和冒泡排序混在一起，原因很简单：两段代码都是两层 for 循环，看起来长得像。但实际上，它们的“行为逻辑”完全不同。
冒泡排序的核心操作是“相邻两两比较，如果顺序不对就交换”，每一轮会把当前最大值“冒泡”到数组末尾，而且如果某一轮没有发生任何交换，说明数组已经有序，可以直接提前结束。选择排序不一样，它每一轮只做一次交换（或零次），直接把这个区间的最小值放到最前面，无论数据原本多有序，它都要老老实实跑完 n-1 轮，因为每轮必须先扫描完才能确定最小值在哪。
我用一张表把关键差异列出来：
| 对比点 | 冒泡排序 | 选择排序 |
|---|---|---|
| 每轮做的事 | 相邻比较并交换，把大值冒到尾 | 扫描未排序区，选最小值放头部 |
| 交换次数 | 最坏 O(n²) | 最多 n-1 次 |
| 能否提前结束 | 某轮无交换可提前退出 | 不能，必须跑满 n-1 轮 |
| 稳定性 | 稳定 | 不稳定 |
冒泡排序的优点是比较容易提前结束，缺点是交换频繁；选择排序的优点是交换次数少，缺点是无论如何都要把所有比较做完，无法感知“数组已经有序”。这个区别在复杂度分析那节还会再次体现。
2. 图解全过程与基础实现
2.1 文字图解：数组 [5, 2, 4, 6, 1, 3] 完整走一轮
“图解”不一定非要放张动图，我们用表格和分步描述，一样能把每一轮的变化看得清清楚楚。准备一个数组[5, 2, 4, 6, 1, 3]，共 6 个元素，按算法要求需要走 5 轮。
先看第 1 轮，未排序区间是[0, 5]，临时假设最小值下标为 0（元素 5）。然后从下标 1 开始往右逐个比较：
- j=1，元素 2 小于 5，更新最小值下标为 1；
- j=2，元素 4 不小于 2，不动；
- j=3，元素 6 不小于 2，不动；
- j=4，元素 1 小于 2，更新最小值下标为 4；
- j=5，元素 3 不小于 1，不动。
扫描结束，真正的最小值下标是 4，与当前区间首个下标 0 不同，所以交换arr[0]和arr[4]。数组变为[1, 2, 4, 6, 5, 3]。第一轮结束后，下标 0 的位置已经固定为全局最小值。第 2 轮开始时，未排序区间变成[1, 5]，临时假设最小值下标为 1（元素 2）。从下标 2 扫描到 5，里面的元素分别是 4、6、5、3，没有一个比 2 小，因此最小值下标仍然是 1，不需要交换，数组不变。接着看第 3 轮，未排序区间[2, 5]，假设最小值为下标 2 的元素 4。扫描 6、5、3 后，发现下标 5 的元素 3 更小，于是交换arr[2]和arr[5]，数组变成[1, 2, 3, 6, 5, 4]。第 4 轮，未排序区间[3, 5]，假设最小值为下标 3 的元素 6。扫描 5、4 后，发现下标 5 的元素 4 更小，交换后数组变为[1, 2, 3, 4, 5, 6]。第 5 轮，未排序区间[4, 5]，假设最小值为下标 4 的元素 5，扫描到 6 后仍然没有更小值，不需要交换。此时整个数组已经有序。
把每一轮的关键信息汇总一下：
| 轮次 | 未排序区间 | 找到的最小值 | 交换后数组 |
|---|---|---|---|
| 1 | [5, 2, 4, 6, 1, 3] | 1（下标4） | [1, 2, 4, 6, 5, 3] |
| 2 | [2, 4, 6, 5, 3] | 2（下标1） | 不变 |
| 3 | [4, 6, 5, 3] | 3（下标5） | [1, 2, 3, 6, 5, 4] |
| 4 | [6, 5, 4] | 4（下标5） | [1, 2, 3, 4, 5, 6] |
| 5 | [5, 6] | 5（下标4） | 不变 |
这份表格其实就是现成的“文字图解”。初学者写代码前，建议先自己在纸上把这样的过程推演两遍，确认理解“每次找最小值”到底发生在哪个区间，再动手写代码。
2.2 基础实现：代码拆开讲
推演过程搞清楚了，代码就是水到渠成的事。这里用 Python 写一版最容易读的实现，可以直接复制运行：
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] return arr逐行解释一下。for i in range(n - 1)控制轮次，第 i 轮就是要把第 i 小的元素放到下标 i 上，最后一轮 i = n-2 处理完后，最后一个元素自然归位，所以不需要跑到 n。min_idx = i表示先假设当前未排序区间的第一个元素就是最小值。内层for j in range(i + 1, n)从 i+1 开始扫描到数组末尾，凡是遇到比arr[min_idx]更小的值，就更新最小值下标。扫描结束后，min_idx指向这个区间真正的最小值。最后如果min_idx != i，说明最小值不在当前区间首位，需要交换一次；如果两者相等，说明当前位置已经是对的，什么都不用做。
这里的实现方式特别适合小白，因为所有交换都集中在最后一步。很多人第一次写会把交换挪进 if 判断里，每发现一个更小的值就立刻交换，这是一种错误写法，后面问题排查小节会专门讲。
如果你想换成 C、Java 或其他语言，思路完全不变，唯一要注意的就是交换那行改写。下面是 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; } } }2.3 复杂度推导和“为什么有序也慢”
关于复杂度，我需要把数字算给你看。
先看比较次数。第 1 轮要比较 n-1 次，第 2 轮比较 n-2 次，第 3 轮比较 n-3 次，最后一轮比较 1 次。把这些数加在一起：
(n-1) + (n-2) + ... + 1 = n(n-1)/2
所以无论数组原本是否有序，选择排序的比较次数永远是 n(n-1)/2，这个数字就是 O(n²)。也就是说，哪怕你喂给它一个已经排好序的数组，它依然要把所有比较走完。这和冒泡排序不一样，冒泡可以在某一轮没有任何交换时提前退出，最好情况能做到 O(n)，选择排序做不到。
再看交换次数。每一轮最多交换一次，所以总交换次数最多只有 n-1 次。如果输入数组已经基本有序，甚至可能一次交换都不发生。交换少是选择排序为数不多的优势之一，这也意味着在“交换成本远高于比较成本”的场景下，它可能比冒泡更划算。
空间复杂度很简单，只用了min_idx一个额外变量，不依赖输入规模，所以是 O(1)，属于原地排序算法。
综合起来就是一张很经典的口诀式结论：时间复杂度平均和最坏都是 O(n²)，空间复杂度 O(1)，不稳定。对于数据量小、写操作昂贵的场景，选择排序因为交换次数少还能用一用；数据量一大，O(n²) 的比较开销就会让它非常吃亏。
3. 进阶优化与稳定版实现
3.1 优化思路：一轮同时固定两个元素
既然每轮只找最小，那么能不能同时把最大值也找出来，一轮固定两个位置？当然可以。思路是在同一轮扫描里，同时记录未排序区间的最小值下标和最大值下标，扫描结束后把最小值放到区间左端、最大值放到区间右端，然后区间两边同时收缩。这样原本需要 n-1 轮，现在最多只需要 n/2 轮左右，常数项能省一半。
把实现写出来是下面这样：
def selection_sort_optimized(arr): n = len(arr) left = 0 right = n - 1 while left < right: min_idx = left max_idx = left for k in range(left, right + 1): if arr[k] < arr[min_idx]: min_idx = k if arr[k] > arr[max_idx]: max_idx = k if min_idx != left: arr[left], arr[min_idx] = arr[min_idx], arr[left] # 关键修正：如果最大值之前位于 left，交换后它已经被移到了 min_idx 位置 if max_idx == left: max_idx = min_idx if max_idx != right: arr[right], arr[max_idx] = arr[max_idx], arr[right] left += 1 right -= 1 return arr这段代码里有个很经典的坑：先交换最小值后，最大值所在的位置可能被破坏。举个例子，当最大值恰好位于 left 时，第一次交换会把最小值放到 left，而最大值被换到了 min_idx 原来所在的位置。此时如果还按原来的 max_idx 去把最大值放到 right，就会把已经放好的最小值又错误地交换出去。所以需要加一行修正判断：如果max_idx == left，就把max_idx更新成min_idx，因为最大值此时已经被换到了旧的最小值位置。
这里说的情形比较绕，我用一个具体例子演示。假设某轮区间是[9, 1, 3]，left=0，right=2，最小值在下标 1，最大值在下标 0。先交换arr[0]和arr[1]，数组变成[1, 9, 3]，这时最大值 9 实际上在下标 1。如果不修正，max_idx还是 0，接下来会把arr[0]（现在是最小值 1）和arr[2]（3）交换，得到[3, 9, 1]，整个顺序就乱了。修正后max_idx更新为 1，再执行最大值交换，得到[1, 3, 9]，正确。
这个优化版的复杂度仍然是 O(n²)，但实际比较次数没有减少，只是每轮能固定两个元素，减少了扫描轮数和一半的交换次数。数据量不大时，纯 Python 里因为多了分支判断，反而可能比基础版还慢，面试里提一嘴作为优化思路就够了，日常用基础版更耐看。
3.2 稳定版选择排序
如果保持“选择最小值归位”的大思路不变，怎么才能让它稳定？核心问题出在“交换”上。交换会跨越中间元素，导致相同元素的相对顺序被破坏。解决思路也很直接：不交换，改成平移。
具体操作是：找到最小值后，把从 i 到 min_idx-1 这段元素整体向右平移一位，再把最小值放到下标 i。这样每个元素只在自己的相对顺序中“平移”，不会跨过其他相同值。
def stable_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 temp = arr[min_idx] for k in range(min_idx, i, -1): arr[k] = arr[k - 1] arr[i] = temp return arr还是看一个容易理解的例子：数组[5a, 5b, 1]，其中 5a 和 5b 都表示值为 5 但来自不同位置的两个元素。找到最小值 1 在下标 2 后，先把 1 暂存到 temp，然后把arr[1]（5b）移到arr[2]，把arr[0]（5a）移到arr[1]，最后把 temp 放到arr[0]，结果是[1, 5a, 5b]。两个 5 的相对顺序保持住了，所以稳定。
但注意，稳定版的代价是移动可能大量增加，最坏情况每轮都要移动 O(n) 个元素，整体时间常数比基础版更大。它更多是用来理解“稳定性”这个概念，实际工程中不会为了稳定而选择这个变体，通常会直接改用归并排序。面试时如果被问到“选择排序能否稳定”，能说出“通过平移代替交换可以实现稳定，但代价更高”，说明你是真的理解了稳定性。
3.3 什么时候该用选择排序
聊完优化，说点实际的。选择排序在工程真实项目里用得很少，主要原因是 O(n²) 比较次数在数据规模稍大的情况下就很吃亏。但这不代表它没有存在价值。
一是在数据量很小、同时交换代价很高的场景下。比如数组元素不是简单整数，而是很大的结构体或对象，交换一次的开销比比较一次大得多。选择排序每轮最多交换一次，总交换次数是 n-1，能避免大量写操作。
二是在某些特殊硬件或受限环境里，比如内存极小、没有额外数组可用的情况下，选择排序作为原地排序，额外空间只有 O(1)，在一些嵌入式教学场景里还有一席之地。
三是纯粹作为教学。它是排序算法家族里思维最直白的一位，能帮你建立“扫描区间 + 维护最值下标”的基本功。之后学堆排序时，你会恍然大悟，原来堆的作用就是把这个“每轮查找最小值”的操作从 O(n) 提升到 O(logn)。
所以我的建议是：面试和考试必须会写，它是基础分；实际业务代码里如果数据规模超过几十个元素，优先考虑内置排序或快速排序、归并排序这些更高效的方案。
4. 常见问题与排查技巧实录
4.1 初学最容易踩的4个坑
代码不长，但写错的人真不少。我结合带新人的经验，把最常见的几个坑列成了一张速查表：
| 症状 | 可能原因 | 解决办法 |
|---|---|---|
| 排序后结果部分错误 | 内层循环从 0 开始，把已排序前缀也扫描了一遍 | 内层从 i+1 开始，只用未排序区 |
| 每轮交换很多次，结果还是乱 | 在 if 里直接交换，而不是记录下标 | 先记录 min_idx，扫描完再交换 |
| 数组越界 | 内层循环写成range(i, n+1) | 内层最大下标是 n-1 |
| 总感觉“少排了最后一个” | 外层循环写成range(1, n) | 外层 range(n-1)，最后一轮会自动归位 |
还有一个小细节，min_idx一定要初始化为 i，而不是固定初始化为 0。如果初始化为 0，每一轮都会把全局最小元素和当前区间首位做比较，会导致已经排好的前缀被再次参与比较，逻辑上就是错的。
4.2 写一个自检小用例
写完代码别急着说自己会了，先用几组数据自测。推荐必测的四种类型：
- 逆序数组
[5, 4, 3, 2, 1]：这是最坏场景，能检验交换逻辑。 - 已经有序的数组
[1, 2, 3, 4, 5]：能看出来它并不会提前退出。 - 含有重复值的数组
[2, 2, 1, 1, 3]：观察稳定性问题的好素材。 - 空数组和单元素数组：
[]和[1]应该原样返回。
如果结果不符合预期，最快的方法是在函数内每轮结束后打印数组。比如输入[5, 2, 4, 6, 1, 3]，第 1 轮结束后应该得到[1, 2, 4, 6, 5, 3]。如果打印出的结果是[1, 5, 4, 6, 2, 3]之类，说明交换逻辑或者 min_idx 更新时机有问题，逐一对比每轮变化就能缩小排查范围。
4.3 两个常考概念：原地排序与稳定性
这两个概念在选择题里反复出现，我把它们一次说清楚。
原地排序指的是不借助额外数组完成排序，额外空间复杂度为 O(1)。选择排序只用一个额外变量存下标，属于原地排序。
稳定性指的是排序前后，值相同的元素相对顺序保持不变。选择排序是不稳定的，原因在于交换可能跨越中间元素。举经典的例子：[5a, 5b, 1]，第一轮找到最小值 1，交换arr[0]和arr[2]，得到[1, 5b, 5a]。原来 5a 在 5b 前面，排序后 5a 跑到 5b 后面去了，相对顺序被破坏，所以不稳定。
如果面试官紧接着问“能不能把选择排序改成稳定”，你就把 3.2 节的平移法说出来。这个补充能体现出你对概念的掌握不是停留在背结论层面。
4.4 现场调试：如何快速定位错误
我自己的调试经验是，把数组切成“红区”和“蓝区”来理解。红区是前面已经排好的部分，蓝区是后面待处理的部分，每一轮只在蓝区找最小值，然后把这个最小值“钉”到红区的下一个位置。定位错误时可以问自己三个问题：
第一，当前轮次的蓝区起点是不是 i？如果内层循环范围不对，排序结果必然出错。第二，min_idx在每一轮扫描结束后，是否真的指向蓝区的最小值？如果中间交换过，它就可能是脏数据。第三，交换完以后，数组是否仍然只有红区递增，而蓝区内部乱序？这其实是正常的，因为蓝区还没排。
遇到测试不过，就用打印大法。每轮结束输出一次数组状态，和前面对照着看，通常一两分钟就能发现边界写错还是交换写错。别怕打印日志，这是调试里最朴素也最有效的手段。
最后再分享一个我实际操作中的体会：选择排序虽然写起来简单，但真能一次写对的人不算多。当年我第一遍写的时候，就是把内层循环起点写成 0，结果前两个元素永远排不对。后来养成一个习惯，写任何排序算法，先手动推演一轮，再翻译成代码，出错率会大幅下降。这篇提到的优化版和稳定版，建议你也照着推演一遍，特别是优化版里max_idx == left的修正，那一段是真正的分水岭，弄明白了，你对下标操作的掌控会上一个台阶。之后学堆排序时，可以带着“怎么更快找出未排序区最小值”这个问题去学，收获会更大。
