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

思想

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

我们提供的服务有：网站设计、网站制作、微信公众号开发、网站优化、网站认证、建邺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元起，快前往官网查看详情吧

网站题目：排序算法之归并排序-创新互联
标题来源：https://www.cdcxhl.com/article2/disdoc.html

成都网站建设公司_创新互联，为您提供面包屑导航、网站改版、做网站、App开发、网站收录、移动网站建设

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

成都定制网站网页设计

软件开发知识

分类信息网站