什么是选择排序？¶
选择排序是一种简单直观的排序算法，它的核心思想是每次从待排序的元素中找出最小（或最大）的元素，然后将其放到已排序部分的末尾，直到所有元素都排好序。想象一下整理一叠打乱的扑克牌：你会从牌堆中一张一张挑出最小的牌，按顺序放在桌子的左边，直到所有牌都排好序。
选择排序的步骤¶
- 初始化：假设数组的第一个元素是当前最小的元素（即位置0为已排序部分的末尾）。
- 遍历寻找最小值：从当前未排序部分的下一个元素开始，遍历整个未排序区域，找到比当前最小值更小的元素，更新最小值的位置。
- 交换位置：将找到的最小值与当前未排序部分的第一个元素交换位置，此时该元素就被“固定”在已排序部分的末尾。
- 重复操作：重复上述步骤，直到未排序部分为空（即所有元素都已排好序）。
Python代码实现¶
下面是选择排序的Python实现，代码中包含详细注释，方便理解每一步：
def selection_sort(arr):
# 获取数组长度
n = len(arr)
# 外层循环：控制需要排序的元素范围（从0到n-2，因为最后一个元素无需排序）
for i in range(n - 1):
# 假设当前位置i的元素是最小值
min_index = i
# 内层循环：从i+1到n-1寻找更小的元素
for j in range(i + 1, n):
# 如果找到更小的元素，更新最小值的位置
if arr[j] < arr[min_index]:
min_index = j
# 交换当前位置i的元素与找到的最小值元素
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
# 测试代码
if __name__ == "__main__":
# 未排序的数组
unsorted = [64, 25, 12, 22, 11]
print("排序前：", unsorted)
# 调用选择排序函数
sorted_arr = selection_sort(unsorted)
print("排序后：", sorted_arr)
代码解释¶
- 外层循环：变量
i从0到n-2（range(n-1)），表示已排序部分的末尾位置。每次循环结束后，arr[i]会被固定为已排序部分的第i个元素（即最小值）。 - 内层循环：变量
j从i+1到n-1，遍历未排序部分的所有元素，找到最小元素的位置min_index。 - 交换操作：找到最小值后，通过
arr[i], arr[min_index] = arr[min_index], arr[i]交换元素，确保最小值被“放到”已排序部分的末尾。
运行结果¶
运行上述测试代码，输出如下：
排序前： [64, 25, 12, 22, 11]
排序后： [11, 12, 22, 25, 64]
复杂度分析¶
- 时间复杂度：无论输入数据如何，选择排序都需要进行两层循环（外层
n次，内层n次），因此时间复杂度为O(n²)（n为数组长度）。 - 空间复杂度：选择排序是原地排序算法，不需要额外的数组空间，因此空间复杂度为O(1)。
选择排序的特点¶
- 简单直观：逻辑清晰，容易理解和实现，适合初学者学习排序算法的基本思想。
- 不稳定排序：如果数组中有相同元素，交换过程可能导致它们的相对顺序改变（例如数组
[2, 2, 1]排序后可能变成[1, 2, 2]，但原数组中第一个2可能和第二个2的顺序被交换）。 - 原地排序：不需要额外空间，仅通过交换元素完成排序。
选择排序虽然时间复杂度较高，但在小规模数据排序中仍有实用价值，尤其适合理解排序算法的基本思想。通过上述步骤和代码，你已经掌握了如何用Python实现选择排序！