C++ 归并排序(merge sort)案例详解
核心思想：“分”与“合”。
主体流程
先将一个序列分成很多个不能再分割的子序列，将各个子序列分别排序后再将子序列合并。其实就是重复两个步骤：【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;
}
到此这篇关于C++ 归并排序(merge sort)案例详解的文章就介绍到这了,更多相关C++ 归并排序(merge sort)内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！
相关推荐
-
C++/GoLang如何实现自底向上的归并排序
前言 上一篇文章写了一个自顶向下的归并排序,把一个完整的数组不断二分,然后再合并.其实换一种思路:把数组中相邻的N个元素看成是已经二分好了的,直接进行合并,就省掉了二分那一步骤 自底向上的归并排序示意图 C++实现: template<typename T> void mergeSortButton2Top(T arr[], int n) { for (int size = 1; size <= n; size += size) { for (int i = 0; i+size <
-
c++归并排序详解
说一说归并排序 归并排序:归并排序(英语:Merge sort,或mergesort),是创建在归并操作上的一种有效的排序算法,效率为O(n log n).1945年由约翰·冯·诺伊曼首次提出.该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行. 归并排序的核心思想是将两个有序的数列合并成一个大的有序的序列.通过递归,层层合并,即为归并. 如图,从下到上,每一步都需要将两个已经有序的子数组合并成一个大的有序数组,如下是实现合并的具体代码,请
-
C++实现归并排序算法
归并 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列:即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为二路归并. 算法描述 归并操作的工作原理如下: 1.申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列 2.设定两个指针,最初位置分别为两个已经排序序列的起始位置 3.比较两个指针所指向的元素,选择相对小
-
C++实现自顶向下的归并排序算法
本文实例讲述了C++实现自顶向下的归并排序算法.分享给大家供大家参考,具体如下: 一. 算法描述 自顶向下的归并排序:采用分治法进行自顶向下的程序设计方式,分治法的核心思想就是分解.求解.合并. 1. 先将长度为N的无序序列分割平均分割为两段 2. 然后分别对前半段进行归并排序.后半段进行归并排序 3. 最后再将排序好的前半段和后半段归并 过程(2)中进行递归求解,最终下图详细的分解了自顶向下的合并算法的实现过程: 二. 算法实现 /*==============================
-
C++实现归并排序（MergeSort）
本文实例为大家分享了C++实现归并排序的具体代码,供大家参考,具体内容如下 一.思路:稳定排序 (1)划分:一直调用划分过程,直到子序列为空或只有一个元素为止,共需log2(n): (2)归并:将两个子序列从小到大合并为一个序列 二.实现程序: // 归并排序:(二路归并) // (1)递归分解数组: // (2)合并有序的序列 #include <iostream> using namespace std; // 合并两个有序的序列 template <typename T> v
-
C++实现的归并排序算法详解
本文实例讲述了C++实现的归并排序算法.分享给大家供大家参考,具体如下: 归并排序 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法. 该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列: 即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为二路归并. 归并过程 1.比较a[i]和a[j]的大小,若a[i]≤a[j],则将第一个有序表中的元素a[i]复制到temp[k]中,并令i
-
c++实现二路归并排序的示例代码
二路归并排序 基本思想 二路归并排序就是将两个有序子表归并成一个有序表.首先我们得有一个算法用于归并:两个有序表放在同一数组的相邻位置上,arr[left]到arr[center-1]为第一个有序表,arr[center]到arr[right]是第二个有序表.每次从两端中取出一个进行比较,小的先放在一个temp数组,最后将比较剩下的直接放到temp中去,最后将temp又复制回arr.这是"治". 所谓"分",就是递归地将前半部分和后半部分的数据各自归并排序即可. 算
-
C++实现归并排序
定义:归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列:即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为二路归并. 简单的来说,归并排序主要分为三步,一是对数组的划分,二是对数组的排序,三是对数组的合并.划分的大小是可以随自己的想法而设置,但是一般都是以2为单位,这样最小的一组的排序就比较方便. 具体一个简单的例子: 设有数
-
C++ 归并排序(merge sort)案例详解
核心思想:"分"与"合". 主体流程 先将一个序列分成很多个不能再分割的子序列,将各个子序列分别排序后再将子序列合并.其实就是重复两个步骤:[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
-
PHP排序算法之归并排序(Merging Sort)实例详解
本文实例讲述了PHP排序算法之归并排序(Merging Sort).分享给大家供大家参考,具体如下: 基本思想: 归并排序:就是利用归并(合并)的思想实现的排序方法.它的原理是假设初始序列含有 n 个元素,则可以看成是 n 个有序的子序列,每个子序列的长度为 1,然后两两归并,得到 ⌈ n / 2⌉ (⌈ x ⌉ 表示不小于 x 的最小整数)个长度为 2 或 1 的有序序列:再两两归并,······,如此重复,直至得到一个长度为 n 的有序序列为止,这种排序方法就成为 2 路归并排序. 一.归并
-
PHP排序算法之基数排序(Radix Sort)实例详解
本文实例讲述了PHP排序算法之基数排序(Radix Sort).分享给大家供大家参考,具体如下: 基数排序在<大话数据结构>中并未讲到,但是为了凑齐八大排序算法,我自己通过网络学习了这个排序算法,并给大家分享出来. 基本思想: 基数排序(radix sort)属于"分配式排序"(distribution sort),又称"桶子法"(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些"桶&quo
-
Python heapq库案例详解
Python heapq heapq 库是 Python 标准库之一,提供了构建小顶堆的方法和一些对小顶堆的基本操作方法(如入堆,出堆等),可以用于实现堆排序算法. 堆是一种基本的数据结构,堆的结构是一棵完全二叉树,并且满足堆积的性质:每个节点(叶节点除外)的值都大于等于(或都小于等于)它的子节点. 堆结构分为大顶堆和小顶堆,在 heapq 中使用的是小顶堆: 大顶堆:每个节点(叶节点除外)的值都大于等于其子节点的值,根节点的值是所有节点中最大的. 小顶堆:每个节点(叶节点除外)的值都小于等于其
-
java中的arrays.sort()代码详解
Arrays.sort(T[], Comparator < ? super T > c) 方法用于对象数组按用户自定义规则排序. 官方Java文档只是简要描述此方法的作用,并未进行详细的介绍,本文将深入解析此方法. 1. 简单示例 sort方法的使用非常的简单明了,下面的例子中,先定义一个比较Dog大小的Comparator,然后将其实例对象作为参数传给sort方法,通过此示例,你应该能够快速掌握Arrays.sort()的使用方法. import java.util.Arrays; impo
-
Java jpa外连接查询join案例详解
1.IndexTagController.java @GetMapping("/tags/{id}") public String types(@PageableDefault(size = 3,sort = {"updateTime"},direction = Sort.Direction.DESC)Pageable pageable, @PathVariable long id, Model model, HttpSession session){ //找到所有
-
Python实现堆排序案例详解
Python实现堆排序 一.堆排序简介 堆排序(Heap Sort)是利用堆这种数据结构所设计的一种排序算法. 堆的结构是一棵完全二叉树的结构,并且满足堆积的性质:每个节点(叶节点除外)的值都大于等于(或都小于等于)它的子节点. 关于二叉树和完全二叉树的介绍可以参考:https://blog.csdn.net/weixin_43790276/article/details/104737870 堆排序先按从上到下.从左到右的顺序将待排序列表中的元素构造成一棵完全二叉树,然后对完全二叉树进行调整,使
-
Java之Algorithm_analysis案例详解
/* 冒泡排序:双层循环 1.外层循环:控制排序轮数,排序数组长度减1(最后一次循环只剩下一个元素,不需要比较,同时数组已完成排序. 2.内层循环:比较数组临近元素大小,确定是否交换位置,对比和交换次数随排序轮数而减少. */ public class BubbleSort { public void sort(int[] array){ for(int i=1;i<array.length;i++){//控制轮数 //比较相邻两个元素,较大的数往后冒泡 for(int j=0;j<array
-
java中归并排序和Master公式详解
目录 基本思想 实现 对数器验证 递归时间复杂度计算 Master 公式 总结 基本思想 归并排序采取分治的思想进行排序,借用一张图片说明一下 将n个元素从中间切开,分成两部分.(左边可能比右边多1个数) 将步骤1分成的两部分,再分别进行递归分解.直到所有部分的元素个数都为1. 从最底层开始逐步合并两个排好序的数列.优点在于,分治之后,合并排序的过程时间复杂度是O(N)(只需要扫描一遍就可以将两个有序的数组合并成一个有序数组) 实现 public static void MergeSort(in
-
AngularJS日程表案例详解
功能:添加事件/完成事件/删除事件 <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>Document</title> <style> *{ margin: 0; padding: 0; } .note{ margin:0 auto; background: orange; color: ora