在部分递归调用mergeSort期间合并排序的无限循环问题 - 腾讯云开发者社区 - 腾讯云

开发者社区

文档建议反馈控制台

最新优惠活动

文章/答案/技术大牛

发布

面试高频题：归并排序详解

比如归并排序，“归并”二字就是“递归”加“合并”。 ——它是典型的分而治之算法。上图中，先把数组一分为二，然后递归地排序好每部分，最后合并。...我们再回忆一下归并算法的步骤： 1、数组分成两半，left和right 2、递归处理left 3、递归处理right 4、合并二者结果然后再来轻松翻译成代码： function mergeSort...mergeSort(array.slice(m)) return merge(left, right)} 递归是自身调用自身，不能无限次地调用下去，因此需要有递归出口（初始条件）。...它的递归出口是，当数组元素个数为小于2时，就是已经是排好序的，不需要再递归调用了。...归并排序需要额外空间，空间复杂度为O(n)，不是本地排序，相等元素是不会交换前后顺序，因而是稳定排序。时间复杂度为O(nlogn)，是比较优秀的算法，在面试题中出现的概率也很高。

3470 0

数据结构从入门到精通——归并排序

归并排序是一种典型的分治算法，它通过递归地将问题分解为更小的子问题来解决。这种递归性使得归并排序的实现相对简单明了，也易于理解和维护。...然而，递归也可能导致栈空间的消耗，因此在处理大规模数据时需要注意递归深度的问题。综上所述，归并排序作为一种高效稳定的排序算法，在实际应用中具有广泛的应用场景。...归并排序是一种分治算法，首先将原始数组递归地分成两个子数组，然后对子数组进行排序，最后将排序好的子数组合并成一个有序数组。代码中的MergeSort函数是对外接口，用于调用归并排序算法。...首先申请了一个临时数组tmp，用于存放归并过程中的临时结果。然后调用_MergeSort函数进行实际的归并排序操作。 _MergeSort函数是核心函数，用于实现归并排序的递归过程。...归并排序是一种分治算法，通过将数组分成两个部分，分别对这两个部分进行排序，然后将排好序的两个部分合并起来。在代码中，首先创建一个临时数组tmp，用来在合并过程中暂存排序后的结果。

1181 0

您找到你想要的搜索结果了吗？

是的

没有找到

【排序算法】归并排序详解！深入理解！思想+源码实现！

☁️分治法分治法在归并排序中的应用是将问题分解成更小的子问题，然后分别解决这些子问题，最后将子问题的解合并起来得到原问题的解。...⭐代码实现详解: 首先，将整个序列分为两部分，分别递归调用_MergeSort函数对左右两部分进行排序。...然后，计算中间位置mid，并分别递归调用_MergeSort函数对左右两部分进行排序。接下来，进行归并操作。...☁️非递归版归并实现非递归版是在递归上进行了修改,将其递归改为了循环。...递归实现的归并排序代码简洁易懂，但是由于递归调用的开销比较大，所以在实际应用中可能会使用迭代的方式来实现归并排序。适用性：归并排序适用于各种数据规模的排序，而且对于大规模数据的排序效果较好。

2621 0

【排序算法】归并排序

，然后我们调用_MergeSort()函数进行排序。..._MergeSort()函数会递归地将数组分成两个子数组,并对这两个子数组进行排序和合并，最后,我们释放临时数组tmp 递归版实现首先判断待排序的区间是否只有一个元素,如果是,则直接返回。...不同之处在于,递归版本使用递归调用来实现分治,而非递归版本使用循环来实现，有点类似于斐波那契数列，由前面两个相加推出后面。...在每次循环中,我们将 gap 乘以 2,这样可以保证每次合并的区间大小都是上一次的 2 倍。...：归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。

561 0

重读算法导论之算法基础

只不过在归纳法中，归纳步是无限地使用的，而这里存在循环终止，停止归纳。 ---- 用循环不变式验证插入排序初始化: 从上面的代码可以看到。...在循环之前，我们假设排好序的部分A只包含一个元素，此时A当然是满足排好序的。即初始化A满足循环不变式保持：下面分析每一个循环的过程。...直接来看下分治算法求解的三个步骤: 分解：分解原问题为若干子问题，这些子问题就是原问题规模较小的实例解决：递归地求解各个子问题合并：合并子问题的解成原问题的解算法上的分治一种最常见的表现就是递归调用...递归调用就是一个方法不停地对自己进行调用，每次调用的问题规模都会缩小，直至达到方法返回的临界值。归并排序就是分治算法思想的一个典型应用。...因此，在归并排序中当子问题变得足够小时，采用插入排序来使递归的叶变粗是有意义的。

89110 0

文心一言 VS 讯飞星火 VS chatgpt （203）-- 算法导论15.3 2题

