python怎么实现最简单的选择排序

# Python怎么实现最简单的选择排序 选择排序（Selection Sort）是最基础的排序算法之一，其核心思想是每次从未排序部分选出最小（或最大）元素，放到已排序部分的末尾。本文将详细介绍如何用Python实现最简单的选择排序，并分析其时间复杂度和适用场景。 --- ## 一、选择排序算法原理 ### 1. 算法步骤 1. **初始状态**：整个数组分为已排序区（空）和未排序区（完整数组） 2. **迭代过程**： - 在未排序区中找到最小元素 - 将该元素与未排序区的第一个元素交换位置 - 已排序区长度+1，未排序区长度-1 3. **终止条件**：未排序区只剩1个元素时自动有序 ### 2. 动态示意图 

初始：[64, 25, 12, 22, 11] 第1轮：[11, 25, 12, 22, 64] # 11与64交换 第2轮：[11, 12, 25, 22, 64] # 12与25交换 第3轮：[11, 12, 22, 25, 64] # 22与25交换 第4轮：[11, 12, 22, 25, 64] # 已有序

 --- ## 二、Python实现代码 ### 基础实现版本 ```python def selection_sort(arr): n = len(arr) for i in range(n-1): # 只需要n-1轮 # 找到未排序部分的最小值索引 min_idx = i for j in range(i+1, n): if arr[j] < arr[min_idx]: min_idx = j # 交换位置 arr[i], arr[min_idx] = arr[min_idx], arr[i] return arr # 测试用例 print(selection_sort([64, 25, 12, 22, 11])) # 输出 [11, 12, 22, 25, 64] 

优化版本（同时找最小和最大值）

def selection_sort_optimized(arr): n = len(arr) for i in range(n//2): min_idx, max_idx = i, n-i-1 for j in range(i+1, n-i): if arr[j] < arr[min_idx]: min_idx = j if arr[j] > arr[max_idx]: max_idx = j arr[i], arr[min_idx] = arr[min_idx], arr[i] # 处理最大值可能被移动的情况 if max_idx == i: max_idx = min_idx arr[n-i-1], arr[max_idx] = arr[max_idx], arr[n-i-1] return arr 

---

三、算法分析

时间复杂度

场景	复杂度
最好情况	O(n²)
最坏情况	O(n²)
平均情况	O(n²)

空间复杂度

• O(1)（原地排序）

稳定性

• 不稳定排序（交换可能改变相等元素的相对位置）

---

四、选择排序的特点

优点

1. 实现简单直观
2. 不占用额外内存空间
3. 对于小规模数据效率尚可

缺点

1. 时间复杂度较高，不适合大数据量
2. 不稳定排序
3. 无论输入数据是否有序，都需要完成全部比较

---

五、选择排序 vs 冒泡排序

特性	选择排序	冒泡排序
交换次数	O(n)	O(n²)
比较次数	O(n²)	O(n²)
稳定性	不稳定	稳定
最佳情况	仍需全部比较	可提前终止

---

六、实际应用场景

1. 教学演示基础排序原理
2. 数据量极小（n < 100）的排序需求
3. 内存严格受限的环境
4. 需要减少交换次数的场景（如交换成本高的数据结构）

---

七、扩展练习

1. 尝试实现降序排列版本
2. 修改算法使其变为稳定排序
3. 用选择排序实现字符串数组的字典序排序
4. 比较选择排序与插入排序的性能差异

选择排序虽然简单，但包含了算法设计中”选择-交换”的核心思想，是理解更复杂排序算法的重要基础。 “`