首页
学习
活动
专区
圈层
工具
发布

归并排序的递归实现

本文主要介绍2路归并排序的递归实现。 2路归并排序的简单介绍 下面是归并排序的流程图。 ?...可以看到,每次程序都将数字两两分组(n/2个组),组内单独排序,最后将这些组两两合并,生成n/4个组,组内再单独排序。直到最后只剩下一个组为止。 2路归并排序的时间复杂度为O(logN)。...2路归并排序的递归代码实现 2路归并排序的代码递归实现特别简单,只要重复把当前区间[left,right]分为两半,对两边的子区间[left,mid]和[mid+1,right]分别进行递归,最后将两个已经有序的子区间合并为有序区间即可...问题: 怎么表达递归边界(即最后只剩下一个元素)? if(left < right) //当各自剩下一个元素时,left=right,退出if语句 拆分出来的数组元素要怎么存放?...参考 算法笔记3105ProblemB 基础排序III:归并排序 版权所有:可定博客 © WNAG.COM.CN 本文标题:《归并排序的递归实现》 本文链接:https://wnag.com.cn/898

1.2K20

迭代归并:归并排序非递归实现解析

前言 归并排序的思想上我们已经全部介绍完了,但是同时也面临和快速排序一样的问题那就是递归消耗的栈帧空间太大了,所以对此我们必须掌握非递归的排序思想。...文章目录 前言 一、非递归实现的思想 二、非递归实现的过程 2.1 非递归实现的调整 2.2 调整思路讲解 2.3 归并非递归完整代码 三、归并排序的总结 文章结语: 一、非递归实现的思想 归并实现的思想无非就是先将...既然要用非递归那么我们是不是可以这样想 直接吧每个区间定义为 1 进行归并然后再来进行循环到上一组归并排序: 这样就可以利用循环来吧归并排序非递归化了 二、非递归实现的过程 好了具体思想那么我们懂了...以上就是非递归实现的代码了,但你真的以为非递归就这样结束了?...(3-0)虽然是相减了但是我们实际复制的是4个数 2.3 归并非递归完整代码 // 归并排序非递归实现 void MergeSortNonR(int* a, int n) { int* tmp =

