Python选择排序详解：从原理到优化，彻底搞懂O(n²)算法

1. 先聊两句：为什么你现在就该弄懂选择排序

很多初学者学 Python 算法时，第一个接触的排序往往是冒泡排序，因为教材里它总是排在最前面。但说实话，真正让人“一眼看穿排序是怎么回事”的，我觉得是选择排序。选择排序的核心逻辑极其朴素：每次从剩下的元素里找出最小的那个，放到前面去。像极了我们在生活里挑东西——从一筐苹果里挑出最大的，放到篮子里，再接着挑下一个。

选择排序的原理不依赖复杂的递归或分治思想，它的每一步都肉眼可见、逻辑可循。无论你是刚学 Python 的编程新手，还是在准备面试需要快速回顾基础算法的求职者，这都是一篇可以直接照着写代码、跟着推过程的实操笔记。这篇文章会从底层原理讲起，手把手拆解 Python 实现，再附上完整的示例代码和调试经验，尽量把每一步都掰开揉碎。

这篇内容能解决什么问题？说白了就两件事：第一，让你彻底看懂选择排序是怎么工作的；第二，让你能自己写出不出 bug 的 Python 实现，并且真正理解它为什么是 O(n²) 的时间复杂度——而不是只会背结论。

2. 选择排序思路拆解：从生活场景到算法模型

2.1 一句话说清算法思想

选择排序的完整思想其实就两步循环完成：在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置；然后继续从剩余未排序元素中寻找最小（或最大）元素，放到已排序序列的末尾，直到所有元素均排序完毕。

这个过程有点像玩扑克牌时的整牌动作：你手里有 5 张乱序的牌，你想从小到大排好。你最自然的做法是什么？肯定是扫一眼，找出最小的一张放到最左边，然后从剩下的 4 张里再找最小放到第二张位置，依此类推。这就是活生生的选择排序，只不过计算机不会“扫一眼”，它只能通过逐一比较来找出最小值。

2.2 逐步演算：一个完整的选择过程

光看文字描述还是不够直观，我习惯用一组具体数据来演示。假设我们要对下面这组数字做升序排序：

[64, 25, 12, 22, 11]

第一轮：从第 0 个位置到最后，寻找最小值。

• 从 64 开始，依次比较 25、12、22、11
• 发现 11 最小，所以 11 和第 0 个位置的元素（64）交换位置
• 排序结果：[11, 25, 12, 22, 64]

此时第 0 个位置已经确定了，不用再管。

第二轮：从第 1 个位置到最后，寻找最小值。

• 在[25, 12, 22, 64]里找最小值，找到 12
• 12 和第 1 个位置的元素（25）交换
• 排序结果：[11, 12, 25, 22, 64]

第三轮：从第 2 个位置到最后，寻找最小值。

• 在[25, 22, 64]里找最小值，22 最小
• 22 和第 2 个位置的元素（25）交换
• 排序结果：[11, 12, 22, 25, 64]

第四轮：从第 3 个位置到最后，寻找最小值。

• 在[25, 64]里找最小值，25 本来就在第 3 个位置，不用交换
• 排序完成：[11, 12, 22, 25, 64]

这个推演过程我建议你一定在草稿纸上自己画一遍。当年我理解不了排序，就是因为只看代码不动手模拟。真的跟着数据走一轮流程之后，排序的整个流程刻在脑子里，再也忘不掉。

2.3 为什么不用“每次都交换”

有个细节值得单独说一下：第一轮里我们是从头比到尾，记录的是“当前最小值的下标”，并不是每次比较到更小的值就立刻交换。找到最小值 11 后，只和位置 0 交换一次。

这样做能减少交换次数，避免不必要的性能损耗。你看我上面的演示，每轮最多只发生一次交换，这就是“选择”这个名字的来历——先选出目标，再动手，而不是边走边换。

3. 复杂度分析：为什么它注定慢，但依然值得学

3.1 时间复杂度：稳定地 O(n²)

选择排序的时间复杂度分析是所有排序算法里最直白的之一。不管你给的数组是正序、倒序还是乱序，它做的比较次数都不变。

