当前位置：首页 > news >正文

数据结构：选择排序 (Selection Sort)

news 2025/8/30 9:08:06

从学生排队开始

算法的初始状态和核心操作

代码的逐步完善

第一阶段：定义函数框架和外层循环

第二阶段：实现“寻找最小元素”的逻辑（内层循环）

第三阶段：完成“交换”操作

复杂度与特性分析

时间复杂度 (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)：
1. 扫描整个数组，发现最小元素是 2。
2. 将 2 与无序区的第一个元素 arr[0] (也就是 5a) 进行交换。
3. 交换后，数组变为 [2, 8, 5b, 5a]。
观察结果：在原始数组中，5a 在 5b 的前面。但在第一轮排序后，5a 跑到了 5b 的后面。它们的相对位置发生了改变。
仅仅一个反例就足以证明，选择排序不是一个稳定的排序算法。
因此，选择排序是❌不稳定排序 (Unstable Sort)。