目录
从学生排队开始
算法的初始状态和核心操作
代码的逐步完善
第一阶段：定义函数框架和外层循环
第二阶段：实现“寻找最小元素”的逻辑（内层循环）
第三阶段：完成“交换”操作
复杂度与特性分析
时间复杂度 (Time Complexity)
空间复杂度 (Space Complexity)
稳定性 (Stability)
从学生排队开始
我们已经探讨了两种排序思路：
-
冒泡排序：不断比较相邻的元素，像“本地微调”，慢慢把大的元素换到后面。
-
插入排序：始终维护一个有序的局部，然后把新元素插入进去。
现在我们思考一种完全不同的、更具“全局观”的策略。想象一下，老师让一队学生按身高从矮到高排队。老师会怎么做？
一种非常直接的方法是：
-
老师先扫视所有未排队的学生，从中找出最矮的那一个。
-
然后指着队伍的最前面说：“你，站到这里来。”
-
接着，老师在剩下的学生中，再扫视一遍，找出剩下人里最矮的。
-
然后指着队伍的第二个位置说：“你，站到这里来。”
-
重复这个过程，直到所有学生都排好队。
这个“每次选择一个最值，放到它最终应该在的位置”的思路，就是选择排序的灵魂。
算法的初始状态和核心操作
和插入排序一样，我们也将数组在逻辑上分为两个部分：
左边是已经排好序、元素都已在最终位置的有序区。
右边是还未处理、元素位置都是临时的无序区。
算法开始时，有序区是空的，整个数组都是无序区。
📌 核心操作（一轮迭代）：
-
在无序区中，通过一次完整的扫描，找到值最小的那个元素。
-
将这个最小的元素与无序区的第一个元素交换位置。
-
交换完成后，无序区的第一个元素就变成了有序区的最后一个元素。有序区长度加一，无序区长度减一。
我们来手动模拟一下。假设数组是 arr = [64, 25, 12, 22, 11]
-
有序区:
[] -
无序区:
[64, 25, 12, 22, 11]
1️⃣ 第一轮 (i=0)：
-
扫描无序区
[64, 25, 12, 22, 11]。 -
发现最小的元素是
11，它的索引是4。 -
将
11与无序区的第一个元素64交换。
-
✅ 结果：
[**11**, 25, 12, 22, 64]。现在11已经在它的最终位置了。 -
有序区:
[11], 无序区:[25, 12, 22, 64]
2️⃣ 第二轮 (i=1)：
-
扫描无序区
[25, 12, 22, 64]。 -
发现最小的元素是
12，它的索引是2。 -
将
12与无序区的第一个元素25交换。
-
✅ 结果：
[11, **12**, 25, 22, 64]。现在12也归位了。 -
有序区:
[11, 12], 无序区:[25, 22, 64]
这个过程持续
n-1轮，当n-1个元素都归位后，剩下的最后一个元素自然也在正确的位置上了。
代码的逐步完善
现在，我们将这个“选择-交换”的策略翻译成代码。
第一阶段：定义函数框架和外层循环
外层循环的职责是控制轮次，也就是每次为哪个位置寻找正确的元素。
i 将代表当前“坑位”的索引，我们要在无序区中找到元素来填这个“坑”。
#include <iostream>void swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp;
}// 选择排序函数框架
void selectionSort(int arr[], int n) {// 外层循环控制轮次，i 是当前要放置正确元素的目标位置// 我们需要为 arr[0], arr[1], ..., arr[n-2] 依次寻找元素// 当 arr[n-2] 也正确时，arr[n-1] 必然也正确了for (int i = 0; i < n - 1; ++i) {// 在这里，我们将找到无序区 arr[i...n-1] 中的最小元素，// 然后把它放到 arr[i] 这个位置上。}
}第二阶段：实现“寻找最小元素”的逻辑（内层循环）
在每一轮中，我们需要一个内层循环来扫描整个无序区，目的是找到最小元素的索引。
void selectionSort(int arr[], int n) {for (int i = 0; i < n - 1; ++i) {// 1. 先假设当前无序区的第一个元素就是最小的int min_idx = i;// 2. 用内层循环扫描无序区的其他元素for (int j = i + 1; j < n; ++j) {// 如果发现了更小的元素...if (arr[j] < arr[min_idx]) {// ...就更新最小元素的索引min_idx = j;}}// 当这个内层循环结束后，min_idx 就一定指向了// 整个无序区中最小元素的实际位置。// 接下来就是交换操作了。}
}第三阶段：完成“交换”操作
找到了最小元素的索引 min_idx 后，我们只需要将它和当前轮次的目标位置 i 的元素进行一次交换。这个交换操作发生在内层循环结束之后。
void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {std::cout << arr[i] << " ";}std::cout << std::endl;
}// 最终的选择排序代码
void selectionSort(int arr[], int n) {for (int i = 0; i < n - 1; ++i) {// 寻找 [i, n-1] 区间里的最小元素int min_idx = i;for (int j = i + 1; j < n; ++j) {if (arr[j] < arr[min_idx]) {min_idx = j;}}// 将找到的最小元素与 i 位置的元素交换swap(&arr[min_idx], &arr[i]);std::cout << "第 " << i + 1 << " 轮排序后: ";printArray(arr, n);}
}至此，一个从“全局选择最优”这个第一性原理出发的选择排序算法就清晰地构建完成了。
复杂度与特性分析
我们用之前建立的评判标准来分析它。
时间复杂度 (Time Complexity)
-
算法的主要耗时在于嵌套的循环。
-
外层循环执行
n-1次。 -
内层循环的执行次数：
-
当
i=0时，比较n-1次。 -
当
i=1时，比较n-2次。 -
...
-
当
i=n-2时，比较1次。
-
-
-
总的比较/移动次数大约是 1 + 2 + ... + (n−1) = n * (n−1) / 2。
⚠️ 请注意，无论输入的数组是已经有序、还是完全逆序，选择排序的这个比较次数是固定不变的。
因为它必须完整地扫描完无序区，才能确认哪个是最小的。它无法像插入排序或优化后的冒泡排序那样提前结束。
因此，选择排序的最好、最坏和平均情况的时间复杂度都是：O(n^2)
空间复杂度 (Space Complexity)
-
在排序过程中，我们只使用了
i,j,min_idx这几个辅助变量。 -
变量数量是固定的常数，不随
n的增长而增长。 -
因此，空间复杂度是：O(1)
-
它也是一个原地排序 (In-place Sort) 算法。
稳定性 (Stability)
-
这是选择排序一个非常重要的特性。我们来举个例子判断一下。
-
假设数组是
[5a, 8, 5b, 2](这里5a和5b值相等，但我们为了区分，加上了标记)。 -
第一轮 (i=0)：
-
扫描整个数组，发现最小元素是
2。 -
将
2与无序区的第一个元素arr[0](也就是5a) 进行交换。 -
交换后，数组变为
[2, 8, 5b, 5a]。
-
-
观察结果：在原始数组中，
5a在5b的前面。但在第一轮排序后，5a跑到了5b的后面。它们的相对位置发生了改变。 -
仅仅一个反例就足以证明，选择排序不是一个稳定的排序算法。
-
因此，选择排序是❌不稳定排序 (Unstable Sort)。
选择排序的特点非常鲜明：它的时间复杂度很“死板”，不受输入数据的影响，始终是 O(n^2)。
但它有一个优点，就是数据交换的次数非常少，最多只有 n-1 次。在一些“写”操作远比“读”操作昂贵的场景下，这可能成为一个考虑因素。