75910
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    归并排序的迭代(非递归)实现

    本文主要介绍2路归并排序的递归实现。 2路归并排序的简单介绍 归并排序的算法思想 归并排序的算法思想基于对一个数组的两个已排序子数组的排序–Merge。...对整个数组进行一次小长度的Merge算法后,可以构成一个长度翻倍的Merge算法的条件而进行Merge算法,最终对整个数组实现排序。 归并排序的流程图 下面是归并排序的流程图。 ?...2路归并排序的迭代分布实现 基础–Merge (一)Merge算法的前提:一个数组可以划分为两个已排序的子数组,如1 4 7 8 2 5 10,此数组可以划分为两个已排序的子数组:1 4 7 8和2 5...O(Nlog(N)) 参考 九大排序之归并排序--实现及注意点 算法笔记3105ProblemB 基础排序III:归并排序 版权所有:可定博客 © WNAG.COM.CN 本文标题:《归并排序的迭代(...非递归)实现》 本文链接:https://wnag.com.cn/900.html 特别声明:除特别标注,本站文章均为原创,本站文章原则上禁止转载,如确实要转载,请电联:wangyeuuu@qq.com

    2K30

    【排序篇】快速排序的非递归实现与归并排序的实现

    1 快速排序非递归 利用迭代的方式来模仿递归,快速排序递归的本质也就是它可以拿到那些待排序的区间,那么不就说明了只要我们右那些待排序的区间就可以不再需要递归了。...归并排序 基本思想: 归并排序(MERGT-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治(Divide and Conquer)的一个非常典型的应用。...归并排序核心步骤: 合并时的动图: 其实归并排序很简单,像分解的过程,不是和快速排序很像嘛,都是传数组和区间。...if (tmp == NULL) { perror("malloc"); exit(-1); } //归并排序的核心逻辑,再封装一个函数来实现 _MergeSort(a, tmp,...0, n - 1); } 归并排序的特性总结: 归并排序缺点在于需要O(N)的空间复杂度,归并排序的思考更多的是解决在磁盘中的外排序问题 时间复杂度:O(N*logN) 空间复杂度:O(N) 稳定性:稳定

    60310

    归并排序 递归版和非递归版的实现(java)

    https://blog.csdn.net/gdutxiaoxu/article/details/51292207 归并排序的实现(java) 本文固定链接:https://www.zybuluo.com.../xujun94/note/424570 关于二分查找的,可以参考我的这篇博客二分查找的相关算法题 关于归并排序的的,可以参考我的这篇博客归并排序 递归版和非递归版的实现(java) 关于快速排序的...,可以参考我的这篇博客 快速排序的相关算法题(java) 转载请注明原博客地址: http://write.blog.csdn.net/postedit/51292207 什么是归并排序 归并排序其实就做两件事...“合并”——将划分后的序列段两两合并后排序。 首先我们来看一下分解是怎样实现的呢?...可以参考我的这篇博客二分查找的相关算法题 关于归并排序的的,可以参考我的这篇博客归并排序 递归版和非递归版的实现(java) 转载请注明原博客地址: http://write.blog.csdn.net

    1.5K10

    排序算法指南:归并排序(非递归)

    前言: 非递归实现归并排序,通常被称为 “自底向上”(Bottom-Up) 的归并排序,与递归版本(先将数组对半拆分直到只剩一个元素,再通过递归栈回溯合并)不同,非递归版本直接从最小的子数组...一、归并排序非递归的核心思路 递归算法转换为非递归实现主要有两种常见方法: 1.使用栈结构模拟递归过程 2.将递归逻辑改写为循环结构 1.1 栈模拟失效 如果仅通过栈结构模拟递归过程,我们只能够做到拆分数组...1.2 循环结构实现 递归版本是“先拆分,后合并”,而非递归版本则是直接从最小的子数组开始“只合并”,不需要拆分。...③步长=4:继续合并为 8张…… ④循环:直到步长超过数组长度,排序完成 二、归并排序非递归的实现流程 假设存在如下数组 [10, 6, 7, 1, 3, 9, 4, 2],一步一步演示循环结构是如何控制归并过程...3.3递归与非递归的区别 你可能会疑惑:“为什么递归版本的归并排序,好像没有这么多复杂的边界判断?

    40410

    排序-归并排序,一种外排序,递归,非递归,磁盘?

    这相当于对多个有序的数组进行排序,归并排序是最适合此场景的排序算法。...该算法是将已有的子序列不断进行合并从而最终达到全局有序,一般我们的实现都是二路归并,就是两个有序的子序列进行合并,但也可以进行多路归并(将大于两个的子序列进行合并) 我们通过一个简单的归并排序(递归)来分析时间...我们分析上面的代码,看看归并排序的复杂度怎么样呢,首先递归的终止条件必须确定,就是数组大小小于等于1时,递归终止,我们不断通过对待排序的数据array进行折中,从而达到最终二路归并时left,right...复杂度总结 时间复杂度:nlog2(n) 空间复杂度:O(n) 除了递归实现,你能想到非递归怎么实现吗?...非递归实现二路归并排序 一般非递归代替递归,递归其实利用了操作系统的栈空间存储临时数据,所以两种方案,一是利用栈数据结构,二是利用变量(这种相对局限一点) ?

    1.5K20

    排序算法全解析:归并排序、非递归实现与映射型排序

    若数组是奇数个数据依旧一样,(0+2)/2=1,分成[0,1],[2,2]两个序列,然后以依次类推 二分也是和二叉树一样的递归过程 归并排序和快速排序的参数有所不同,归并排序函数这里只需要两个参数...,一个是指向数组的指针,一个是数组数据个数(n),给了n就知道数据下标范围是[0,n-1],然后在一个内部函数实现归并排序中分解的过程 接下啦就是合并了,第一次合并,10和6合并时先对两个序列取值,取到第一个值后比较...,谁小谁放前,开一个临时的数组暂存合并后的结果,申请数组的大小和原数组大小一样(8个数据) 大致过程就是这样,接下来看代码的实现 由于归并排序是一个递归的代码,所以想要求时间复杂度就要按照递归算法的时间复杂度进行推理...在外层的MergeSort函数内没有循环,_MergeSort函数内的while循环是用于两个序列分开进行数据的比较,实际上可以看作是对一个数组进行遍历,所以单词递归的时间复杂度为n。...分解是一个二叉树不断递归的过程,所以递归的次数就和二叉树的高度有关系,所以递归次数为logn 由于归并排序中malloc了一个和原数组一样大小空间的数组,所以其空间复杂度为O(n) 可以看到归并排序和希尔排序

    37610

    4.比较排序之归并排序(递归)

    归并排序里运用到算法里很重要的一个思想——分治法:将原问题分解为几个规模较小但类似于原问题的子问题——《算法导论》。...在每一层递归中都有3个步骤:   1.分解问题   2.解决问题   3.合并问题的解   举例待排序数组:{6, 5, 3, 1, 7, 2, 4},将它原始序列做分解。 ?   ...将他们进行两两归并排序形成二叉树(也称为2路归并算法),可见二叉树的根节点即为最终序列。在这个过程中我们完成了剩余的两个步骤:解决问题和合并问题。 ?   理论很简单,实践很“复杂”。...对于归并排序的理论从上面的二叉树就看的很明白,将原始待排序数组不断分解最后看成是二叉树的叶子节点,再把它们两两排形成新的节点,逐渐归并为一个节点,此时的节点即为排好序的数组序列。   ...Java 1 package com.algorithm.sort.merge; 2 3 import java.util.Arrays; 4 5 /** 6 * 归并排序(递归)

    99180

    用 C 语言玩转归并排序:递归实现的深度解析

    在算法世界里,排序算法是基础中的基础,而归并排序凭借其稳定的时间复杂度和清晰的逻辑结构,成为很多开发者学习递归思想的首选案例。...今天我们就以 C 语言为工具,从零拆解归并排序的递归实现,带你理解 “分治思想” 如何落地为可执行的代码。...,避免栈溢出 // 归并排序递归函数:负责拆分与合并 void merge_sort(int arr[], int left, int right) { // 递归终止条件:当子数组只有1个元素时(left...递归函数的核心:终止条件与拆分逻辑 merge_sort函数是整个算法的灵魂,它的参数arr是待排序数组,left和right分别代表当前排序区间的左右边界。...五、总结:递归与分治的启示 通过 C 语言实现归并排序,我们不仅学会了一种高效的排序算法,更理解了递归思想的本质 ——将复杂问题拆解为多个相同的子问题,解决子问题后再整合结果。

    43910

    归并排序含非递归版

    1.归并排序的原理 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。...如图所示: 2.实现归并排序 归并排序需要开额外的空间来辅助实现 之所以不在原数组实现,是因为如果你使用交换的方式来进行排序,可能会将原数组已经排好序的部分又一次变回无序,而使用令数组向后移动的方式进行对应的排序...归并排序需要开额外的空间,但每次递归都要开空间显然是不合理的,因此我们使用一个函数来完成递归的部分。...思考一下,新创建的函数的参数应该有哪些,首先得有原数组,其次得有我们开辟好的数组,而我们要如二叉树一般形成对应的递归,显然需要区间,而区间的形成需要两个数来辅助,因此可以传递两个代表区间的数进来,可以取名为...memcpy(arr+begin,a+begin,(end-begin+1)*sizeof(int)); } 2.5测试 3.非递归实现归并排序 根据我们之前的排序我们可以看到它的本质是和预排序差不多的形态

    56710

    数据结构排序——详细讲解归并排序(c语言实现递归及非递归)

    上次是快排和冒泡:数据结构排序——详解快排及其优化和冒泡排序(c语言实现、附有图片与动图示意) 今天为大家带来归并排序 1.基本思想 归并排序是一种分治算法,它将序列分成两个子序列,分别对子序列进行排序...在合并子序列的过程中,需要比较两个子序列的元素,并按顺序将它们合并成一个有序序列 注意:归并排序的关键在于合并两个有序的子序列,这一步需要额外的空间来存储中间结果。...在实际的实现中,可以使用递归或非递归的方式来完成归并排序 2.递归实现 递归归并排序: 如果序列长度小于等于1,无需排序,直接返回 将序列分成两个子序列,分别进行递归归并排序 合并两个已排序的子序列...(int)); PrintArray(a, sizeof(a) / sizeof(int)); return 0; } 3.非递归实现 非递归实现归并排序是一种迭代式的排序算法,它避免了递归调用带来的额外开销...,通常使用循环和迭代来实现归并排序的过程: 确定归并区间的思路:对于给定的数组,首先将相邻的元素两两归并(gap=1),然后将归并的区间长度不断扩大,依次归并相邻的区间、长度为 2 的区间、长度为

    65710

    5.比较排序之归并排序(非递归)

    在上一节中讲解了归并排序的递归版《4.比较排序之归并排序(递归)》,通常来讲,递归版的归并排序要更为常用,本节简单介绍下非递归版的归并排序。...思路和递归版相同,均为先分解后合并,非递归的重点在于如何确定并合理的分解待排序数组。   对于递归我们是这么做的: ?   ...对于非递归来讲,切分的不向递归从大到小,非递归实际上从一开始构建算法的时候都从小到大。   第一次切分排序就确定最小单位为1个数字,将2个数字组合为一组。 ?   ...也就是说非递归归并排序中分解的依据为:从切分的水长度为1开始,一次归并变回原来的2倍。每完成一次归并则 len = len * 2。   ...(非递归) 19 * 从切分的数组长度为1开始,一次归并变回原来长度的2倍 20 * @param nums 待排序数组 21 * @return 排好序的数组 22

    2.8K90

    递归 —— 二分查找法 —— 归并排序

    PS:什么是递归、二分查找、归并排序。...递归排序大家都不陌生,递归简单的说就是自己在没有达到目的的同时在此调用本身,把一个大问题层层转化为和原问题相似的小问题解决,递归需要有边界条件、递归前进段和递归返回段。...归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。...3:归并排序 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。...归并排序的条件、使用优点 通过两个不同的有序数组,互相比较按照比较大小排序 把一个无序的数组分成N个数据,每个数据本身比较一次,之后再和下一个数组比较并合并,以此类推。

    1.8K40

    javaScript实现归并排序

    归并排序是一个O(nlogn)的算法,其基本思想就是一个分治的策略,先进行划分,然后再进行合并,下面举个例子。...它是一个在效率上高于一般排序的算法.一般排序:冒泡, 插入, 选择排序的时间复杂度为O(N^2), 而归并排序的时间复杂度为O(N*LOG N),如果N(及排序项的数目)是10000.那么N^2就是100000000...也就是如果这个数量的数据.如果用归并排序需要40S的时间,那么用插入排序则需要28个小时....归并排序算法的核心: 核心思想就是分治算法.先进行划分,再进行排序归并.归并两个有序的数组.即归并两个有序的数组A和B,然后就有了包含这两个新数组的数组C....Math.floor(array.length / 2); var left = array.slice(0, mid); var right = array.slice(mid); /* 递归分别对左右两部分数组进行排序合并

    98080

    Python实现归并排序

    待排序列表是无序的,使用二分法递归地将列表最终拆分成只有一个元素的子表,只有一个元素的列表一定是有序的,此时递归往回合并,即可依次将待排序列表拆分然后合并成一个有序的列表。...二、归并排序原理 归并排序的原理如下: 1....实现归并排序函数merge_sort(array)时,递归调用merge(left_array, right_array)函数。...所以归并排序中递归地将待排序列表进行拆分,直到拆分成只有一个元素的列表,然后调用merge(left_array, right_array)函数进行合并,这样依次递归合并,最终实现归并排序。...归并排序一直对待排序列表进行拆分,需要进行logn次拆分,在每一次递归合并中,需要进行n次比较和添加。

    1.7K40

    归并排序python实现

    归并排序python实现 归并排序 归并排序在于把序列拆分再合并起来,使用分治法来实现,这就意味这要构造递归算法 首先是一个例子 ? 原序先通过一半一半的拆分,然后: ?...然后再一步一步的向上合并,在合并的过程中完成了排序,合并排序算法如下: def merge(s1,s2,s): """将两个列表是s1,s2按顺序融合为一个列表s,s为原列表""" #...,互相比较选择较小的那个数放入最后的序列,s是原序列,所以在一开始会有与len(s)的比较 完整算法 算法中通过递归并调用merge函数完成排序 def merge(s1,s2,s): """将两个列表是...i += 1 else: s[i+j] = s2[j] j += 1 def merge_sort(s): """归并排序...= s[0:mid] s2 = s[mid:n] # 子序列递归调用排序 merge_sort(s1) merge_sort(s2) # 合并 merge

    85660

    归并排序代码实现

    归并排序 给定你一个长度为 n 的整数数列。 请你使用归并排序对这个数列按照从小到大进行排序。 并将排好序的数列按顺序输出。 输入格式 输入共两行,第一行包含整数 n。...输出格式 输出共一行,包含 n 个整数,表示排好序的数列。...数据范围 1≤n≤100000 输入样例: 5 3 1 2 4 5 输出样例: 1 2 3 4 5 算法思路 算法的时间复杂度的话:最差的时间复杂度也有O(nlogn) 这个题需要记住的是这个归并排序的模板...那么也就意味着所有子区间都成了有序的序列。...(没有元素和一个元素算作序列有序) 然后不断将已有序的子序列递归合并,最终得到完全有序的序列 C++ #include using namespace std; const int

    66000
    领券