AcWing 787. 归并排序
原题链接
简单
作者:
lemon_242
,
2024-02-23 09:39:01
,
所有人可见
,
阅读 28
y总原样模板+注释理解
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], tmp[N]; //a[N]用于存储输入进来的数据,tmp[N]用于存储两个数组合并后的结果
void merge_sort(int q[], int l, int r) //传入待排序的数组,左边界下标,右边界下标
{
if (l >= r) return; //如果左边界>=右边界,说明只有1个数,或者没有数字,那么排序完成
int mid = l + r >> 1; //归并的中间值是:左右下标之和除2下取整,写成l + r >> 1
//快排的保险写法 也是mid = l + r >> 1【二者统一】
merge_sort(q, l, mid), merge_sort(q, mid + 1, r); //分别把左边数组和右边数组递归排序好
//左右两边的数组排序完成后,需要合并两个数组
//设置指针i,j,分别指向两个数组的开头位置:i = l,j = mid + 1
int k = 0, i = l, j = mid + 1;
//当两个指针都没有扫描到尾部时,不断地把小的数放在tmp数组里
while (i <= mid && j <= r)
if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ]; //注意,tmp[k ++ ] = q[i ++ ]这里的写法是:先赋值后自增
else tmp[k ++ ] = q[j ++ ];
//如果有指针扫描到尾部,则开始判断是哪边的数组还有剩余数字,直接把所有数字加在tmp数组末尾
//2个while,把两边都判断一下
while (i <= mid) tmp[k ++ ] = q[i ++ ]; //先赋值后自增
while (j <= r) tmp[k ++ ] = q[j ++ ];
//最后一步:把tmp存储的排好序的数字放到传入的q数组中,等待输出
for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
merge_sort(a, 0, n - 1); //传入待排序的数组a,左右下标对应序号分别是0,n-1
for (int i = 0; i < n; i ++ ) printf("%d ", a[i]);
return 0;
}