选择排序：像玩扑克牌一样挑出最小的牌

你玩过扑克牌吗？假如手里有一把乱序的牌，你会怎么把它们从小到大排好？一种方法是：先找到最小的那张牌，放在最左边；然后从剩下的牌里再找最小的，放在第二张的位置……这样一步步，所有牌就排好了。选择排序就是这种思路——每次从未排序的部分中选出最小的那个数，把它放到已排序部分的末尾。

这个算法在生活中很常见，比如你有一盒笔，想按长短摆好，你可以每次从剩下的笔里抽出最短的那支放到左边。选择排序简单直观，适合用来理解“比较和交换”的基本思想。

核心思想：不断挑选最小的“宝石”

选择排序把数组分成两个区域：

左边：已排序区（一开始是空的）
右边：未排序区（一开始就是整个数组）

每次从右边未排序区里找到最小的元素，然后把它和未排序区的第一个元素交换位置。这样，最小的元素就加入到了左边的已排序区，而未排序区缩小一个。重复直到所有元素都排好。

过程动画（用数字举例）：原数组：[29, 10, 14, 37, 13]

第一轮：未排序区是全部。找到最小值 10，把它和第一个元素 29 交换 → [10, 29, 14, 37, 13]
第二轮：未排序区从第二个位置开始 [29,14,37,13]。找到最小值 13，和第二个元素 29 交换 → [10, 13, 14, 37, 29]
第三轮：未排序区 [14,37,29]。最小值 14 已经在开头，不用交换 → [10,13,14,37,29]
第四轮：未排序区 [37,29]。最小值 29，和 37 交换 → [10,13,14,29,37] 完成。

生活中的类比：排队买零食

想象一下，你们班要按身高从矮到高排队，但大家站得乱七八糟。老师点名：“所有没排好的人注意！现在，从没排好的人里找出最矮的那个，让他站到队伍最前面（已排好区域的末尾）。”然后重复这个过程，每次选一个最矮的放到已经排好的同学后面。这就是选择排序的“挑最小”法。

另一个例子：你在玩挖宝石游戏，每次从盒子里找最小的一颗宝石放在空地上，然后继续从剩下的找最小……最后宝石按从小到大的顺序排好。

Python 代码实现（带中文注释）

下面这段代码实现了选择排序，每一行都加了中文注释，方便你理解：

def selection_sort(arr):
    """选择排序：每次找出未排序部分的最小值，放到已排序末尾"""
    n = len(arr)                 # 数组长度
    for i in range(n - 1):       # 外层循环：控制已排序区的末尾位置（共 n-1 轮）
        # 假设当前 i 位置是最小值的下标
        min_idx = i               # 最小值下标，初始设为 i
        # 在未排序区（i 后面）找真正的最小值
        for j in range(i + 1, n): # 内层循环：从 i+1 到末尾寻找更小的
            if arr[j] < arr[min_idx]:
                min_idx = j       # 更新最小值下标
        # 如果最小值不在 i 处，就交换
        if min_idx != i:          # 只有当 min_idx 变化时才交换
            arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

# 测试：用成绩排序
scores = [88, 75, 93, 67, 81, 90]
print("排序前:", scores)
selection_sort(scores)
print("排序后:", scores)

运行结果：

排序前: [88, 75, 93, 67, 81, 90]
排序后: [67, 75, 81, 88, 90, 93]

新手容易犯的错误

忘记记录最小值的下标
有些同学会用 arr[j] < arr[i] 就直接交换，但这样会频繁交换，效率低且逻辑错乱。正确做法是记下标，一轮结束再交换一次。
内层循环范围写错
for j in range(i+1, n) 中的 n 不能写 n-1，否则会漏掉最后一个元素。
交换条件写反
- 错误：if min_idx == i: 然后交换（这样会把自己和自己交换，没意义）
- 正确：只有当 min_idx != i 时才交换，减少不必要的操作。
混淆外层循环次数
对于 n 个元素，只需要 n-1 轮即可（最后一个元素自然归位）。如果写成 for i in range(n)，最后一轮里数组已经排好，但会多一次无意义的寻找。

总结：效率如何？稳定吗？

时间复杂度：选择排序有两层循环，比较次数为 $\frac{n(n-1)}{2}$ ，所以总是 $O(n^2)$ 。不管数组是否已经排好，它都要找最小值，因此最好情况和最坏情况一样慢。
稳定性：不稳定，因为交换可能把相同值的元素相对顺序打乱。比如数组 [5, 5, 3]，第一轮把 3 和第一个 5 交换，两个 5 的相对顺序就变了。
空间复杂度：只用了几个临时变量，所以是 $O(1)$ 原地排序。

选择排序虽然慢，但思路简单，适合作为学习排序算法的入门。GESP 4级考试中，你不仅要能写出代码，还要能手动模拟每一轮的交换过程。

选择排序：像玩扑克牌一样挑出最小的牌