比较次数怎么算？第一轮需要比较 n-1 次，第二轮 n-2 次，第三轮 n-3 次……一直到最后 1 次。加在一起就是：

(n-1) + (n-2) + ... + 1 = n(n-1)/2

用大 O 表示法去掉常数项和低阶项，就是O(n²)。这意味着什么？如果数组里有 10000 个元素，你需要做大约 5000 万次比较。这个量级在数据量小的时候无所谓，数据量一大就非常吃力。

我经常用这个类比来解释 O(n²) 有多夸张：假设你从 10 个人里找最高的，比 9 次就行；从 100 个人里找，比 99 次；但如果要排序 100 个人，你得反复找 100 轮，总比较次数是 4950 次。人数只翻了 10 倍，工作量翻了大约 100 倍。

3.2 空间复杂度与稳定性：两个关键标签

空间复杂度是O(1)，这是选择排序最拿得出手的优点。它是在原数组上就地排序，只需要一个临时变量来辅助交换，不需要额外开辟大块内存。这一点在实际嵌入式中非常受欢迎，因为内存紧张的环境里，O(1) 空间是硬指标。

稳定性则需要特别留意：选择排序是不稳定的。举个例子，你有序列[5(a), 8, 5(b), 2]（其中 a、b 用于区分两个值相同的 5），排序时第一次会找到最小值 2，和第一个 5(a) 交换，变成[2, 8, 5(b), 5(a)]。此时 5(a) 被换到了 5(b) 的后面，两个相同值元素的相对顺序变了。如果你对稳定性有要求，比如排序的键值有多个优先级，需要保持相同键值元素原有先后顺序，这时选择排序就不合适。

注意最好情况也是 O(n²)，这点和冒泡排序不同。冒泡排序如果在某一轮没发生任何交换，可以提前退出循环；选择排序哪怕已经有序了，仍然要老老实实完成所有比较，因为它不知道“有序”这个状态。

4. Python 实现：从基础版到优化版

4.1 基础版：逐行注释的完整示例

写 Python 实现时，我通常先把最朴素的版本写出来，保证逻辑清晰，然后再谈优化。下面这段代码可以直接复制运行：

def selection_sort(arr): n = len(arr) # 外层循环：i 表示当前要确定的位置 # 最后一个元素不需要再排序，所以只需要循环 n-1 轮 for i in range(n - 1): # 假设当前位置就是最小值所在位置 min_index = i # 内层循环：在未排序区间 [i+1, n-1] 中寻找更小值 for j in range(i + 1, n): if arr[j] < arr[min_index]: min_index = j # 如果找到了更小的值，交换；否则保持不变 if min_index != i: arr[i], arr[min_index] = arr[min_index], arr[i] return arr if __name__ == "__main__": test_arr = [64, 25, 12, 22, 11] sorted_arr = selection_sort(test_arr) print(sorted_arr) # 输出 [11, 12, 22, 25, 64]

这段代码里有几个值得展开的细节。外层循环为什么是range(n - 1)而不是range(n)？因为当倒数第二个位置确定好了，最后一个位置自然也确定了，不需要再处理。内层循环的范围为什么是range(i + 1, n)？当i已经是第一个位置时，前i个位置已经排好序了，每轮搜索只需要在未排序部分进行。

min_index = i这个初始化的思路是代码里的一个常规技巧：我先把当前位置当作最小值，然后拿它去和别人比。如果发现别人更小，更新min_index，最后统一交换。这样写的好处是让代码意图非常明确：找到本轮最小值的下标后，再做一次交换操作。

我见过很多新手在交换这里踩坑，使用临时变量实现交换，代码变成这样：

temp = arr[i] arr[i] = arr[min_index] arr[min_index] = temp

这当然也能实现交换，但 Python 的元组赋值语法arr[i], arr[min_index] = arr[min_index], arr[i]更简洁，也不需要显式声明中间变量。两种方式都能用，但用 Python 原生的交换方式代码更 Pythonic。

4.2 优化版：同时找最大值和最小值，减少比较趟数

基础版在一次遍历里只找最小值。其实我们可以每轮同时找出最小值和最大值，最小值放到前头，最大值放到后头。这样外层循环的趟数可以减半。

