第12课：选择排序

学习目标

完成本课学习后，你将能够：

理解选择排序的核心思想：掌握通过反复“查找最小值”和“交换位置”来排序的逻辑。
独立实现选择排序算法：能够用代码完整实现选择排序。
分析选择排序的时间复杂度：理解其时间复杂度与空间复杂度。
区分选择排序与冒泡排序：了解两种算法在实现和思路上的主要区别。
应用选择排序解决简单排序问题：能够使用该算法对给定数据进行排序。

核心概念

想象一下，你手中有一副打乱顺序的扑克牌（数字1到5），你想把它们从小到大排好。一个很自然的想法是：

第一步：在整副牌里找到最小的那张（比如是1），然后把它和最左边第一张牌交换位置。
第二步：现在第一张牌已经是最小的了，我们只看剩下的牌。在剩下的牌里再找到最小的那张（比如是2），然后把它和剩下牌里最左边的那张交换位置。
重复这个过程：每次都在未排序的部分里找到最小的元素，然后把它放到已排序部分的末尾。

这就是选择排序（Selection Sort） 的核心思想。它的关键操作有两个：“选择”最小值和交换位置。

算法步骤分解：

外层循环：控制“当前要放置最小值的位置”，从数组第一个位置 (i = 0) 开始。
内层循环：在从 i 开始到数组末尾的未排序区间中，找到最小元素的索引 (min_index)。
交换：如果 min_index 不是 i 本身，就将位置 i 的元素与 min_index 的元素交换。
重复：移动 i 的位置，重复步骤2和3，直到整个数组有序。

代码示例

下面是一个完整的、带详细注释的 Python 选择排序实现。

def selection_sort(arr):
    """
    使用选择排序对列表进行原地排序。
    
    参数:
    arr (list): 需要排序的列表
    返回:
    list: 排序后的列表（原地修改，返回同一对象）
    """
    n = len(arr)
    
    # 外层循环：i 表示当前需要放置最小值的位置
    # 当 i 到达 n-1 时，最后一个元素自然有序，所以只需到 n-1
    for i in range(n - 1):
        # 假设当前位置 i 的元素就是最小的
        min_index = i
        
        # 内层循环：从 i+1 开始，在未排序区间中寻找真正最小的元素
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j  # 找到更小的，更新最小索引
        
        # 如果最小元素不在位置 i，则进行交换
        if min_index != i:
            arr[i], arr[min_index] = arr[min_index], arr[i]
            # 等价于:
            # temp = arr[i]
            # arr[i] = arr[min_index]
            # arr[min_index] = temp
    
    return arr

# --- 测试代码 ---
if __name__ == "__main__":
    # 测试用例 1：普通数组
    array1 = [64, 25, 12, 22, 11]
    print("原始数组:", array1)
    selection_sort(array1)
    print("排序后数组:", array1)
    
    # 测试用例 2：已排序数组（最坏情况之一）
    array2 = [1, 2, 3, 4, 5]
    print("\n原始数组:", array2)
    selection_sort(array2)
    print("排序后数组:", array2)
    
    # 测试用例 3：逆序数组（最坏情况之一）
    array3 = [5, 4, 3, 2, 1]
    print("\n原始数组:", array3)
    selection_sort(array3)
    print("排序后数组:", array3)
    
    # 测试用例 4：包含重复元素的数组
    array4 = [3, 1, 4, 1, 5, 9, 2, 6]
    print("\n原始数组:", array4)
    selection_sort(array4)
    print("排序后数组:", array4)

运行结果预期：

原始数组: [64, 25, 12, 22, 11]
排序后数组: [11, 12, 22, 25, 64]

原始数组: [1, 2, 3, 4, 5]
排序后数组: [1, 2, 3, 4, 5]

原始数组: [5, 4, 3, 2, 1]
排序后数组: [1, 2, 3, 4, 5]

原始数组: [3, 1, 4, 1, 5, 9, 2, 6]
排序后数组: [1, 1, 2, 3, 4, 5, 6, 9]

实践练习

练习1：基础实现 根据上面的算法描述和代码，尝试自己从头编写 selection_sort_desc 函数，实现降序排序（从大到小）。

def selection_sort_desc(arr):
    # 在此实现你的代码
    pass

# 测试
test_arr = [4, 2, 8, 1, 6]
selection_sort_desc(test_arr)
print(test_arr) # 预期输出: [8, 6, 4, 2, 1]

练习2：统计交换次数 修改选择排序算法，使其在排序过程中统计并返回总共进行了多少次元素交换。思考：在什么情况下交换次数最少？什么情况下最多？

def selection_sort_count_swaps(arr):
    swaps = 0
    # 在此实现你的代码，记得更新 swaps 变量
    return arr, swaps

# 测试
arr, swap_count = selection_sort_count_swaps([5, 1, 4, 2, 8])
print("排序结果:", arr)
print("交换次数:", swap_count) # 预期输出: 交换次数应为 3

练习3：选择最大值 重新设计算法思路，改为每次从未排序区间选择最大值，然后交换到未排序区间的末尾。实现 selection_sort_by_max 函数。

def selection_sort_by_max(arr):
    # 实现一个每次选择最大值的版本
    pass

# 测试
test_arr = [3, 7, 1, 9, 4]
selection_sort_by_max(test_arr)
print(test_arr) # 预期输出: [1, 3, 4, 7, 9]

常见错误

循环边界错误：外层循环写成 for i in range(n) 或内层循环写成 for j in range(i, n)。这会导致最后一个元素没有被正确比较或产生数组越界错误。
遗漏交换步骤：只找到了最小值索引 min_index，但忘记执行 arr[i], arr[min_index] = arr[min_index], arr[i] 的交换操作，或者交换逻辑写错。
混淆内层循环的起始：内层循环 j 应该从 i+1 开始，而不是从 0 开始。因为位置 i 之前的元素已经是有序的了，无需再参与比较。
不必要交换：当 min_index == i 时（即最小的元素已经在正确的位置），依然执行交换。虽然这不会影响结果，但增加了不必要的操作。用 if min_index != i: 判断可以优化。
认为选择排序是稳定排序：这是一个重要概念错误。选择排序是不稳定的排序算法。因为在交换过程中，可能会改变相等元素的原始相对顺序。例如，排序 (5a, 3, 5b, 1)，第一次交换后，5a 和 5b 的顺序可能被改变。

小结

核心思想：每一轮从未排序区间中选出最小（或最大）的元素，将其放到已排序区间的末尾。
关键操作：比较（查找极值）和交换。
时间复杂度：无论数据初始状态如何，比较次数都是 $O(n^2)$，交换次数是 $O(n)$（因为每轮最多交换一次）。总的时间复杂度为 $O(n^2)$。
空间复杂度：$O(1)$，只需要常数级别的额外空间用于临时变量，是原地排序算法。
稳定性：不稳定排序算法。
与冒泡排序对比：冒泡排序是通过相邻元素不断交换把最大值“浮”到顶端，交换非常频繁；而选择排序是先找到极值再交换，交换次数少，但比较次数两者都是 $O(n^2)$。
适用场景：由于时间复杂度较高，不适用于大规模数据。但其思想简单，且交换次数少的特性在对交换操作代价很高的场景下（例如元素是非常大的对象）可能有一定优势。对于初学者理解排序算法和“分治”思想很有帮助。

下一课预告：我们将学习另一种简单直观的排序算法——插入排序，它的思想类似于我们整理手中的扑克牌。

练习编辑器

rust