这是一个典型的分治算法，它首先将数组一分为二，然后递归地对每一半进行排序，最后将两个已排序的半部分合并成一个有序的数组。...然而，在归并排序这种分治算法中，备忘技术并不有效，因为归并排序的递归过程中，子问题并不是独立的。...在归并排序中，我们需要同时合并两个已排序的子数组，而这个合并过程是无法通过仅仅存储子数组的前缀来避免重复计算的。...归并排序是一种分治算法，它的核心思想是将数组分成两半，分别对这两部分进行排序，然后将排序后的两部分合并。这个过程会递归地继续下去直到每个子数组只有一个元素，此时它们已经是排序好的。...即使子数组在不同的递归路径上出现，它们也是独立排序的，合并操作是唯一的，因此没有必要缓存之前的合并结果。 3.

1262 0

归并排序(递归+非递归)

归并排序递归 1.基本思想主要使用了分治思想即大事化小，先使每个子序列有序，子使序列段有序，将两个有序表合并成一个有序表 2....使用两个函数完成归并因为想要malloc只开辟一块空间，而不是设置在mergesort1函数中每递归一次开辟一块空间,极大节省开辟空间开销 3....(int* a, int n)// 归并排序递归 { int* tmp = (int*)malloc(sizeof(int) * n); mergesort1(a, 0, n - 1,tmp); free...归并排序非递归 1....思想将一个数组，通过gap分为几组进行合并，gap每次扩大2倍,gap<n 合并方式与递归相同第一个数组的 begin1 改为 i 第一个数组的 end1 改为 i+gap-1 第二个数组的

4721 0

排序7:归并排序

目录 1.排序思想 2.图解 3.递归版本 3.1子排序代码实现 3.2 剩下的主体部分 4.非递归版本 5.特性总结 ---- 1.排序思想归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法...分到最细的时候每次排序是两个数字排序或者是一个数字原地不动，那么我们可以设置一个for循环，每次 i 加上两个gap的值，就做到了跳到下一个需要的排序的区间。...然后每次gap的值×2，就解决了两个区间合并的问题。接下来就是细节问题：我们从前面可以知道我们下标是两个gap移动的，那么如果剩下的数个数不满足加的值呢？此时就会发生越界问题了。...修正第一组尾部：修正第二组全部：修正第二组的尾部：考虑完了越界问题，才能够高枕无忧的排序，非递归的排序和递归思路一样。这里就不过多叙述。...归并的缺点在于需要 O(N) 的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。 2. 时间复杂度： O(N*logN) 3.

2783 0

【算法】归并排序