def selection_sort_improved(arr): n = len(arr) left = 0 right = n - 1 while left < right: min_index = left max_index = left # 在 [left, right] 区间内同时找最小和最大值 for i in range(left, right + 1): if arr[i] < arr[min_index]: min_index = i if arr[i] > arr[max_index]: max_index = i # 交换最小值到左端 arr[left], arr[min_index] = arr[min_index], arr[left] # 注意：如果最大值原本在 left 位置，它已经被换走了 if max_index == left: max_index = min_index # 交换最大值到右端 arr[right], arr[max_index] = arr[max_index], arr[right] left += 1 right -= 1 return arr

这个优化版本里有一个非常经典的坑：如果最大值刚好在left位置，而第一次交换时它被换走了，这时候max_index必须同步更新成min_index。否则第二次交换就会把错误的值放到右端。

我当初第一次写这个优化版的时候，在max_index == left这个特殊情况上卡了半小时。数据如果恰好是[5, 1, 3, 4, 2]这种类型，最大值 5 在left位置，第一次交换后变成了[1, 5, 3, 4, 2]，如果不对max_index做修正，第二轮交换arr[right]时，max_index还是 0，此时 0 位置已经变成 1 了，排序结果就会出错。

这就是为什么说排序算法的优化最容易出 bug 的地方往往不是主逻辑，而是边界情况的处理。这段代码你可以多拿几个不同的测试用例跑一跑，尤其是最大最小值落在边缘位置的场景。

4.3 另一个变体：排成降序怎么做

选择了升序还是降序，其实只改一个比较符号。降序选择排序无非是把“找最小值”改成“找最大值”。为了不让你觉得只会升序不够用，我给你一份降序示例：

def selection_sort_desc(arr): n = len(arr) for i in range(n - 1): max_index = i for j in range(i + 1, n): if arr[j] > arr[max_index]: max_index = j if max_index != i: arr[i], arr[max_index] = arr[max_index], arr[i] return arr

这个版本的核心就是if arr[j] > arr[max_index]，从找最小变成找最大。如果你需要按字符串长度、元组某个字段等自定义规则排序，也可以通过修改比较逻辑或者传入key函数来实现。这一点在实际工程里用处很大，比如你有一个字典列表，想按其中的某个键排序，就可以改动内层比较逻辑来适配。

5. 实操常见问题与排查记录

5.1 问题速查表：这些坑我都踩过

写选择排序的代码不算难，但真想一次跑对、结果正确，还是有几处隐藏的陷阱。我把这些年在教学和实战中见到的典型问题整理成一个表格，方便你自查：

看到“把索引和值搞混”这一条，我要多说一句。很多教材里会用min_value这个变量来记录最小值，但到了交换环节才发现你还得知道最小值在哪，于是又去index()方法里找一次。这种写法不仅多扫一遍数组，还有潜在 bug——如果列表里有重复值，index()返回的是第一个匹配项的下标，未必是你想要的那个。所以从一开始就别记录值，只记录下标。

5.2 边界条件测试：代码正确性的关键

写完排序算法，第一件事不是拿去用，而是用各种边界输入测试。我从实际摸索中总结了一套最小测试集：

def run_tests(): # 测试1：空列表 assert selection_sort([]) == [] # 测试2：只有一个元素 assert selection_sort([1]) == [1] # 测试3：完全逆序 assert selection_sort([5, 4, 3, 2, 1]) == [1, 2, 3, 4, 5] # 测试4：已经完全有序 assert selection_sort([1, 2, 3, 4, 5]) == [1, 2, 3, 4, 5] # 测试5：包含重复元素 assert selection_sort([4, 2, 7, 2, 9, 1]) == [1, 2, 2, 4, 7, 9] # 测试6：包含负数 assert selection_sort([-3, 10, -1, 0, -20]) == [-20, -3, -1, 0, 10] print("全部测试通过") run_tests()

这种测试集合有助于快速定位问题。比如写着写着发现空列表传入时n - 1是 -1，range(-1)就不会执行，返回空列表，看似没问题。但如果你的实现里没有对