Python算法——选择排序
选择排序（Selection Sort）是一种简单的排序算法，它的基本思想是在未排序的部分中选择最小（或最大）的元素，然后将其放在已排序部分的末尾。选择排序不同于冒泡排序，它不需要反复交换元素，因此在某些情况下可能比冒泡排序更快。本文将详细介绍选择排序的工作原理和Python实现。
选择排序的工作原理
选择排序的基本思想是：
- 从未排序的数组中找到最小的元素。
- 将最小元素与未排序部分的第一个元素交换位置。
- 重复上述两步，不断扩大已排序部分，缩小未排序部分，直到整个数组有序。
选择排序的核心思想是每一轮选择一个最小的元素，并将它交换到已排序部分的末尾。这一过程持续多轮，每轮选择一个最小的元素，直到整个数组有序。
下面是一个示例，演示选择排序的过程。我们以升序排序为例：
原始数组：[64, 25, 12, 22, 11]
- 第一轮选择，最小元素为 11，交换位置后数组变为：[11, 25, 12, 22, 64]
- 第二轮选择，最小元素为 12，交换位置后数组变为：[11, 12, 25, 22, 64]
- 第三轮选择，最小元素为 22，交换位置后数组变为：[11, 12, 22, 25, 64]
- 第四轮选择，最小元素为 25，交换位置后数组变为：[11, 12, 22, 25, 64]
- 第五轮选择，最小元素为 64，交换位置后数组不变：[11, 12, 22, 25, 64]
Python实现选择排序
下面是Python中的选择排序实现：
def selection_sort(arr):n = len(arr)for i in range(n):min_index = ifor j in range(i+1, n):if arr[j] < arr[min_index]:min_index = jarr[i], arr[min_index] = arr[min_index], arr[i]
- arr 是待排序的数组。
- n 表示数组的长度。
- 外层循环 for i in range(n) 用于控制遍历的轮数。
- 内层循环 for j in range(i+1, n) 用于查找未排序部分中的最小元素。
- min_index 用于记录最小元素的索引，如果找到更小的元素，更新 min_index。
- 在内层循循环结束后，将最小元素与当前轮次的第一个元素交换位置。
示例代码
下面是一个使用Python进行选择排序的示例代码：
def selection_sort(arr):n = len(arr)for i in range(n):min_index = ifor j in range(i+1, n):if arr[j] < arr[min_index]:min_index = jarr[i], arr[min_index] = arr[min_index], arr[i]# 测试排序
arr = [64, 25, 12, 22, 11]
selection_sort(arr)
print("排序后的数组:", arr)
时间复杂度
选择排序的时间复杂度为 O(n^2)，其中 n 是数组的长度。与冒泡排序一样，选择排序不是最高效的排序算法，但它是一种简单易懂的算法，适用于小型数据集。
总之，选择排序是一种简单的排序算法，通过选择最小元素并将其放在已排序部分的末尾，实现了排序数组的目标。了解选择排序有助于理解排序算法的基本原理，并为学习更高效的排序算法奠定了基础。