c语言归并排序非递归 - 腾讯云开发者社区 - 腾讯云

开发者社区

文档建议反馈控制台

文章/答案/技术大牛

发布

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

归并排序递归 1.基本思想主要使用了分治思想即大事化小，先使每个子序列有序，子使序列段有序，将两个有序表合并成一个有序表 2....使用两个函数完成归并因为想要malloc只开辟一块空间，而不是设置在mergesort1函数中每递归一次开辟一块空间,极大节省开辟空间开销 3....); //第二种拷贝方式 /*for (i = 0; i <= right; i++) { a[i] = tmp[i]; }*/ } void mergesort(int* a, int n)// 归并排序...归并排序非递归 1....代码 void mergesortNonR(int* a, int n)//归并排序非递归 { int* tmp = (int*)malloc(sizeof(int) * n); if

5841 0

非递归版归并排序

非递归版的归并排序，省略了中间的栈空间，直接申请一段O(n)的地址空间即可，因此空间复杂度为O(n),时间复杂度为O(nlogn); 算法思想：　　开始以间隔为1的进行归并，也就是说，第一个元素跟第二个进行归并...第三个与第四个进行归并；　　然后，再以间隔为2的进行归并，1-4进行归并，5-8进行归并；　　再以2*2的间隔，同理，知道2*k超过数组长度为止。...while(i<length){ Merge(arr,temp,i,length); i *= 2; } 　　当不够两组进行归并是，如果超过k个元素，仍然进行归并

7117 0

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

是的

没有找到

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

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

3311 0

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

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

3491 0

归并排序含非递归版

1.归并排序的原理归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。...然后使用归并的方式将左子树和右子树归并成有序数组，再将其拷贝会原数组，这样对应的子树便会有序，再递归返回，不断地递归。直到根左子树和根右子树有序，再归并和拷贝，整个数组就会变得有序。...归并排序需要开额外的空间，但每次递归都要开空间显然是不合理的，因此我们使用一个函数来完成递归的部分。...memcpy(arr+begin,a+begin,(end-begin+1)*sizeof(int)); } 2.5测试 3.非递归实现归并排序根据我们之前的排序我们可以看到它的本质是和预排序差不多的形态...; }*/ memcpy(arr + i, a + i, sizeof(int) * order); } gap *= 2; } free(a); } 3.4修改测试至此，归并排序的递归版和非递归版讲解完成

2301 0

【分治】归并排序：递归版 && 非递归版

nums = [5,1,1,2,0,0] 输出：[0,0,1,1,2,5] 提示： 1 <= nums.length <= 5 * 104 -5 * 104 <= nums[i] <= 5 * 104 递归版归并排序... 其实我们之前就已经接触过归并排序了，就是很经典的分治思想，如下图所示：它和快速排序的思想一样，都是基于分治思想的，但不同的是，快速排序是先对当前数组区间进行处理，然后再递归左右区间继续处理，...而归并排序则是先递归左右区间进行处理，等左右区间都处理完之后才返回给当前数组区间进行合并处理，所以归并排序相当于是后序遍历！ ...nums.size()); // 开辟一个辅助数组 merge_sort(nums, 0, nums.size() - 1, tmp); return nums; } }; 非递归版归并排序... 思路：与递归不同的是，迭代是不需要分解的，只需要控制好每次归并的区间，让它们从一一归并、二二归并、四四归并……即可，直到最后归并成一个完整的数组。

1211 0

排序-归并排序，一种外排序，递归，非递归，磁盘？

官网的一段描述，官网地址如下，友情提示:官网左边导航栏最下方支持中英文语言切换哦 https://shardingsphere.apache.org/document/current/cn/features...该算法是将已有的子序列不断进行合并从而最终达到全局有序，一般我们的实现都是二路归并，就是两个有序的子序列进行合并，但也可以进行多路归并(将大于两个的子序列进行合并) 我们通过一个简单的归并排序(递归)来分析时间...我们分析上面的代码，看看归并排序的复杂度怎么样呢，首先递归的终止条件必须确定，就是数组大小小于等于1时，递归终止，我们不断通过对待排序的数据array进行折中，从而达到最终二路归并时left，right...复杂度总结时间复杂度：nlog2(n) 空间复杂度：O(n) 除了递归实现，你能想到非递归怎么实现吗？...非递归实现二路归并排序一般非递归代替递归，递归其实利用了操作系统的栈空间存储临时数据，所以两种方案，一是利用栈数据结构，二是利用变量(这种相对局限一点) ?

1.2K2 0

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

