c++ 归并排序（分治）

简介

归并排序，往往用于解决数据量比较大的情况。通过将一个大的模块拆分为多个小的区域（最终为每个区域元素个数为1）进行排序后再次合并组合在一起的方式，叫做归并排序。

步骤分析

代码思路

代码实现 

#include<bits/stdc++.h>
using namespace std;
//归并排序 
long long a[500001],b[500001];//a数组为存数据数组 b数组为临时数组 
//分治合并 
void merge(long long l,long long r){long long mid=(l+r)/2,t=0,frist=l,second=mid+1;while(frist<=mid&&second<=r){//如果左侧区域第一个指针小于中间指针 并且 右侧区域第一和指针小于最右侧 （表示左右侧仍存在数据未放到a数组中） if(a[frist]<=a[second]){//分别取左右区域的最小值进行比较 谁小放到临时数组b中 进行排序 b[t++]=a[frist++];//每排一次，t frist 都往后移 }else{b[t++]=a[second++];}}//如果一侧排完毕后，对另一侧未排完的数据直接放入数组b中 while(frist<=mid){b[t++]=a[frist++];}while(second<=r){b[t++]=a[second++];} //两个子区域的值都放入b数组后，在更新区间，将值放入a数组中for(int i=0;i<r-l+1;i++){a[l+i]=b[i];}} 
//分治拆分 
void mergeSort(long long l,long long r){long long mid=(l+r)/2;if(l<mid)mergeSort(l,mid);//左侧区域进行再次分治拆分 if(r>mid+1)mergeSort(mid+1,r);//右侧区域进行再次分治拆分 merge(l,r);
}int main(){long long n;scanf("%lld",&n);for(int i=0;i<n;i++){scanf("%lld",&a[i]);}mergeSort(0,n-1); for(int i=0;i<n;i++){printf("%lld ",a[i]);}return 0;
}