C++ 归并排序(merge sort)案例详解
作者:Joe_Somebody 时间:2022-03-23 00:00:00
核心思想:“分”与“合”。
主体流程
先将一个序列分成很多个不能再分割的子序列,将各个子序列分别排序后再将子序列合并。其实就是重复两个步骤:【1】分【2】合并。
首先是第一个小问题,怎么分?
比如说一个序列:12 ,23,1,44,233,10,9,8。我们先分成两段:12 ,23,1,44 和 233,10,9,8,
发现还能再分成4段:12 ,23 和 1,44------233,10 和 9,8。
再分成8段:12--23--1--44 和233--10--9--8。
这时候开始把子序列进行排序合并,一个元素就是有序的。所以不用排序。
合并成2个一组排序得到:12,23----1,44---10,233---8,9。
再合并成4个一组排序得到:1,12,23,44---8,9,10,233。
最后合并得到最终结果:1,8,9,10,12,23,44,233。
下面是分段的代码,用递归实现。
void mergesort(int a[], int first, int last, int temp[])
{
if (first < last)
{
int mid = (first + last) / 2;
mergesort(a, first, mid, temp); //左边有序
mergesort(a, mid + 1, last, temp); //右边有序
mergearray(a, first, mid, last, temp); //再将二个有序数列合并
}
}
整体思路很清晰,还差一个小问题没解决,怎么合并?
现在问题就变成了怎么合并两个有序序列,思路是比较两个有序序列的第一个元素,谁小把谁放进最终序列的结尾,并把它从原来的队列里面删掉直到有个序列为空。
这时候另一个序列可能还有剩余的数据。没关系,因为他们本身是有序的,所以我们只要按顺序把他们添加到最终序列的尾部就好了。
这样两个有序序列就合并成一个有序序列了。
实现代码:
void mergearray(int a[], int first, int mid, int last, int temp[])
{
int i = first, j = mid + 1;
int m = mid, n = last;
int k = 0;
while (i <= m && j <= n)
{
if (a[i] <= a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
while (i <= m)
temp[k++] = a[i++];
while (j <= n)
temp[k++] = a[j++];
}
整体测试代码:
#include<iostream>
#include<math.h>
#include<stdlib.h>
using namespace std;
//将有二个有序数列a[first...mid]和a[mid...last]合并。
void mergearray(int a[], int first, int mid, int last, int temp[])
{
int i = first, j = mid + 1;
int m = mid, n = last;
int k = 0;
while (i <= m && j <= n)
{
if (a[i] <= a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
while (i <= m)
temp[k++] = a[i++];
while (j <= n)
temp[k++] = a[j++];
for (i = 0; i < k; i++)
a[first + i] = temp[i];
}
void mergesort(int a[], int first, int last, int temp[])
{
if (first < last)
{
int mid = (first + last) / 2;
mergesort(a, first, mid, temp); //左边有序
mergesort(a, mid + 1, last, temp); //右边有序
mergearray(a, first, mid, last, temp); //再将二个有序数列合并
}
}
bool MergeSort(int a[], int n)
{
int *p = new int[n];
if (p == NULL)
return false;
mergesort(a, 0, n - 1, p);
delete[] p; //删除p临时数组
return true;
}
int main()
{
int i=0,temp=0;
int a[10]={0};
for(i=0;i<10;i++)
{
a[i]=rand();
cout<<a[i]<<" ";
}
cout<<endl;
MergeSort(a,10);
for(i=0;i<10;i++)
{
cout<<a[i]<<" ";
}
return 0;
}
来源:https://www.jianshu.com/p/b50a6034eb90
标签:C++,归并排序
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
java底层JDK Logging日志模块处理细节深入分析
2023-02-04 12:47:31
Android RecycleView和线型布局制作聊天布局
2022-08-01 15:36:56
![](https://img.aspxhome.com/file/2023/2/108302_0s.jpg)
Android实现简洁的APP更新dialog数字进度条
2023-01-29 18:53:39
![](https://img.aspxhome.com/file/2023/8/93318_0s.gif)
MyBatis-plus中的模糊查询解读
2022-06-16 08:27:03
![](https://img.aspxhome.com/file/2023/5/61665_0s.png)
SpringBoot配置自定义拦截器实现过程详解
2022-11-04 17:24:48
Android实现手机游戏隐藏虚拟按键
2023-01-29 02:04:55
Java查看和修改线程优先级操作详解
2023-09-13 08:25:30
![](https://img.aspxhome.com/file/2023/1/80271_0s.png)
C# 键盘Enter键取代Tab键实现代码
2022-11-21 08:53:14
![](https://img.aspxhome.com/file/2023/7/68107_0s.png)
MyBatis使用雪花ID的实现
2023-06-09 16:26:23
java判断今天,昨天,前天,不能用秒间隔的简单实例
2021-07-27 23:01:35
Logger.getLogger()与LogFactory.getLog()的区别详解
2021-11-04 19:16:00
将Java的List结构通过GSON库转换为JSON的方法示例
2023-02-13 20:33:52
c# winform多线程的小例子
2023-01-05 07:11:44
![](https://img.aspxhome.com/file/2023/5/108685_0s.png)
String类型传递是值传递,char[]类型传递是引用传递的实现
2022-06-01 09:33:44
sweet alert dialog 在android studio应用问题说明详解
2022-12-14 04:17:53
![](https://img.aspxhome.com/file/2023/2/93312_0s.jpg)
最常用的1000个Java类(附代码示例)
2023-03-25 20:29:07
Java常见数据结构面试题(带答案)
2023-11-24 19:44:05
解决Mybatis映射文件mapper.xml中的注释问题
2023-09-17 15:06:30
c# 生成二维码的示例
2021-09-17 14:03:26
![](https://img.aspxhome.com/file/2023/2/79082_0s.png)
Spring Validation方法实现原理分析
2023-09-04 17:11:55
![](https://img.aspxhome.com/file/2023/7/81257_0s.jpg)