为什么你打牌时天生就会选择排序，写代码时却总踩坑？ - 每日分享

你有没有注意过这样一个现象？

一个完全不懂编程的人，拿起一把乱序的扑克牌，也能很快把牌理好。但你让一个刚学排序的人手写选择排序，他大概率会在内层循环的边界上翻车。

这不是巧合。选择排序之所以适合作为排序算法的入门，恰恰因为它模拟的是人类最本能的整理策略——每次挑最小的，放到一边。但“本能”和“代码”之间，隔着几个非常具体的坑。

选择排序的本质：一个不断缩小的未排序区

先把核心思想压缩成一句话：维护一个已排序区的右边界，每轮从未排序区里选出最小值，和未排序区的第一个元素交换。

这个定义里有三个关键信息，每一个都对应一类常见错误：

“选出最小值”——你需要记录的是下标，不是值。记录值没有意义，因为最终要交换的是位置。
“和未排序区第一个元素交换”——交换只发生一次，不是每次比较都换。
“已排序区右边界”——外层循环控制的是这个边界，不是“比较次数”。

拿 [5, 3, 8, 1, 4] 走一遍第一轮：

整个数组都是未排序区，遍历一遍找到最小值 1，它在下标 3 的位置。把 1 和未排序区第一个元素 5 交换，得到 [1, 3, 8, 5, 4]。

注意一个细节：交换之后，5 被扔到了原来 1 的位置。**其余元素的相对顺序没有变。**这就是为什么第一轮结束后是 [1, 3, 8, 5, 4] 而不是 [1, 5, 3, 8, 4]——后者是把选择排序和冒泡排序搞混了。冒泡排序第一轮会把最大的 8 冒到末尾，得到的是完全不同的结果。

稳定性：一个容易被“想当然”带偏的性质

很多人第一次听到“选择排序不稳定”时会愣一下：我每次挑最小的，怎么会不稳定？

问题出在交换上。

假设序列是 [5a, 5b, 3]，5a 和 5b 值相等，但 5a 在 5b 前面。第一轮选出最小值 3，它和未排序区第一个元素 5a 交换，得到 [3, 5b, 5a]。原来 5a 在 5b 前面，现在反过来了。

这就是选择排序不稳定的根源：**跨位置的交换会打乱相等元素的相对顺序。**冒泡排序和插入排序之所以稳定，是因为它们只做相邻交换或插入，不会让相等元素“跳过”彼此。

这个知识点在判断题里出现频率极高——“选择排序是稳定的”这句话，永远是错的。

从算法到题目：错误票据问题

有一道题很有意思：全年票据的 ID 号是连续的，但录入时出了一个错——一个 ID 断号，另一个 ID 重号。要你找出这两个 ID。

这道题表面上看和排序没关系，但解法里藏着一个关键思路：先排序，再扫描相邻元素的差值。

为什么排序能帮忙？因为 ID 号本来是连续的。排序之后，如果某个位置出现了重复，相邻两个数会相等；如果某个位置出现了断号，相邻两个数的差会是 2 而不是 1。

nums.sort()  # 排序后，断号和重号都会在相邻比较中暴露
for i in range(1, len(nums)):
    if nums[i] == nums[i-1]:
        duplicate = nums[i]       # 重号
    if nums[i] - nums[i-1] == 2:
        missing = nums[i] - 1     # 断号

这里排序不是目的，而是手段。选择排序当然也能用，但 Python 内置的 sort() 底层是 Timsort，效率远高于手写选择排序。这道题真正考察的是：你能不能想到用“有序性”来暴露异常。

去重排序：选择排序的一个变体思路

另一道题要求输出去重后从大到小排序的序列。如果用手写排序，选择排序的思路可以稍作变形：每轮选出最大值放到已排序区末尾，同时在输出时跳过与上一个输出相同的元素。

但更值得说的是：这道题其实在提醒你，排序和去重可以解耦。先去重再排序，或者排序后跳过去重，都可以。选择排序本身不负责去重，但排序后的数组让去重变得极其简单——只需要比较相邻元素是否相等。

# 排序后去重（从大到小）
result = []
for x in sorted(nums, reverse=True):
    if not result or result[-1] != x:
        result.append(x)

这就是排序的威力：它把“找重复”这个看似需要哈希表的问题，变成了一个线性扫描就能解决的事情。

新手最容易踩的三个坑

坑一：每次比较都交换。 看到 arr[j] < arr[i] 就 swap，结果数组被搅得乱七八糟。正确做法是记录 min_idx，一轮只交换一次。

坑二：内层循环写成 range(i+1, n-1)。 最后一个元素永远参与不了比较，导致最小值可能被漏掉。边界是 n，不是 n-1。

坑三：外层循环写成 range(n)。 最后一个元素不需要再找最小值了，它自然就是剩下的那个。多跑一轮不会出错，但暴露了你对算法边界的不理解。

选择排序的真正价值

说实话，选择排序在实际工程中几乎不会被用到。它的比较次数固定是 n(n-1)/2，不管数据是否已经有序，都是 O(n²)。它也不稳定。

但它的价值在于教学。它把排序问题拆解成两个最基本的操作：比较和交换。理解了这两个操作如何配合，你才能理解为什么插入排序更高效（减少了交换次数），为什么归并排序能突破 O(n²)（分治减少了比较次数）。

选择排序是一把钥匙，不是一扇门。用它打开排序的门，然后尽快走向更高效的算法。

关于作者

我是赵老师，持有 NOI 信息学奥赛教练证书，拥有 15 年以上的软件开发经验，从事信息学少儿编程教学已有 8 年时间。

这些年累计帮助多名学生通过编程特长升入自己心仪的目标学校。

如果你在编程学习上有任何疑问，欢迎联系我：18620372957（微信同号）