一、选择排序的定义
选择排序（Selection Sort）是一种不稳定的原地比较排序，它的核心思想是每轮遍历选择最小（或最大）元素放入合适位置，最终完成排序。该算法适用于小规模数据排序，尤其是在对数据稳定性要求不高的场景中。
二、选择排序的发展历史
选择排序最早由计算机科学家提出，作为最基本的排序算法之一，它在计算机科学教育中被广泛用于教学。虽然在实际应用中不如快速排序等高效算法常用，但其直观的选择过程使其成为算法学习的基础。
三、选择排序的排序过程
选择排序的基本步骤如下：
- 遍历数组，找到最小元素：从数组未排序部分选出最小（或最大）元素；
- 交换元素：将最小（或最大）元素与当前遍历的起始位置元素进行交换；
- 重复上述步骤：逐轮确定一个最小值，并放置在正确的位置，直到整个数组有序。
例如，对 [64, 25, 12, 22, 11] 进行升序排序：
初始数组：[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]
最终结果：[11, 12, 22, 25, 64]
可以看到，每轮都找到了最小元素，并将其交换到正确的位置。
四、选择排序的基本原理
选择排序的核心思想是不断选择未排序部分的最小值，并与当前轮次的起始元素进行交换。
其原理可以概括如下：
- 假设前
i个元素已排序，从未排序的n - i个元素中找到最小值； - 将最小值放在第
i位，确保前i + 1个元素已经排序； - 重复
n-1轮，最终数组有序。
该算法的时间复杂度为 O(n²)，空间复杂度为 O(1)，因为它只使用了少量额外的变量。
五、选择排序的特点
- 不稳定：当某个最小元素被交换时，可能会改变相等元素的相对顺序。
- 时间复杂度恒定：无论初始数据是否有序，选择排序始终执行 O(n²) 级别的比较操作。
- 空间占用小：不需要额外的辅助存储空间，仅使用常数级别的辅助变量。
六、选择排序的优点
- 交换次数少：相比冒泡排序，选择排序的交换次数较少，每轮最多一次交换，提高了效率；
- 适用于小规模数据排序：在数据量较小时，仍然可以较快完成排序；
- 不依赖数据初始状态：无论数据是否有序，选择排序的执行流程一致。
七、选择排序的缺点
- 时间复杂度高：无论数据是否已部分有序，选择排序始终需要 O(n²) 次比较；
- 不稳定：如果相同元素被交换，可能会打乱其原始相对顺序；
- 不适用于大规模数据：在数据量较大时，选择排序的效率较低，不如快速排序或归并排序等高效算法。
Python 代码实现
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 # 更新最小值索引arr[i], arr[min_idx] = arr[min_idx], arr[i] # 交换当前元素和最小元素return arr# 测试
print(selection_sort([64, 25, 12, 22, 11]))
代码解析
- 外层循环 (
for i in range(n))：遍历整个数组，确定当前位置的元素； - 内层循环 (
for j in range(i+1, n))：从未排序部分找最小值； min_idx = j：更新最小值的索引；arr[i], arr[min_idx] = arr[min_idx], arr[i]：找到最小值后进行交换。
代码运行结果
[11, 12, 22, 25, 64]
总结
选择排序通过不断寻找最小元素并交换位置，实现数组的排序。虽然它具有较好的直观性，但由于其时间复杂度较高，不适合大规模数据处理。它的优势在于较少的交换次数，但劣势是不稳定且对已排序数组没有优化。
