归并排序主要采取分治的思想,也可以说是递归的思想。
在学习链表的时候,我们会遇到 如何将两个有序表合并成一个有序表的问题,归并排序就是类似地利用了这一个操作。
这里以 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元起,快前往官网查看详情吧
网站题目:排序算法之归并排序-创新互联
标题来源:https://www.cdcxhl.com/article2/disdoc.html
成都网站建设公司_创新互联,为您提供面包屑导航、网站改版、做网站、App开发、网站收录、移动网站建设
声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联