插入排序-知识总结 解决问题 对一组线性存储的数据进行排序。
核心思想 插入排序通过插入的方法构建有序序列从而实现排序。是使用了贪心法的排序算法。
工作原理 原理介绍 初始化：标记已排序部分为1个元素 ①找到未排序部分的第一个元素X ②从后向前找到第一个大于等于它的元素Y ③检查Y是否存在： A.若存在则将X插入到Y之后 B.否则将X插入到所有元素前 重复①②③至所有元素都已排序
代码模板
1// 从小到大排序
2#include <bits/stdc++.h>
3using namespace std;
4
5int arr[1005];
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 = 1; i < n; ++i) {
14 int key = arr[i];
15 int j = i - 1;
16 while (j >= 0 && key < arr[j]) {
17 arr[j + 1] = arr[j];
18 --j;
19 }
20 arr[j + 1] = key;
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[1005];
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 = 1; i < n; ++i) {
40 int key = arr[i];
41 int j = i - 1;
42 while (j >= 0 && key > arr[j]) {
43 arr[j + 1] = arr[j];
44 --j;
45 }
46 arr[j + 1] = key;
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) 稳定性：稳定排序
总结作业非常重要，请务必认真完成✔️
考试只有一次提交机会，请务必本地检查正确后再提交❇️
请在AC后或者思考15分钟没有进展后查看，不可抄代码❇️
L2163题解+参考代码 题目链接 找到数列元素唯一并排序：L2163
题解 我们需要对输入的 n 个无序整数进行去重并排序。可以使用插入排序的思想来实现去重和排序。
算法步骤 读取输入：读取整数 n 和接下来的 n 个整数。 去重和排序： 遍历每个数，并将其插入到有序部分中，同时检查是否重复。 使用插入排序的方法将新元素插入到正确的位置。 输出结果：按从小到大的顺序输出排序后的数组 示例代码 这里是使用 C++ 实现的示例代码：
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 // 读取输入
6 int n;
7 cin >> n;
8 int nums[1000], sorted[1000], sortedCount = 0;
9
10 for (int i = 0; i < n; ++i) {
11 cin >> nums[i];
12 }
13
14 // 使用插入排序思想进行去重和排序
15 for (int i = 0; i < n; ++i) {
16 int key = nums[i];
17 bool isDuplicate = false;
18
19 // 检查是否重复
20 for (int j = 0; j < sortedCount; ++j) {
21 if (sorted[j] == key) {
22 isDuplicate = true;
23 break;
24 }
25 }
26
27 // 如果不是重复的数，插入排序
28 if (!isDuplicate) {
29 int j = sortedCount - 1;
30 while (j >= 0 && sorted[j] > key) {
31 sorted[j + 1] = sorted[j];
32 j--;
33 }
34 sorted[j + 1] = key;
35 sortedCount++;
36 }
37 }
38
39 // 输出结果
40 for (int i = 0; i < sortedCount; ++i) {
41 if (i > 0) cout << " ";
42 cout << sorted[i];
43 }
44 cout << endl;
45
46 return 0;
47}L2164题解+参考代码 题目链接 学生组队：L2164
题解 我们需要找出使所有学生能力值相同的最少题数。首先，我们可以将能力值排序。然后，计算每一对学生能力值之间的差值，这个差值就是需要提升的题数。最终，我们将所有的差值相加得到最少需要做的题数。
算法步骤 读取输入：读取整数 n 和每个学生的能力值。 排序：对能力值进行升序排序。 计算最少需要做的题数： 遍历排序后的能力值列表，计算每两个相邻学生的能力值差值。 将所有差值相加，得到最少需要做的题数。 输出结果：输出最少需要做的题数。 示例代码 这里是使用 C++ 实现的示例代码：
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 // 读取输入
6 int n;
7 cin >> n;
8 int ability[100];
9
10 for (int i = 0; i < n; ++i) {
11 cin >> ability[i];
12 }
13
14 // 使用插入排序对能力值进行排序
15 for (int i = 1; i < n; ++i) {
16 int key = ability[i];
17 int j = i - 1;
18 while (j >= 0 && ability[j] > key) {
19 ability[j + 1] = ability[j];
20 j--;
21 }
22 ability[j + 1] = key;
23 }
24
25 // 计算最少需要做的题数
26 int totalProblems = 0;
27 for (int i = 0; i < n; i += 2) {
28 totalProblems += ability[i + 1] - ability[i];
29 }
30
31 // 输出结果
32 cout << totalProblems << endl;
33
34 return 0;
35}