本课时有配套视频讲解，购买后即可观看（永久有效）
选择排序
课上练习
知识总结
选择排序-知识总结
选择排序-知识总结 解决问题 对一组线性存储的数据进行排序。
核心思想 选择排序通过不断选择未排序部分中的最值元素，将其放在已排序部分的末尾实现排序。是使用了贪心法的排序算法。
工作原理 原理介绍 初始化：标记已排序部分为空 ①在未排序部分中找到最值元素 ②交换最值元素与未排序的第一个元素 ③更新已排序部分 重复①②③至所有元素都已排序
代码模板
1// 从小到大排序
2#include <bits/stdc++.h>
3using namespace std;
4
5int arr[1003] = {};
6
7int main() {
8 int n;
9 cin >> n;
10 for (int i = 0; i < n; ++i) {
11 cin >> arr[i];
12 }
13 for (int i = 0; i < n - 1; ++i) {
14 int min_idx = i;
15 for (int j = i + 1; j < n; ++j) {
16 if (arr[j] < arr[min_idx]) {
17 min_idx = j;
18 }
19 }
20 swap(arr[i], arr[min_idx]);
21 }
22 for (int i = 0; i < n; ++i) {
23 cout << arr[i] << (i + 1 == n ? "\n" : " ");
24 }
25 return 0;
26}
27// 从大到小排序
28#include <bits/stdc++.h>
29using namespace std;
30
31int arr[1003] = {};
32
33int main() {
34 int n;
35 cin >> n;
36 for (int i = 0; i < n; ++i) {
37 cin >> arr[i];
38 }
39 for (int i = 0; i < n - 1; ++i) {
40 int max_idx = i;
41 for (int j = i + 1; j < n; ++j) {
42 if (arr[j] > arr[max_idx]) {
43 max_idx = j;
44 }
45 }
46 swap(arr[i], arr[max_idx]);
47 }
48 for (int i = 0; i < n; ++i) {
49 cout << arr[i] << (i + 1 == n ? "\n" : " ");
50 }
51 return 0;
52}算法评价 时间复杂度：O(n^2) 空间复杂度：O(n^2) 稳定性：不稳定排序
️课后作业
☝️总结作业
总结作业非常重要，请务必认真完成✔️
- 选择排序的核心思想是什么？
- 简单介绍选择排序的工作原理。
- 1s的时间内选择排序可以处理的数据规模最大是多少？
✌️编程作业
考试只有一次提交机会，请务必本地检查正确后再提交❇️
👌编程作业标准答案
请在AC后或者思考15分钟没有进展后查看，不可抄代码❇️
L2133题解+参考代码
L2133题解+参考代码 题目链接 数的排序：L2133
题解 我们需要对输入的 n 个整数，按其各位数字和从小到大排序。为此，我们可以使用选择排序算法来实现。
算法步骤 读取输入：读取整数 n 和 n 个整数。 计算每个数的各位数字和： 定义一个函数 digitSum，计算一个数的各位数字和。 选择排序： 使用选择排序对 n 个整数按照其各位数字和进行排序。 输出结果：输出排序后的每个数的各位数字和。 示例代码 这里是使用 C++ 实现的示例代码：
1#include <bits/stdc++.h>
2using namespace std;
3
4// 计算一个数的各位数字和
5int digitSum(int num) {
6 int sum = 0;
7 num = abs(num); // 处理负数情况
8 while (num > 0) {
9 sum += num % 10;
10 num /= 10;
11 }
12 return sum;
13}
14
15int main() {
16 // 读取输入
17 int n;
18 cin >> n;
19 int nums[10];
20 int sums[10];
21 for (int i = 0; i < n; ++i) {
22 cin >> nums[i];
23 sums[i] = digitSum(nums[i]);
24 }
25
26 // 使用选择排序对数字和进行排序
27 for (int i = 0; i < n - 1; ++i) {
28 int minIndex = i;
29 for (int j = i + 1; j < n; ++j) {
30 if (sums[j] < sums[minIndex]) {
31 minIndex = j;
32 }
33 }
34 // 交换 sums 和 nums
35 swap(sums[i], sums[minIndex]);
36 swap(nums[i], nums[minIndex]);
37 }
38
39 // 输出排序后的数字和
40 for (int i = 0; i < n; ++i) {
41 cout << sums[i] << (i == n - 1 ? '\n' : ' ');
42 }
43
44 return 0;
45}L2134题解+参考代码
L2134题解+参考代码 题目链接 字典排序：L2134
题解 我们需要按字典顺序对输入的 N 个整数进行排序。字典顺序的方法是先比较第一个数字，小者在先，若相同再比较第 2 位数字，以此类推。
算法步骤 读取输入：读取整数 N 和接下来的 N 个字符串形式的整数。 使用选择排序按字典顺序排序： 在每一轮中找到当前未排序部分中字典顺序最小的字符串，并将其交换到当前未排序部分的最前面。 输出结果：按字典顺序输出排序后的字符串形式的整数。 示例代码 这里是使用 C++ 实现的示例代码：
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 // 读取输入
6 int n;
7 cin >> n;
8 string nums[10];
9 for (int i = 0; i < n; ++i) {
10 cin >> nums[i];
11 }
12
13 // 使用选择排序按字典顺序排序
14 for (int i = 0; i < n - 1; ++i) {
15 int minIndex = i;
16 for (int j = i + 1; j < n; ++j) {
17 if (nums[j] < nums[minIndex]) {
18 minIndex = j;
19 }
20 }
21 // 交换字符串
22 swap(nums[i], nums[minIndex]);
23 }
24
25 // 输出结果
26 for (int i = 0; i < n; ++i) {
27 cout << nums[i] << (i == n - 1 ? '\n' : ' ');
28 }
29
30 return 0;
31}