归并排序
作者:
WQIAN
,
2023-04-06 21:44:22
,
所有人可见
,
阅读 168
/*
*基础算法二:归并排序
*/
#include <iostream>
#include <algorithm>
using namespace std;
const int N=100010;
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);//递归,归并排序后,前半部分和后半部分分别有序
int k=0,i=l,j=mid+1;//前半部分以i开始,后半部分以mid+1开始,k时temp数组的下标
while(i<=mid&&j<=r){//两个数组开始比较,直到其中一个数组的指针移到末尾
//即i移到mid处,j移到r处时,循环停止
if(q[i]<=q[j])temp[k++]=q[i++];//将小的那个数放到temp数组里
else temp[k++]=q[j++];
}
while(i<=mid)temp[k++]=q[i++];//若是i还没有移到末尾mid处,就将前半部分剩下的数接到temp后
while(j<=r)temp[k++]=q[j++];//若是j还没有移到末尾r处,就将后半部分剩下的数接到temp后
//前半部分和后半部分经过merge_sort,分别都是有序的
for(int k=0,i=l;i<=r;i++,k++)q[i]=temp[k];//最后将temp数组里的数赋值给q数组
}
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++)cin>>q[i];//读入
merge_sort(q,0,n-1);//归并排序
for(int i=0;i<n;i++)cout<<q[i]<<' ';//输出
return 0;
}