测试数据:
归并排序-知识总结 解决问题 对一组线性存储的数据进行排序。
核心思想 归并排序的核心思想是将一个大数组分解成两个小数组去解决。然后递归地排序这两个小数组,最后将排序好的小数组合并成一个大数组。归并排序的效率来自于它合并两个已排序数组的能力。
工作原理 原理介绍 分解:从中间将待排序的数组分割成两部分,直到每个子数组只包含一个元素(递归基)。 解决:递归地对这两个子数组进行归并排序,直到每个子部分被排序。 合并:将两个排序好的子数组合并成一个最终的排序数组。合并过程需要额外的空间来临时存储这两个数组,然后按顺序选取两个数组中的元素填充到原数组中。
示例 考虑数组 [3,1,4,1,5,9,2,6][3, 1, 4, 1, 5, 9, 2, 6][3,1,4,1,5,9,2,6] 的排序过程: 分解: [3,1,4,1][3, 1, 4, 1][3,1,4,1] 和 [5,9,2,6][5, 9, 2, 6][5,9,2,6] 进一步分解为 [3,1][3, 1][3,1] 和 [4,1][4, 1][4,1],以及 [5,9][5, 9][5,9] 和 [2,6][2, 6][2,6] 最后分解到单个元素 解决: 单个元素自然有序 合并: 合并 [3][3][3] 和 [1][1][1] 得到 [1,3][1, 3][1,3] 合并 [4][4][4] 和 [1][1][1] 得到 [1,4][1, 4][1,4] 合并 [1,3][1, 3][1,3] 和 [1,4][1, 4][1,4] 得到 [1,1,3,4][1, 1, 3, 4][1,1,3,4] 类似地,[5,9][5, 9][5,9] 和 [2,6][2, 6][2,6] 合并为 [2,5,6,9][2, 5, 6, 9][2,5,6,9] 最后,合并 [1,1,3,4][1, 1, 3, 4][1,1,3,4] 和 [2,5,6,9][2, 5, 6, 9][2,5,6,9] 得到 [1,1,2,3,4,5,6,9][1, 1, 2, 3, 4, 5, 6, 9][1,1,2,3,4,5,6,9]
代码模板
1#include<iostream>
2#include<algorithm>
3#include<vector>
4#include "stdio.h"
5#include "time.h"
6using namespace std;
7
8int a[10000005] = {0};
9
10// 合并两个有序数组段的函数
11void merge(int a[], int left, int mid, int right) {
12 int t[105] = {0}; // 创建一个临时数组用于存储合并后的有序序列
13 int lp = left; // lp是左半部分的起始索引
14 int rp = mid + 1; // rp是右半部分的起始索引
15 int si = left; // si是用于追踪当前要插入元素到临时数组t的索引
16
17 // 遍历左右两部分,直到一个达到终点
18 while (si <= right) {
19 // 如果左半部分已完全处理完毕,或者右半部分当前元素小于左半部分当前元素
20 if (lp > mid || (rp <= right && a[lp] > a[rp])) {
21 t[si] = a[rp]; // 将右半部分当前元素拷贝到临时数组
22 rp++; // 移动右半部分的索引
23 }
24 else {
25 t[si] = a[lp]; // 否则,将左半部分当前元素拷贝到临时数组
26 lp++; // 移动左半部分的索引
27 }
28 si++; // 移动临时数组的索引
29 }
30
31 // 将临时数组中排序后的元素拷贝回原数组a
32 for (int i = left; i <= right; i++) {
33 a[i] = t[i];
34 }
35}
36
37// 归并排序的递归实现
38void merge_sort(int a[], int left, int right) {
39 if (right <= left) {
40 return; // 如果当前数组段的长度为1或0,直接返回
41 }
42 int mid = (left + right) / 2; // 找到中点,将数组分成两半
43 merge_sort(a, left, mid); // 递归排序左半部分
44 merge_sort(a, mid + 1, right); // 递归排序右半部分
45 merge(a, left, mid, right); // 合并两个有序的半部分
46}
47
48int main() {
49 int n = 0;
50 cin >> n;
51 for (int i = 0; i < n; i++) {
52 cin >> a[i];
53 }
54 merge_sort(a, 0, n - 1);
55 for (int i = 0; i < n; i++) {
56 cout << a[i] << ' ';
57 }
58 cout << endl;
59 return 0;
60}算法评价 时间复杂度:O(nlogn) 归并排序需要进行大约logn次的分解步骤,每次合并操作最多需要O(n)时间。 空间复杂度:O(n) 稳定性:稳定排序
总结作业非常重要,请务必认真完成✔️
考试只有一次提交机会,请务必本地检查正确后再提交❇️
