对一组线性存储的数据进行排序。
选择排序通过不断选择未排序部分中的最值元素，将其放在已排序部分的末尾实现排序。选择排序是使用了贪心法的排序算法，每一步都选择当前最优的元素放到正确位置。
选择排序的执行步骤如下：
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] 为例，展示从小到大的选择排序完整过程：
| 比较 | 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 就位）
| 比较 | 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 在位置 4，交换 arr[2] 和 arr[4]：[1, 2, 3, 5, 8]（3 就位）
找到最小值 5 在位置 3（就是当前位置），无需交换：[1, 2, 3, 5, 8]（5 就位）
排序完成：[1, 2, 3, 5, 8]
总结： 5 个元素需要 4 轮选择，n 个元素需要 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 开始会重复比较已排序的部分，虽然结果正确但浪费时间swap(arr[i], arr[i]) 虽然不会出错，但可以加一个 if (min_idx != i) 判断来避免无效操作i < n 会导致内层循环 j = i+1 越界（虽然不一定报错，但逻辑上不正确）