AcWing 787. 归并排序
原题链接
简单
作者:
九折_5
,
2024-06-11 11:39:38
,
所有人可见
,
阅读 1
#include<iostream>
using namespace std;
const int N=1e5+10;
// q是待排序数组,tmp是临时数组
int q[N],tmp[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);
// 合并子问题
// 核心思想是利用双指针按照不断比较把数组中的数全部挪到临时数组
// 然后再把排好序的挪回去
int k=0,i=l,j=mid+1;
// 三个while注意边界问题
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(int k=0,i=l;i<=r;i++,k++){
q[i]=tmp[k];
}
}
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;
}