本文主要介绍2路归并排序的递归实现。 2路归并排序的简单介绍归并排序的算法思想归并排序的算法思想基于对一个数组的两个已排序子数组的排序–Merge。...//因归并排序的第一步是划分，步长一步步翻倍 //因待排序的数组的长度可能是奇数，而步长总是2的整数倍，故将step的上限定为数组长度的一半并向上取整，即c.length/2 + 1 while(step...(b.c[i] + " "); } } } 算法笔记的迭代归并排序代码归并排序每次分组时组内元素上限都是2的幂次。..., 只是多算了一些分解数组的时间) 下图图示了归并排序的归并树, 每一层的代价为 CN 一共有log2(N+1), 所有的代价和为 T(N) = C(log(N)) + C(N), 使用大 O 记号去掉常量和低阶项得到该算法时间复杂度...非递归)实现》本文链接：https://wnag.com.cn/900.html 特别声明：除特别标注，本站文章均为原创，本站文章原则上禁止转载，如确实要转载，请电联：wangyeuuu@qq.com

1.6K3 0

5.比较排序之归并排序（非递归）

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

2.5K9 0

C语言快速排序（非递归）图文详解

前言：上一期分析了快速排序的三种写法，这三种写法有一个相同点，都是采用递归形式来实现的，那么有没有非递归的方法实现呢？...答案是当然有，用非递归的方法实现快速排序，其实可以借助数据结构中的栈来模拟实现递归的过程。...思路图分析: 因为使用c语言写的，所以需要我们自己写一个栈，栈的实现我这里不再过多赘述，我会把栈的码放在最后。假如我们现在有下面这组数组，我们要对它进行排序。...（注意下面的数字代表下标）好，接下来开始用栈模拟递归：（图中栈中的数字均表示下标） 1.第一次入栈：将整个数组入栈，也就是下标为0-8 2.第一次出栈：每次出栈，对出栈的下标区间进行一次部分排序，...现在就不难感受出，这其实是在模拟递归的过程。

5311 0

归并排序递归版和非递归版的实现（java）

/xujun94/note/424570 关于二分查找的，可以参考我的这篇博客二分查找的相关算法题关于归并排序的的，可以参考我的这篇博客归并排序递归版和非递归版的实现（java）关于快速排序的...，可以参考我的这篇博客快速排序的相关算法题（java）转载请注明原博客地址： http://write.blog.csdn.net/postedit/51292207 什么是归并排序归并排序其实就做两件事...return true; } 源码如下： package com.xujun.mergesort1;public class MergeSort2 { /** * 二路归并排序的递归算法...return true; MSortRecursive(t, 0, t.length - 1); return true; } /** * 二路归并排序的递归算法...，可以参考我的这篇博客归并排序递归版和非递归版的实现（java）转载请注明原博客地址： http://write.blog.csdn.net/postedit/51292207 源码下载地址：

1.1K1 0

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

1 快速排序非递归利用迭代的方式来模仿递归，快速排序递归的本质也就是它可以拿到那些待排序的区间，那么不就说明了只要我们右那些待排序的区间就可以不再需要递归了。...//非递归版本 void QuickSortNonR(int* a, int begin, int end) { stack s; InitStack(&s); //先入left再入right...归并排序基本思想：归并排序（MERGT-SORT）是建立在归并操作上的一种有效的排序算法，该算法是采用分治（Divide and Conquer）的一个非常典型的应用。...若将两个有序表合并成一个有序表，称为二路归并。归并排序核心步骤：合并时的动图：其实归并排序很简单，像分解的过程，不是和快速排序很像嘛，都是传数组和区间。...，再封装一个函数来实现 _MergeSort(a, tmp, 0, n - 1); } 归并排序的特性总结：归并排序缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题

2571 0

【C语言数据结构】排序（快速排序及多种优化|递归及非递归版本）

快排优化三数取中法选key 递归到小的子区间时，可以考虑使用插入排序三数取中法快排对于有序的数据，效率不是很高。如上图，我们前面的快排是固定选key的，也就是左边第一幅图，效率很低。...我们就可以在最后几层时，使用其他排序方法进行。这里使用插入排序。...cur) Swap(&a[prev], &a[cur]); ++cur; } Swap(&a[prev], &a[keyi]); keyi = prev; return keyi; } 非递归版本快排...非递归版本的快排需要用到栈。...>top == 0) //{ // return true; //} //else //{ // return false; //} return pst->top == 0; } 非递归代码实现

3081 0

【数据结构与算法】：非递归实现快速排序、归并排序

1.非递归实现快速排序快速排序的非递归实现主要依赖于栈（stack）来模拟递归过程中的函数调用栈。...，也是一次取一组进行排序，递归寻找每个区间 2.归并排序假如我们已经有了两个已经排序好的数组，我们如何让他们并为一个有序的数组呢？...我们的做法就是用两个索引进行比较，然后插入一个新的数组完成排序，这就是归并排序的基础思路那如果左右不是两个排序好的数组呢？...下面是归并排序的算法步骤：递归分解数组：如果数组的长度大于1，首先将数组分解成两个部分。...通常这是通过将数组从中间切分为大致相等的两个子数组递归排序子数组：递归地对这两个子数组进行归并排序，直到每个子数组只包含一个元素或为空，这意味着它自然已经排序好合并排序好的子数组：将两个排序好的子数组合并成一个排序好的数组

