排序算法之归并排序-创新互联

归并排序主要采取分治的思想，也可以说是递归的思想。

在学习链表的时候，我们会遇到 如何将两个有序表合并成一个有序表的问题，归并排序就是类似地利用了这一个操作。

这里以 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元起，快前往官网查看详情吧