C++ 选择排序详解

工作过程

选择排序（Selection Sort）是一种简单直观的排序算法。它的工作原理如下：

1. 首先，在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置。
2. 然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。
3. 重复第二步，直到所有元素均排序完毕。

简单来说：每一轮从未排序的部分中，选择一个最小的元素，放到已排序部分的末尾。

基本特性

• 时间复杂度：平均、最好、最坏情况下都是 O(n²)。因为它需要嵌套循环，外层循环 n-1 次，内层循环平均 n/2 次。比较次数固定为 n(n-1)/2。
• 空间复杂度：O(1)。因为它只需要常数个额外变量用于存储索引和临时交换，是原地排序。
• 稳定性：不稳定。在交换最小值到当前位置时，可能会改变相等元素的原始相对顺序。例如 [5, 8, 5, 2, 9]，第一轮找到 2，与第一个 5 交换，变成 [2, 8, 5, 5, 9]，两个 5 的相对顺序改变了。

核心逻辑

• 外层循环 i 从 0 到 n-2 (最后一个元素自然有序)。
• 内层循环 j 从 i+1 到 n-1，用于在 a[i...n-1] 范围内寻找最小值。
• 使用变量 minIdx 记录当前找到的最小元素的索引，初始设为 i。
• 内层循环结束后，如果 minIdx 不等于 i，则交换 a[i] 和 a[minIdx]。

减少不必要的交换

在内层循环找到最小元素索引 minIdx 后，如果 minIdx 恰好就是当前位置 i，说明 a[i] 已经是未排序部分的最小值，此时无需执行交换操作。这可以略微优化性能，尤其是在数组部分有序的情况下，可以减少写操作。

// 在交换前添加判断
if (minIdx != i) {
    swap(a[i], a[minIdx]);
}

注意：这个优化并不会改变算法的 O(n²) 时间复杂度，因为比较次数并未减少。

数组边界

实现时要特别注意循环的边界条件，防止数组越界访问：

• 外层循环 i 的范围通常是 0 到 n-2 (或 < n-1)。当 i 到达 n-1 时，只剩一个元素，无需再排序。
• 内层循环 j 的范围通常是 i+1 到 n-1 (或 < n)。确保 j 始终在数组的有效索引范围内。

适用场景

选择排序的主要优点是实现简单、空间复杂度低（O(1)）。但其 O(n²) 的时间复杂度使其不适合处理大规模数据集。

它主要用于：

• 教学目的：作为入门级排序算法，帮助理解排序的基本思想和复杂度分析。
• 小规模数据：当 n 非常小（例如小于几十或几百）时，其性能尚可接受，且实现简单。
• 写操作昂贵的场景：选择排序的交换次数是固定的 O(n) 次（最多 n-1 次），相比冒泡排序（最坏 O(n²) 次交换）在某些写操作成本极高的硬件或环境下可能有优势。

常见 O(n²) 排序算法比较

堆排序：选择排序的改进

选择排序每轮需要 O(n) 时间找到最小值。如果能用更高效的方式找到最小值，就能改进算法。堆排序（Heap Sort） 正是利用了堆（Heap）这种数据结构。

堆可以在 O(log n) 时间内找到并移除最值，同时维护堆的性质。通过先将数组构建成一个最大堆（或最小堆），然后重复取出堆顶元素（最值）放到数组末尾，堆排序将整体时间复杂度优化到了 O(n log n)。它同样是原地排序（O(1) 空间），但也是不稳定的。

可以认为堆排序是选择排序在选择最小值这一步上的高效优化版本。

稳定性的意义

排序算法的稳定性指的是：如果数组中有两个相等的元素，排序后它们的相对位置保持不变。

稳定性在某些场景下非常重要：

• 多级排序：例如，先按姓名排序，再按分数排序。如果按分数排序时使用了不稳定的算法，可能会打乱之前按姓名排好的顺序（对于分数相同的学生）。
• 保持原始关联信息：在某些数据处理中，元素的原始顺序可能隐含某种信息，需要保持相等元素的相对次序。
• 用户体验：在 UI 列表排序时，稳定的排序能给用户更一致和可预测的结果。

选择排序由于其交换操作的性质，通常是不稳定的。