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(1)（原地排序）

稳定性

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

四、选择排序的特点

优点

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

缺点

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

五、选择排序 vs 冒泡排序

六、实际应用场景

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

七、扩展练习

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

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