AcWing 787. 归并排序
原题链接
简单
作者:
doubleq
,
2021-05-17 17:29:37
,
所有人可见
,
阅读 214
归并排序
输入样例
5
3 1 2 4 5
输出样例
1 2 3 4 5
时间复杂度 :$O(nlogn)$
C++ 代码
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100010;
int a[N],temp[N];
int n;
void merge_sort(int l,int r)
{
if(l >= r) return;//递归的截止条件
int mid = l + r >> 1;//每次将下标一分为二,然后进行递归,直到l >= r时退出
merge_sort(l,mid);
merge_sort(mid + 1,r);
//将上面两个sort过的部分按照由小到大进行合并
int k = 0, i = l,j = mid + 1;
while(i <= mid && j <= r)
{
if(a[i] <= a[j]) temp[k ++] = a[i ++];
else temp[k ++] = a[j ++];
}
//一个数组的数值比另一个部分的数组的某个数小,导致另一个数组剩下一部分没有赋值,剩下的数全部比之前的大,所以直接接在后面
while(i <= mid) temp[k ++] = a[i ++];
while(j <= r) temp[k ++] = a[j ++];
for(int i = l,j = 0;j < k;i ++,j ++) a[i] = temp[j];//将已经排好序的temp数组赋值给原数组
}
int main()
{
scanf("%d",&n);
for(int i = 0;i < n;i ++) scanf("%d",&a[i]);
merge_sort(0,n - 1);
for(int i = 0;i < n;i ++) printf("%d ",a[i]);
return 0;
}