二路归并排序(也叫合并排序)
排序 合并 归并
2023-09-14 09:08:01 时间
以下这图展示了二路归并的过程
二路归并的核心代码是merge()函数
它将2个切割的数组有序的合并在一起
如图:
在数组A中,
从p到q是一个数组,从q到r是另外一个数组
那么怎样将这2个数组有序的合并在一起,组个新的数组A呢?
步骤:
第一步:开辟一个数组L,存放p到q之间(也就是须要归并的左边数组)的元素
第二部:开辟一个数组R。存放q到r之间(也就是须要归并的右边数组)的元素
第三步:2个数组的最后还要加一个无穷大的数(能够用0x7FFF表示),因此开辟的数组空间要多1字符个空间
第四步:L与R中的数字逐个比較,把较小的先放在数组A中(从数组A【0】開始存放。依次往后覆盖原来的数),然后较小的数组指针往后移动,指向下一位再和另外一个数组比較
//第一个參数为须要排序的数组,第2个參数为切割的第一个数组開始元素的下标 //第3个參数为切割的第一个数组的最后1个元素的下标 //第4个參数为数组最后1个元素的下标 void Merge(int *A,int p,int q,int r) { int n1,n2,i,j,k,g; n1=q-p+1; n2=r-q; int *L,*R; L=(int *)malloc(sizeof(int)*(n1+1)); R=(int *)malloc(sizeof(int)*(n2+1)); L[n1]=0x7fff; //开辟的左右2个数组最后1个数设置为最大值 R[n2]=0x7fff; g=0; for(i=p;i<=q;i++) { L[g]=A[i]; g++; } g=0; for(i=q+1;i<=r;i++) { R[g]=A[i]; g++; } //逐个比較左右两组数组,把较小的值写入原来的数组 j=k=0; for(i=p;i<=r;i++) { if(L[j]<R[k]) { A[i]=L[j]; j++; } else { A[i]=R[k]; k++; } } }
完整代码:
#include<iostream> using namespace std; //第一个參数为须要排序的数组,第2个參数为切割的第一个数组開始元素的下标 //第3个參数为切割的第一个数组的最后1个元素的下标 //第4个參数为数组最后1个元素的下标 void Merge(int *A,int p,int q,int r) { int n1,n2,i,j,k,g; n1=q-p+1; n2=r-q; int *L,*R; L=(int *)malloc(sizeof(int)*(n1+1)); R=(int *)malloc(sizeof(int)*(n2+1)); L[n1]=0x7fff; //开辟的左右2个数组最后1个数设置为最大值 R[n2]=0x7fff; g=0; for(i=p;i<=q;i++) { L[g]=A[i]; g++; } g=0; for(i=q+1;i<=r;i++) { R[g]=A[i]; g++; } //逐个比較左右两组数组,把较小的值写入原来的数组 j=k=0; for(i=p;i<=r;i++) { if(L[j]<R[k]) { A[i]=L[j]; j++; } else { A[i]=R[k]; k++; } } } void MergeSort(int *A,int p,int r) { int q; if(p<r) //当第一个元素比最后1个元素还小时,继续运行递归,直到仅仅剩下一个元素(形參p=r) { q=(p+r)/2; MergeSort(A,p,q); MergeSort(A,q+1,r); Merge(A,p,q,r); } } void main() { int A[5]={5,3,4,23,11}; MergeSort(A,0,4); for(int i=0;i<5;i++) cout<<A[i]<<endl; system("pause"); }
相关文章
- js史上最简单的数组合并去重排序
- 多维数组进行排序
- 【轻松学排序算法】眼睛直观感受几种常用排序算法
- 关于PHP+jQuery-ui拖动浮动层排序并保存到数据库实例
- Java实现 LeetCode 23 合并K个排序链表
- Java实现合并排序
- Python学习小技巧之列表项的排序
- 【刷题】排序的稳定和不稳定
- 算法练习之合并两个有序链表, 删除排序数组中的重复项,移除元素,实现strStr(),搜索插入位置,无重复字符的最长子串
- 合并两个list集合并且排序
- (剑指Offer)面试题17:合并两个排序的链表
- 36. 合并两个排序的链表
- JavaScript对象根据自定义属性进行排序
- Python语言学习之pandas:DataFrame二维表的简介、常用函数、常用案例(增删改查排序之选择指定列、根据条件选择特定数据、赋值、列名重命名、修改列数据、处理缺失值、列合并、分组之详细攻略
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-493 合并排序数组
- 【数据结构与算法Python实践系列】5分钟学会经典排序算法-堆排序
- 剑指 Offer II 006. 排序数组中两个数字之和-哈希表法
- 合并两个排序的链表
- 习题 6.4 有一个已排好序的数组,要求输入一个数后,按原来排序的规律将它插入数组中。
- 选择排序
- Sort List[leetcode] 由归并排序的递归和循环,到本题的两种解法
- mahout demo——本质上是基于Hadoop的分步式算法实现,比如多节点的数据合并,数据排序,网路通信的效率,节点宕机重算,数据分步式存储
- 剑指 Offer 25. 合并两个排序的链表
- Mysql 单字段排序形成连续序列
- 二叉排序树的创建和插入----二叉查找树
- 容器合并排序算法-----merge