本课时有配套视频讲解，购买后即可观看（永久有效）
选择排序
一、课上练习
编程练习
二、知识总结
✨ 选择排序的核心思想
对一组线性存储的数据进行排序。
选择排序通过不断选择未排序部分中的最值元素，将其放在已排序部分的末尾实现排序。选择排序是使用了贪心法的排序算法，每一步都选择当前最优的元素放到正确位置。
✨ 选择排序的原理
选择排序的执行步骤如下：
- 初始化：标记已排序部分为空
- 在未排序部分中找到最值元素（升序找最小，降序找最大）
- 交换最值元素与未排序部分的第一个元素
- 更新已排序部分（已排序部分增加一个元素）
- 重复步骤 2-4，直到所有元素都已排序
从小到大排序
选择排序从小到大代码示例
1#include <bits/stdc++.h>
2using namespace std;
3
4int arr[1003] = {};
5
6int main() {
7 int n;
8 cin >> n;
9 for (int i = 0; i < n; ++i) {
10 cin >> arr[i];
11 }
12 for (int i = 0; i < n - 1; ++i) {
13 int min_idx = i;
14 for (int j = i + 1; j < n; ++j) {
15 if (arr[j] < arr[min_idx]) {
16 min_idx = j;
17 }
18 }
19 swap(arr[i], arr[min_idx]);
20 }
21 for (int i = 0; i < n; ++i) {
22 cout << arr[i] << (i + 1 == n ? "\n" : " ");
23 }
24 return 0;
25}从大到小排序
只需将比较条件从 < 改为 >，每次选择未排序部分中的最大值：
选择排序从大到小代码示例
1#include <bits/stdc++.h>
2using namespace std;
3
4int arr[1003] = {};
5
6int main() {
7 int n;
8 cin >> n;
9 for (int i = 0; i < n; ++i) {
10 cin >> arr[i];
11 }
12 for (int i = 0; i < n - 1; ++i) {
13 int max_idx = i;
14 for (int j = i + 1; j < n; ++j) {
15 if (arr[j] > arr[max_idx]) {
16 max_idx = j;
17 }
18 }
19 swap(arr[i], arr[max_idx]);
20 }
21 for (int i = 0; i < n; ++i) {
22 cout << arr[i] << (i + 1 == n ? "\n" : " ");
23 }
24 return 0;
25}✨ 选择排序的复杂度分析
| 指标 | 值 |
|---|---|
| 时间复杂度 | O(n^2) |
| 空间复杂度 | O(1) |
| 稳定性 | 不稳定排序 |
选择排序的时间复杂度为 O(n^2)，因为需要两层嵌套循环。空间复杂度为 O(1)，只需要常数级别的额外空间用于交换。选择排序是不稳定的排序算法，因为交换操作可能改变相等元素的相对顺序。
✨ 选择排序的执行示例
以数组 [5, 3, 8, 1, 2] 为例，展示从小到大的选择排序完整过程：
第1轮（i=0）：在 [5, 3, 8, 1, 2] 中找最小值
| 比较 | min_idx | 原因 |
|---|---|---|
| arr[1]=3 < arr[0]=5 | 1 | 3 比 5 小，更新 min_idx |
| arr[2]=8 < arr[1]=3? | 1 | 8 不比 3 小，不更新 |
| arr[3]=1 < arr[1]=3 | 3 | 1 比 3 小，更新 min_idx |
| arr[4]=2 < arr[3]=1? | 3 | 2 不比 1 小，不更新 |
交换 arr[0] 和 arr[3]：[1, 3, 8, 5, 2]（1 就位）
第2轮（i=1）：在 [3, 8, 5, 2] 中找最小值
| 比较 | min_idx | 原因 |
|---|---|---|
| arr[2]=8 < arr[1]=3? | 1 | 不更新 |
| arr[3]=5 < arr[1]=3? | 1 | 不更新 |
| arr[4]=2 < arr[1]=3 | 4 | 2 比 3 小，更新 min_idx |
交换 arr[1] 和 arr[4]：[1, 2, 8, 5, 3]（2 就位）
第3轮（i=2）：在 [8, 5, 3] 中找最小值
找到最小值 3 在位置 4，交换 arr[2] 和 arr[4]：[1, 2, 3, 5, 8]（3 就位）
第4轮（i=3）：在 [5, 8] 中找最小值
找到最小值 5 在位置 3（就是当前位置），无需交换：[1, 2, 3, 5, 8]（5 就位）
排序完成：[1, 2, 3, 5, 8]
总结： 5 个元素需要 4 轮选择，n 个元素需要 n-1 轮。
✨ 选择排序的解题步骤
例题：对学生成绩进行排名，成绩相同时按学号排序
分析过程：
- 选择排序的基本框架不变：外层循环 n-1 轮，内层循环找最值
- 修改比较条件：不能只比较成绩，当成绩相同时还要比较学号
- 使用结构体存储数据：每个元素包含学号和成绩两个信息
1struct Student {
2 int id, score;
3};
4
5Student stu[1005];
6
7// 选择排序：成绩从高到低，相同成绩按学号从小到大
8for (int i = 0; i < n - 1; ++i) {
9 int best = i;
10 for (int j = i + 1; j < n; ++j) {
11 if (stu[j].score > stu[best].score ||
12 (stu[j].score == stu[best].score && stu[j].id < stu[best].id)) {
13 best = j;
14 }
15 }
16 swap(stu[i], stu[best]);
17}关键思路： 选择排序的核心只是"找最值然后交换"，修改比较条件就能适应不同的排序需求。
✨ 选择排序的常见错误
- 内层循环起始位置错误：内层循环应从
i+1开始，而不是从0开始。从 0 开始会重复比较已排序的部分，虽然结果正确但浪费时间 - 忘记用变量记录最小值位置：直接在循环中交换，导致每次找到更小值就交换一次，增加了不必要的交换次数
- 交换自己和自己：当最小值就在位置 i 时，
swap(arr[i], arr[i])虽然不会出错，但可以加一个if (min_idx != i)判断来避免无效操作 - 外层循环次数错误：n 个元素只需要 n-1 轮，写成
i < n会导致内层循环j = i+1越界（虽然不一定报错，但逻辑上不正确） - 误认为选择排序是稳定的：选择排序是不稳定的。例如 [5a, 5b, 3]，第1轮会把 5a 和 3 交换，变成 [3, 5b, 5a]，两个 5 的相对顺序改变了