C++ 归并排序(merge sort)案例详解
作者:Joe_Somebody 发布时间:2022-03-23 00:00:00
标签:C++,归并排序
核心思想:“分”与“合”。
主体流程
先将一个序列分成很多个不能再分割的子序列,将各个子序列分别排序后再将子序列合并。其实就是重复两个步骤:【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
0
投稿
猜你喜欢
- 先说明一下,项目代码已上传至github,不想看长篇大论的也可以先去下代码,对照代码,哪里不懂点哪里。代码在这https://github.
- 本文实例讲述了Android编程实现小说阅读器滑动效果的方法。分享给大家供大家参考,具体如下:看过小说都知道小说阅读器翻页有好多种效果,比如
- paras.xml文件<?xml version="1.0" encoding="UTF-8"
- 迭代器模式,一直没用过,也不会用。恰巧MyBatis框架中也使用到了迭代器模式,而且看起来还比较简单,在以后的工作中,若有需要咱们可模仿它的
- Android WebView的使用方法 Android app打开H5页一般要实现如下需求:1、打开指定url网页
- 简介:本文已一个简要的代码示例介绍ThreadLocal类的基本使用方式,在此基础上结合图片阐述它的内部工作原理。早在JDK1.2的版本中就
- 本文介绍了Android:利用SharedPreferences实现自动登录,具体如下:主要代码:public class LoginAct
- 最近项目需要通过经纬度查询 具体的地址和区域名称,通过查询网络资源,发现提供的大多是得到具体的地址而对区域或城市名称的获取就不是很好把握;在
- 概述现实生活中,我们常会看到这样的一种集合:IP地址与主机名,身份证号与个人,系统用户名与系统用户对象等,这种一一对应的关系,就叫做映射。J
- 本文实例讲述了C#不重复输出一个数组中所有元素的方法。分享给大家供大家参考。具体如下:1.算法描述0)输入合法性校验1)建立临时数组:与原数
- if语句一个if语句包含一个布尔表达式和一条或多条语句。语法If语句的用语法如下:if(布尔表达式){ //如果布尔
- 什么是零拷贝?零拷贝(英语: Zero-copy)技术是指计算机执行操作时,CPU不需要先将数据从某处内存复制到另一个特定区域。这种技术通常
- Web.Config,其中一部分配置如下: <appSettings> <
- static表示“全局”或者“静态”的意思,用来修饰成员变量和成员方法,也可以形成静态static代码块,但是Java语言中没有全局变量的概
- 现在很多电脑提供了蓝牙支持,很多笔记本网卡也集成了蓝牙功能,也可以采用USB蓝牙方便的连接手机等蓝牙设备进行通信。操作蓝牙要使用类库InTh
- 图片的复制无非有两种方法,一种是图片直接上传到服务器,另外一种转换成二进制流的base64码目前限chrome浏览器使用首先以um-edit
- 自定义log4j日志文件命名规则项目中的日志需要采用一致的命名规范和文件规范,命名规则为:项目模块标识_index_日期时间_日志级别.lo
- SpringMVC @RequestBody的使用Spring mvc是一个非常轻量的mvc框架,注解可以大大减少配置,让请求的拦截变得比较
- 一、前言:垃圾回收:在未来的JDK中可能G1会为ZGC所取代先问自己几个问题:什么是垃圾?垃圾就是堆内存中(范指)没有任何指针指向的对象实体
- 1、fragment简介我对fragment的理解是基于activity的,对于大多数的基本开始发时,我们最先遇到的就是用activity来