Python生成随机数并使用选择排序算法排序

在 Python 编程实践与算法入门中，生成一组无序的随机数据并对其进行排序是最具代表性的练习之一。本文的核心目标是使用 Python 内置的 random 模块生成指定数量与范围的随机整数列表，随后编写原生的选择排序（Selection Sort）算法对该列表完成升序排列与降序扩展，并通过逐步拆解与结构图示深入理解算法内部的极值检索与元素交换逻辑。

一、准备工作：使用 random 模块生成随机整数列表

在对列表执行排序前，首先需要构造一组用于测试的无序数据。Python 标准库自带了 random 模块，无需额外安装任何第三方依赖即可快速生成均匀分布的随机数。

最常用的生成方式是结合列表推导式与 random.randint(a, b) 函数。randint(a, b) 会返回一个位于闭区间 [a, b] 内的随机整数，两端端点均包含在内。若希望生成 10 个介于 10 到 99 之间的随机整数，代码结构如下：

import random

# 生成包含 10 个随机整数的列表（取值范围 10 到 99）
count = 10
random_list = [random.randint(10, 99) for _ in range(count)]
print("初始随机列表:", random_list)

这种写法允许列表中存在重复的数字。如果测试场景严格要求生成不重复的随机数字，可以使用 random.sample() 从指定范围中进行无放回抽样，例如 random.sample(range(10, 100), 10)。在常规算法演示中，允许重复数字更能全面检验排序算法对边界情况的处理能力。

图 1: Python 生成测试随机数列表的全流程结构

二、选择排序算法的核心思想与执行机制

选择排序是一种直观的比较类排序算法。它的核心机制是将整个数组从逻辑上划分为两个部分：左侧的“已排序区间”与右侧的“未排序区间”。初始状态下，已排序区间为空，所有元素均处于未排序区间。

每一轮排序时，算法会遍历未排序区间中的所有数值，找出其中的最小元素（升序排列），并将其与未排序区间的第一个元素进行位置互换。经过这次交换后，该最小元素正式归入已排序区间的末尾，未排序区间的起始下标随之向右推移一位。重复这一过程，直到整个列表中所有元素均完成归位。

以数组 [42, 17, 89, 12, 65, 33] 的第一轮（索引 i = 0）为例：

1. 假定当前索引 0 处的元素 42 为当前最小值，记录 min_index = 0。
2. 从索引 1 开始向右扫描：比较 17 < 42，更新 min_index = 1。
3. 继续扫描：89 > 17 不变；遍历到索引 3 时，发现 12 < 17，再次更新 min_index = 3。
4. 扫描剩余的 65 和 33，均不小于 12。内层扫描结束，确定全局最小值为 12（索引 3）。
5. 此时 min_index != 0，将索引 0 的 42 与索引 3 的 12 交换位置。数组变为 [12, 17, 89, 42, 65, 33]。

图 2: 选择排序单轮扫描与极值交换原理图

三、Python 完整代码实现与逐步拆解

在 Python 中编写选择排序算法时，双层嵌套循环是最标准且清晰的写法。外层循环负责定义未排序区间的边界索引 i，内层循环则负责在未排序区间中寻找真正的极值下标。

以下是完整的端到端代码实现，包含随机数生成、选择排序函数定义、原地排序执行与排序前后对比输出：

import random

def selection_sort(arr):
    """
    对传入的列表执行就地升序选择排序。
    参数:
        arr: 包含可比较元素的列表 (List)
    返回:
        排序后的列表自身
    """
    n = len(arr)
    # 外层循环：只需遍历到倒数第二个位置 (n - 1)
    for i in range(n - 1):
        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]
            
    return arr

# 示例驱动执行流程
if __name__ == "__main__":
    # 1. 设定随机种子(可选，用于结果复现)并生成 10 个范围在 1~100 的随机数
    random.seed(42)
    sample_data = [random.randint(1, 100) for _ in range(10)]
    
    print("【排序前原始随机列表】:")
    print(sample_data)
    
    # 2. 调用选择排序函数
    sorted_data = selection_sort(sample_data)
    
    print("\n【选择排序后升序列表】:")
    print(sorted_data)

运行上述代码后，终端将输出如下示例结果：

【排序前原始随机列表】:
[82, 15, 4, 95, 36, 32, 29, 18, 95, 14]

【选择排序后升序列表】:
[4, 14, 15, 18, 29, 32, 36, 82, 95, 95]

图 3: 选择排序算法的核心控制流程图

四、关键细节与常见疑问分析

初学者在编写选择排序时常会产生几个疑问，理解这些细节有助于掌握该算法与冒泡排序、插入排序的根本区别：

1. 为什么外层循环只需遍历到 n - 1？

因为当外层循环执行完前 n - 1 轮后，列表中前 n - 1 个较小的元素已经全部归位到了各自正确的索引上。此时未排序区间只剩下唯一个位于末尾的元素，它必然是全局最大的元素，已经天然处于正确位置，无需再执行最后一次无意义的单元素扫描。

2. 为什么选择排序的交换次数远少于冒泡排序？

在冒泡排序中，只要相邻两个元素逆序就会立即发生一次数据交换；若数据高度无序，冒泡排序可能触发高达 O(n²) 次物理写交换。而选择排序在内层循环中仅记录极值的索引编号，整个内层扫描期间不产生任何数组修改，直到该轮扫描彻底结束后才至多执行 1 次物理交换。因此，对于长度为 n 的数组，选择排序的总交换次数上限为 n - 1 次。

3. 如何将升序排列切换为降序排列？

要实现从大到小的降序排序，只需将比较逻辑反转。将内层循环中的变量名由 min_index 改为 max_index，并将判断条件由 if arr[j] < arr[min_index] 改为 if arr[j] > arr[max_index]，其余代码结构完全保持一致即可。

4. 选择排序是稳定排序算法吗？

选择排序是不稳定排序算法。长距离的直接位置交换可能会打破相同数值元素原有的相对前后次序。例如对列表 [5a, 8, 5b, 2] 进行升序排列：第一轮找到最小值为 2，与开头的 5a 交换位置，数组变为 [2, 8, 5b, 5a]。原本排在前面的 5a 被交换到了 5b 之后，两者的原有次序发生了逆转。

五、算法性能评估与总结

选择排序的逻辑直观、易于教学，但了解其性能边界在工程开发中至关重要：

• 时间复杂度恒定为 O(n²)：由于算法无法提前预知数组是否已经局部有序，无论传入的测试数组是已经完全排好序、完全逆序还是随机分布，内层循环都必须忠实地执行 (n-1) + (n-2) + ... + 1 = n(n-1)/2 次比较。因此它的最好、最坏和平均时间复杂度均为 O(n²)。
• 空间复杂度为 O(1)：选择排序完全在原列表的内存块上通过下标寻址进行就地交换，除了用于存储计数器与索引的变量（i, j, min_index）外，不需要申请任何与数据规模相关的额外辅助存储空间。
• 工程选型建议：在 Python 生产开发中，若处理海量数据应优先调用 Python 内置的 list.sort() 或 sorted()（底层基于优化后的 Timsort 算法，平均与最坏时间复杂度为 O(n log n)）。然而，若运行环境面对的是闪存、EEPROM 等“物理写擦除代价极其高昂”的特殊硬件介质，选择排序由于其极低且可控的写交换次数（最多 n-1 次），仍具备独特的架构价值。

图 4: 选择排序关键特性与工程决策总结卡片