AcWing 787. 归并排序
原题链接
简单
作者:
米多奇香米饼
,
2023-01-25 10:35:15
,
所有人可见
,
阅读 63
# include<iostream>
using namespace std;
const int N = 1e5 + 5;
int q[N], t[N];
void merge_Sort(int p[],int l,int r){
if(l >= r)return;
int mid = (l+r)>>1;
merge_Sort(p,l,mid);
merge_Sort(p,mid+1,r);
//count记录在数组t中元素的个数
int count = 0,i = l,j = mid+1;
while(i <= mid && j <= r){
//如果第一段的元素小于第二段的元素,那么将第一段的元素赋值到临时数组t中,并将count++,i++
if(q[i]<=q[j])t[count++] = q[i++];
//如果第二段的元素小于第一段的元素,那么将第二段的元素赋值到临时数组t中,并将count++,j++
else t[count++] = q[j++];
}
while(i <= mid)t[count++] = q[i++];
while(j <= r)t[count++] = q[j++];
//将临时数组t中的元素依次赋值到原数组q中
for ( int i = l, j = 0; i <= r; i++, j++ ) q[i] = t[j];
}
int main(){
int n;
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;
}