7471 0

【初阶数据结构】打破递归束缚：掌握非递归版快速排序与归并排序

时间与空间复杂度顺序表单链表带头双向循环链表栈队列循环队列树与二叉树排序引言本章将单独分享关于非递归实现快排和归并排序，可以帮助我们更好地理解递归和熟悉使用数据结构。...图片个人主页：是店小二呀C语言笔记专栏： C语言笔记C++笔记专栏： C++笔记初阶数据结构笔记专栏：初阶数据结构笔记喜欢的诗句:无人扶我青云志我自踏雪至山巅一、非递归实现快速排序void...&s, left);} if (keyi + 1 非递归实现快速排序也是需要通过快速排序思想来走的...说明不存在数据，不需要压栈，等到栈为空结束排序。二、非递归实现归并排序由于快速排序采用是前序遍历满足栈相关数据结构的特性，然后归并排序属于后序排序因此不是通过使用栈区模拟非递归实现归并排序。...如果采用栈去模拟实现非递归归并排序，由于归并排序不像快速排序不是出栈既排序，而是等到栈为空，开始归并排序，然而没有归并操作这种做法。

2171 0

【C语言】深入解析归并排序

在C语言编程中，归并排序是一种高效且稳定的排序算法。它采用分治法将问题分解成更小的子问题进行解决，然后合并结果。...left, int right) { if (left < right) { int mid = left + (right - left) / 2; // 递归排序两个子数组...归并排序函数mergeSort：递归地将数组分成两半，直到每个子数组只有一个元素。调用merge函数合并已排序的子数组。...，以减少递归调用的开销。...结论归并排序是C语言中一种高效且稳定的排序算法，其基于分治法的思想使其在处理大型数据集时表现出色。尽管归并排序需要额外的空间，但通过合理的优化方法，可以在实际应用中达到良好的性能。

4541 0

归并排序-MergeSort (C语言详解)

本章也会深入介绍归并排序的两种写法, 递归版本的归并排序与非递归版本的归并排序. 博客主页:酷酷学!!! 您的支持是我更新的最大动力!...归并排序的递归法首先我们需要具备这样一个思想, 如果两组数据有序, 我们就可以进行归并, 取小的数据进行依次排列, 那么我们就需要一个临时的数组进行存放, 首先动态申请块与数组空间大小相同的空间, 然后进行内层函数的递归调用...end2) { tmp[j++] = a[begin2++]; } memcpy(a+begin, tmp+begin, sizeof(int) * (end - begin + 1)); } 归并排序的非递归法...memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1)); } gap *= 2; } free(tmp); tmp = NULL; } 非递归法与递归法的思路是一模一样的...if (begin2 >= n) { break; } if (end2 >= n) { end2 = n - 1; } 如此非递归版的归并排序我们也完成了

1.1K1 0

归并排序(C语言实现)

首先了解排序有以下几种类型然后我们来了解一下他的思想，什么叫归并排序，他又是怎么完成排序的？ 1.介绍归并归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。...作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；自下而上的迭代； 2.算法步骤申请空间，使其大小为两个已经排序序列之和...，该空间用来存放合并后的序列；设定两个指针，最初位置分别为两个已经排序序列的起始位置；比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；重复步骤 3

1911 0

归并排序的递归实现

本文主要介绍2路归并排序的递归实现。 2路归并排序的简单介绍下面是归并排序的流程图。 ?...可以看到，每次程序都将数字两两分组（n/2个组），组内单独排序，最后将这些组两两合并，生成n/4个组，组内再单独排序。直到最后只剩下一个组为止。 2路归并排序的时间复杂度为O(logN)。...2路归并排序的递归代码实现 2路归并排序的代码递归实现特别简单，只要重复把当前区间[left,right]分为两半，对两边的子区间[left,mid]和[mid+1,right]分别进行递归，最后将两个已经有序的子区间合并为有序区间即可...代码如下： #include const long long maxn = 100005; //将array数组的当前区间[left,right]进行归并排序 void mergeSort...参考算法笔记3105ProblemB 基础排序III：归并排序版权所有：可定博客 © WNAG.COM.CN 本文标题：《归并排序的递归实现》本文链接：https://wnag.com.cn/898

7912 0

数据结构：归并排序（自顶向下和自底向上）递归和非递归

_mergeSortBU(int *a, int n) { for(int sz=1; sz<n; sz+=sz) //对a[i...i+sz-1]和a[i+sz....i+2*sz-1]进行归并.../*(1)为了保证由两个归并段i+sz < n (2)为了保证不越界 min(i+2*sz-1, n-1)*/ for(int i=0; i+sz<n; i+=

3903 0

点击加载更多

相关资讯

热门标签

活动推荐

运营活动

活动名称

广告关闭