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

思想

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

我们提供的服务有:网站设计、网站制作、微信公众号开发、网站优化、网站认证、建邺ssl等。为千余家企事业单位解决了网站和推广的问题。提供周到的售前咨询和贴心的售后服务,是有科学管理、有技术的建邺网站制作公司

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

这里以 2-路归 并为例:

提示:2-路归并是最简单也是最常见的一种归并排序方式

想要排一个序列,可以将这个序列从中间分为左右两个序列。

当左右两个序列分别被排列成一个有序序列后,再合并为一个有序序列。

而想要排列左右两个有序序列,则又可以将这两个序列依次分为两个序列,再进行排序后再合并。

注意:归并排序并不是全部分好后合并,而是一边先分好再合并,再另一边分好再合并

不断的重复操作后,可以将排序转化为如何按序合并的问题。

图示(来源于网络):

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA6ZqP6aOO54Gs6L-c5Y675Li2,size_20,color_FFFFFF,t_70,g_se,x_16

操作

归并排序的思想转化为操作就是递归合并了(这里是我常用的写法):

#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元起,快前往官网查看详情吧


分享名称:排序算法之归并排序-创新互联
网页地址:http://scyanting.com/article/disdoc.html