归并排序先分割为两部分 , 然后两边分别排序 , 再进行合并 ; 先局部有序 , 后整体有序 ; 归并排序与快速排序比较 , 其比快排多花费 O(n) 的空间 , 其合并两个数组时..., 不能在原数组中进行 ; 快速排序 , 始终都在原数组中进行 , 只涉及到交换数组中的元素 ; 正式由于该额外数组的存在 , 因此归并排序 , 并不是排序的最优算法 ; 算法要点 : 合并数组中 ,...创建数组的时机 , 不要放在递归中 , 递归要调用很多次 , 频繁创建销毁数组 , 很耗费时间和空间 ; 代码示例 : class Solution { /** * 归并排序...int mergeArray[] = new int[A.length]; // 递归调用排序算法 mergeSort(A, 0, A.length...// 左侧排序 mergeSort(array, start, (start + end) / 2, mergeArray); // 右侧排序 mergeSort

6971 0

数组归并排序

（声明：文章全部图片均来自传智播客教师课件）归并排序是一种空间换时间的做法，排序的速度当然会提高很多，归并排序中会产生一个临时数组，这个临时数组用来把不断拆分到最后的有序数据进行合并，最后再把合并后的数据重新赋值给原数组...主要分为以下三个步骤： 1、把原数组无限拆分到最少元素（直至剩余一个）如下图表示： 2、把拆分的两组数据合并到临时数组，如下图表示：图片 3、最后把临时数组中的值覆盖掉原始数组的值，整个过程就是下图这样的...// 如果i的下标还没到最最后的位置，那么就循环把值赋给临时数组 temp[length] = arr[i]; length++; i++; } while (j <= mid) { // 如果j的下标还没到最最后的位置...) { if (first < last) { // 将数据分割成两份 int mid = (first + last) / 2; // 一次递归把两份左侧的数据和右侧的数据再次拆分 mergeSort...(arr, first, mid, temp); mergeSort(arr, mid + 1, last, temp); // 把拆分的数据进行排序（递归中，是从拆分到最后的2个或3个数进行排序） mergeArray

991 0

你所能用到的数据结构（四）

递归这个词我的理解应该是传递和回归，如何把自身的状态传递下去和如何回归到一个结果上是递归问题的基本思维方式。...关于如何归，就是要找到递归中止的条件，比如斐波那契数列那个，n=0就是数列的中止条件，别小看这个中止条件，如果不能找出这个中止条件或者定义错误的话，后果就是无限的递归，导致程序堆栈的崩溃，最终整个程序就很快的崩溃掉了...那么，再来看一个二分搜索的好了，二分搜索是在已经排序好的数列里面寻找目标数，比如{1,2,...,10},这种，如果是寻找2，那么先求出这一组数的中值5，2比5小，从而转到0-5这个部分，其中值是2,然后就找到了...归并排序简单的将就是将一个数列不断的平均分为两个小数列，然后每个小数列独立排序之后再合并在一起排序，也就是用若干有序的子序列得到一个有序的数列，为了说明，还是用一个例子好了，就用百度的这个例子好了：如...，然后排序右边的，最后将两个子序列合并起来，是不是思路特别的清晰？

61210 0

Java实现-归并排序算法-动图详解

归并排序详解（后序遍历）大家可能都对二叉树的后序遍历比较熟悉，实际上归并排序本质框架就是二叉树的后序遍历，根结点的遍历只不过换成了治（Merge方法的调用），本文将结合动图+代码的方式进行最通俗的讲解...「基本思想」：利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案修补在一起...left==right，每组的right和left都不相同，左边递归调用传值left的值不变，right值为mid，右边递归调用传值left为mid+1，因为mid是左边的最后一个，所以要加1，右边的值就是...mergeSort(arr, left, mid, temp); //向右递归进行分解动图分组中靠右的部分 mergeSort(arr, mid +...时间复杂度：O(nlogn) 空间复杂度：O(n+logn) 由于归并排序在归并过程中需要与原始记录序列同样数量的存储空间存放归并结果以及递归深度为log2n的栈空间，因此空间复杂度为O(n+logn)

7911 0

归并排序含非递归版

1.归并排序的原理归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。...如图所示： 2.实现归并排序归并排序需要开额外的空间来辅助实现之所以不在原数组实现，是因为如果你使用交换的方式来进行排序，可能会将原数组已经排好序的部分又一次变回无序，而使用令数组向后移动的方式进行对应的排序...归并排序需要开额外的空间，但每次递归都要开空间显然是不合理的，因此我们使用一个函数来完成递归的部分。...注意：两个区间不知道是哪个区间先完成循环，因此在外面需要将未完成循环的区间，补充回辅助数组中。搞定完归并后，使用memcpy将辅助数组中的内容拷贝回原数组，排序便结束了。...注意：我们之前使用拷贝函数均是拷贝2*gap个过去，在这里显然不合适，总区间长度应修正为end2-begin1，这个修正不应该放在最后，因为在进行归并的期间，begin1会++至end1 也不应该放在判断

1191 0

一文带你读懂排序算法（四）：归并算法

归并排序的基本思想核心是分治，就是把一个复杂的问题分成两个或多个相同或相似的子问题，然后把子问题分成更小的子问题，直到子问题可以简单的直接求解，最原问题的解就是子问题解的合并。...算法思想归并排序的主要思想是分治法，排序的方法就是按照大小顺序合并两个元素，接着依次按照递归的返回顺序，不断地合并排好序的子数组，直到最后把整个数组的顺序排好。...主要过程是：将n个元素从中间切开，分成两部分。（左边可能比右边多1个数）将步骤1分成的两部分，再分别进行递归分解。...在每一层里，我们都要进行合并，所涉及到的元素其实就是数组里的所有元素，因此，每一层的合并复杂度都是 O(n)，所以整体的复杂度就是 O(nlogn)。...建议：归并算法的思想很重要，其中对两个有序数组合并的操作，在很多面试题里都有用到，建议大家一定要把这个算法练熟。 —END—

2922 0

手把手教你写归并排序算法 (Java代码)

即先使每个子序列有序，再将已有序的子序列合并，得到完全有序的序列。这里给出一种递归形式的归并排序实现。...mergeSort(arr,left,mid);//对左半部分调用递归方法，使其有序 mergeSort(arr,mid + 1,right);//对右半部分调用递归方法...(arr,0,arr.length - 1);//调用写好的递归版归并排序方法 } 至此，我们便完成了归并排序算法的代码实现。...归并排序算法在排序时首先将问题进行分解，然后解决子问题，再合并，所以总时间=分解时间+解决子问题时间+合并时间。...分解时间就是把一个数组分解为左右两部分，时间为一常数，即O(1)；解决子问题时间是两个递归方法，把一个规模为n的问题分成两个规模分别为n/2的子问题，时间为2T(n/2)；合并时间复杂度为O(n)。

5563 0

排序进行曲-v3.0

空间复杂度分析：在每次递归合并的过程中，需要创建临时数组来存储合并后的子数组，临时数组的空间复杂度为 O(n)。在每次递归合并完成后，临时数组会被销毁，所以整个归并排序的空间复杂度为 O(n)。...例如，在某个数据库表中有大量的数据需要按照某个字段进行排序，可以使用归并排序算法将数据分割成多个较小的部分，分别对这些部分进行排序，然后再将排序好的部分合并起来。...Other 这些例子只是归并排序在实际中的一些应用，实际上归并排序的思想和方法也可以应用于其他问题，只需要将问题分割成更小的子问题，并将子问题的结果合并起来。...解释在mergeSort方法中，首先判断数组的长度是否小于等于1，如果是，则直接返回。然后创建一个临时数组 temp，并调用mergeSort方法对数组进行递归排序。...在mergeSort方法中，首先计算出数组的中间位置 mid，然后分别对左半部分和右半部分进行递归排序，最后调用merge方法将排序好的左右两部分合并起来。

1172 0

第十三天、归并排序

r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。...归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。 ...,iMidIndex); /*递归调用将iSourceArr[iMidIndex+1]~iSourceArr[iEndIndex]归并成有序的*/ MergeSort(iSourceArr...,iTempArr,iMidIndex+1,iEndIndex); /*调用函数将前两部分归并到iSourceArr[iStartIndex]~iSourceArr[iEndIndex]...,j = iMidIndex + 1,k = iStartIndex; while((i <= iMidIndex) && (j <= iEndIndex)) //当i和j都在要合并的部分中成立

4850 0

Go 数据结构和算法篇（七）：归并排序

所谓归并排序，指的是如果要排序一个数据序列，我们可以先把该序列从中间分成前后两部分，然后对这两部分分别做排序操作，再将排好序的两部分合并在一起，这样整个数据序列就都有序了。...归并排序使用了分治思想，分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。说到这里，可能你会联想起我们之前讲到的一个编程技巧 —— 递归，没错，归并排序就是通过递归来实现的。...二、示例代码通过上面的分析，我们知道归并=递归+合并，对应的 Go 实现代码如下： package main import ( "fmt" ) // 归并排序 func mergeSort...归并排序的时间复杂度推导过程归并的思路是将一个复杂的问题 a 递归拆解为子问题 b 和 c，再将子问题计算结果合并，最终得到问题的答案，这里我们将归并排序总的时间复杂度设为 T(n)，则 T(n) =...2*T(n/2) + n，其中 T(n/2) 是递归拆解的第一步对应子问题的时间复杂度，n 则是排序合并函数的时间复杂度（一个循环遍历），依次类推，我们可以推导 T(n) 的计算逻辑如下： T(n)

2452 0

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

，然后将排序好的子序列合并起来。...在合并子序列的过程中，需要比较两个子序列的元素，并按顺序将它们合并成一个有序序列注意：归并排序的关键在于合并两个有序的子序列，这一步需要额外的空间来存储中间结果。...在实际的实现中，可以使用递归或非递归的方式来完成归并排序 2.递归实现递归归并排序: 如果序列长度小于等于1，无需排序，直接返回将序列分成两个子序列，分别进行递归归并排序合并两个已排序的子序列...(a, tmp, left, mid); _MergeSort(a, tmp, mid+1,right );//这两部分都有序啦 //开始归并：归并到到tmp数组的相同位置，再拷贝回去 int...，它避免了递归调用带来的额外开销，通常使用循环和迭代来实现归并排序的过程：确定归并区间的思路：对于给定的数组，首先将相邻的元素两两归并（gap=1），然后将归并的区间长度不断扩大，依次归并相邻的区间

1051 0

合并排序

分治算法：用分治策略实现n个元素进行排序的方法。基本思想：将待排序元素分成大小大致相同的两个子集合，分别对两个子集合进行排序，最终排好序的子集合合并成所要求的排好序的集合。...源码： /* * mergeSort.cpp * 合并排序算法，算法导论P.17 * Created on: 2011-12-21 * Author: LiChanghai */...subMerge对任意数组排序，p, r为下标 //mergeSort(A, p, r)首先将数组A分为两部分 //然后递归调用其本身对这两部分分别排序 //依次递归下去，直到只剩2个数的时候完成这两个数的排序...//然后再层层返回调用处，将已排好序的子序列合并成更大的有序序列 //最后一次调用subMerge时完成数组的排序 template void mergeSort(vector...(vec, iterHead, iterDivide+1); //递归调用自身对前半段排序 mergeSort(vec, iterDivide+1, iterTail); //递归调用自身对后半段排序

7209 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云

扫码加入开发者社群

相关资讯

热门标签

活动推荐

运营活动

活动名称

广告关闭