扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
归并排序主要采取分治的思想，也可以说是递归的思想。
在学习链表的时候，我们会遇到 如何将两个有序表合并成一个有序表的问题，归并排序就是类似地利用了这一个操作。
这里以 2-路归 并为例：
提示：2-路归并是最简单也是最常见的一种归并排序方式
想要排一个序列，可以将这个序列从中间分为左右两个序列。
当左右两个序列分别被排列成一个有序序列后，再合并为一个有序序列。
而想要排列左右两个有序序列，则又可以将这两个序列依次分为两个序列，再进行排序后再合并。
注意：归并排序并不是全部分好后合并，而是一边先分好再合并，再另一边分好再合并
不断的重复操作后，可以将排序转化为如何按序合并的问题。
图示（来源于网络）：
归并排序的思想转化为操作就是递归合并了（这里是我常用的写法）:
#includeusing namespace std;
const int N = 1e6+10; //序列大长度
int temp[N]; // 归并排序需要用到一个临时存储数据的序列
int a[N]; //待排序序列
void Msort(int arr[],int left,int right){ // 归并排序
//递归边界 归并排序触碰到递归边界后，才开始真正的排序操作。
if(left>=right) return;
//折中拆分
int mid=(left+right)/2; //或写成 mid = left+right>>1
Msort(arr,left,mid); //左边
Msort(arr,mid+1,right); //右边
//有序合并
int k=left,i=left,j=mid+1; //k辅助处理数据 i相当于左指针 j相当于右指针
while(i<=mid&&j<=right){ //从小到大排序
if(arr[i] 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
微信二维码
移动版官网