[题目概述]
给定你一个长度为 n 的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整个数列。
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。
数据范围
1 ≤ n ≤ 100000 1 ≤ n ≤ 100000 1≤n≤100000
输入样例：
5
3 1 2 4 5
输出样例：
1 2 3 4 5
- 分析题目
本题为模板题，就是让我们手写一个归并排序。我们可以先理解一下归并，就是把它们聚到一堆合并起来。他的思想就是先将其分成两个部分各自拍好序，然后再将他们按顺序合并。 - 完整代码（逐行解析）
在排序时用到双指针算法，简单解释一下- 用两个数分别指向两个部分的左端点，哪个数小，哪个指针就向后移动一个位置，知道无法移动
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 100010;
int n, q[N], temp[N]; // 数据数组和中间数组
// 三个参数分别是要排序的数组，左端点，右端点
void merge_sort(int q[], int l, int r) {
// 如果数组中没有数或者只有一个数则不用排序
if (l >= r)
return;
// 将其分成左右两个部分，这里的mid是取整个数组的中间（和快速排序不同）
int mid = (l + r) / 2;
// 分别排序左右两边
merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
// 双指针算法，分别指向两个部分的左端点
int i = l, j = mid + 1, k = 0;
// 两个指针都未到达右边
while (i <= mid && j <= r) {
if (q[i] <= q[j])
temp[k ++] = q[i ++];
if (q[i] > q[j])
temp[k ++] = q[j ++];
}
// 两个指针有一个到右边后，就将另外部分剩余的数据接到中间数组中
while (i <= mid) {
temp[k ++] = q[i ++];
}
while (j <= r) {
temp[k ++] = q[j ++];
}
// 将中间数组的数据copy到原数组
// 这里因为原数组是l ~ r,而中间数组是从0开始，所以i 为 l ~ r，j从0开始
for (int i = l, j = 0; i <= r; i ++, j ++) {
q[i] = temp[j];
}
}
int main () {
cin >> n;
for (int i = 0; i < n; i ++)
cin >> q[i];
merge_sort(q, 0, n - 1);
for (int i = 0; i < n; i ++)
printf("%d ", q[i]);
return 0;
}
- 本题就分享完毕了，此题还是主要在于思想，模板要理解背会
有问题的小伙伴可以发在评论区，别忘了点赞关注加收藏！
