【题目来源】
AcWing：787. 归并排序 - AcWing题库
【题目描述】
给定你一个长度为 \(n\) 的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
【输入】
输入共两行，第一行包含整数 \(n\)。
第二行包含 \(n\) 个整数（所有整数均在 \(1\sim 10^9\) 范围内），表示整个数列。
【输出】
输出共一行，包含 \(n\) 个整数，表示排好序的数列。
【输入样例】
5
3 1 2 4 5
【输出样例】
1 2 3 4 5
【解题思路】
【算法标签】
《AcWing 787 归并排序》 #归并排序#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 1000010; // 定义数组最大容量int n; // 数组元素个数
int q[N]; // 存储待排序的数组
int tmp[N]; // 归并排序使用的临时数组// 归并排序函数
void merge_sort(int q[], int l, int r) {// 递归终止条件：区间长度小于1时不需要排序if (l >= r) return;// 计算中点，分界点int mid = (l + r) >> 1; // 等价于(l + r)/2// 递归排序左右两半merge_sort(q, l, mid); // 排序左半部分merge_sort(q, mid + 1, r); // 排序右半部分// 合并两个有序数组int k = 0; // 临时数组的指针int i = l; // 左半部分的指针int j = mid + 1; // 右半部分的指针// 比较左右两部分的元素，按顺序放入临时数组while (i <= mid && j <= r) {if (q[i] <= q[j]) tmp[k++] = q[i++]; // 左边元素较小else tmp[k++] = q[j++]; // 右边元素较小}// 处理剩余元素（左半部分或右半部分可能还有剩余）while (i <= mid) tmp[k++] = q[i++]; // 左半部分剩余元素while (j <= r) tmp[k++] = q[j++]; // 右半部分剩余元素// 将临时数组中的有序元素复制回原数组for (i = l, j = 0; i <= r; i++, j++) {q[i] = tmp[j];}
}int main() {// 输入数据scanf("%d", &n); // 读取元素个数for (int i = 0; i < n; i++) scanf("%d", &q[i]); // 读取数组元素// 调用归并排序merge_sort(q, 0, n - 1);// 输出排序结果for (int i = 0; i < n; i++) printf("%d ", q[i]);return 0;
}
【运行结果】
5
3 1 2 4 5
1 2 3 4 5