def selection_sort(arr):
    n = len(arr)
    # 遍历所有数组元素
    for i in range(n):
        # 假设当前元素是最小的
        min_idx = i
        # 在剩余元素中寻找最小值
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        # 将找到的最小值与第i个元素交换
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

# 测试选择排序
data = [64, 25, 12, 22, 11]
print("原始数组:", data)
sorted_data = selection_sort(data)
print("排序后数组:", sorted_data)

代码解析

• 外层循环：遍历数组中的每个位置（i从0到n-1）
• 内层循环：在未排序部分（i+1到n-1）中查找最小元素的索引
• 交换操作：将找到的最小元素与当前位置元素交换
• 原地排序：直接在原数组上进行操作，不需要额外空间

选择排序的优化

虽然选择排序的时间复杂度难以突破O(n²)，但可以进行一些优化：

• 同时找最小和最大值：每次遍历同时找到最小和最大值，减少一半的遍历次数
• 减少交换次数：在找到最小值后再进行交换，而不是每次比较都交换
• 使用堆结构：使用堆来高效地查找最小元素，这就是堆排序的思想

def optimized_selection_sort(arr):
    n = len(arr)
    for i in range(n//2):
        min_idx, max_idx = i, i
        # 在未排序部分同时查找最小和最大值
        for j in range(i+1, n-i):
            if arr[j] < arr[min_idx]:
                min_idx = j
            elif 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

选择排序总结

选择排序是一种简单但效率不高的排序算法，主要特点：

• 优点：实现简单，交换次数少，原地排序
• 缺点：时间复杂度高，不适合大规模数据，不稳定排序
• 学习价值：理解基本排序思想，掌握算法分析基础
• 实际应用：通常用于教学场景或作为更复杂算法的组成部分

在实际应用中，对于需要排序的场景，Python内置的sorted()函数或列表的sort()方法（使用Timsort算法）是更好的选择。