AcWing 787. 归并排序
原题链接
简单
作者:
Azxcc0
,
2021-12-21 18:25:09
,
所有人可见
,
阅读 204
归并排序
归并排序
参考文献
y总
C++ 代码
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int q[N], temp[N];
void merge_sort(int q[], int l, int r)
{
if(l >= r) return;
int mid = l + r >> 1;
//先递归
merge_sort(q, l, mid), merge_sort(q, mid+1, r);
//C++除法是向下取整, 故+ 1
int k = 0, i = l, j = mid + 1;
//穷尽一个指针
while(i <= mid && j <= r)
if (q[i] < q[j]) temp[k ++ ] = q[i ++ ];
else temp[k ++ ] = q[j ++ ];
//while结束的时候,一个指针已穷尽
//接下来穷尽另一个指针
while (i <= mid) temp[k++ ] = q[i++ ];
while (j <= r) temp[k ++ ] = q[j ++ ];
//复制回去
for (int i = l, j = 0; i <= r; i++, j ++ ) q[i] = temp[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;
}