排序算法8----归并排序(非递归)(C)

这篇具有很好参考价值的文章主要介绍了排序算法8----归并排序(非递归)(C)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

       1、介绍

        归并排序既可以是内排序(在内存上的数据排序),也可以是外排序(磁盘上)(硬盘)(在文件中的数据排序)。

        其他排序一般都是内排序。

        区别于快速排序的非递归,归并排序非递归不适合使用栈。

        因为快速排序的本质是一种前序递归,而归并排序的本质是一种后序递归,并没有“根”来区分左右。

        那么归并排序的非递归应该怎么样实现呢?

        2、思想

        我们先想想归并的思想和目的:递归的分治是将数组分割成两边有序的子序列,然后再合并这两个。那么我们是否可以直接将数组中两两元素归并呢?答案是:对的!因为我们将数组中所有元素看作两两一组(每组数据中都各有一个元素),那么这一组中的两个元素单个来看就是有序的子序列,然后合并这两个元素。再往上就是四四一组(每组数据中都各有两个有序的元素),八八一组........排序算法8----归并排序(非递归)(C),排序算法,排序算法,c语言,算法

        听起来好像很简单,其实坑很多,下面慢慢实现。

        3、代码

void MergeSortNonR_incline(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail\n");
		exit(-1);
	}

	int gap = 1;//1-1归
	//gap代表归并每组数组个数,即gap个和gap个归并
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)//[0,n)
		{
			int begin1 = i, end1 = i + gap - 1;//第一组
			int begin2 = i + gap, end2 = i + 2 * gap - 1;//第二组
			//[begin1,end1],[begin2,end2] 归并
			//[0,0]-[1,1]归,[2,2]-[3,3],[4,4]-[5,5]....
			//[0,1]-[2,3]归, [4,5]-[6,7]....
			//[0,3]-[4,7]归, [8,11]-[11,15]......
			// ......
			//注意:begin1不会越界,end1,begin2,end2都可能越界,所以要修正
			if (end1 >= n || begin2>=n)
				break;
			if (end2 >= n)
				end2 = n - 1;

			//合并,将arr中对应位置,放入tmp的对应位置
			int j = begin1;
			while (begin1 <= end1 && begin2 <= end2)
			{

				if (arr[begin1] < arr[begin2])
					tmp[j++] = arr[begin1++];
				else
					tmp[j++] = arr[begin2++];
			}


			while (begin1 <= end1)
			{
				tmp[j++] = arr[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[j++] = arr[begin2++];
			}

			//[begin1,end1],[begin2,end2]
			memcpy(arr + i, tmp + i, sizeof(int) * (end2-i+1));//每次归并完拷贝回去
		}
		gap *= 2;
	}

	free(tmp);
	tmp = NULL;
}

        4、实现效果

	int arr[] = { 1,6,41,32,5,12,7,11 };
	int size = sizeof(arr) / sizeof(int);
	printf("原数组\n");
	for (int i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");

	printf("排序后\n");
	MergeSortNonR_incline(arr, size);
	for (int i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");

原数组:1 6 41 32 5 12 7 11

排序后:1 5 6 7 11 12 32 41文章来源地址https://www.toymoban.com/news/detail-801445.html

到了这里,关于排序算法8----归并排序(非递归)(C)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 八大排序算法之归并排序(递归实现+非递归实现)

    目录 一.归并排序的基本思想 归并排序算法思想(排升序为例) 二.两个有序子序列(同一个数组中)的归并(排升序) 两个有序序列归并操作代码: 三.归并排序的递归实现 递归归并排序的实现:(后序遍历递归) 递归函数抽象分析:  四.非递归归并排序的实现 1.非递归归并排序算法思想

    2024年02月03日
    浏览(42)
  • 排序算法进阶——归并排序【详细图解,递归和非递归】

    在了解归并排序之前让我们先了解一下归并这一算法吧! 归并算法一般应用于合并两个已经有序的序列,使合并后的序列也有序,是一个时间复杂度为O(N)的算法,不过一般要借助两个要排序的序列的元素个数个额外的空间。 一一一一一一一一一一一一一一一一一一一一一

    2024年01月24日
    浏览(45)
  • 排序算法之七:归并排序(非递归)

    我们之前学习了递归实现的归并排序,是分治的思想,即先分解,再归并 这篇文章我们讲一下非递归的实现 非递归实现的思路是模拟递归的过程,在递归过程中,我们找key将数组分成左右数组,然后递归子数组,知道该数组剩一个元素,然后归并:两个两元素数组归并为四

    2024年01月18日
    浏览(43)
  • 排序算法8----归并排序(非递归)(C)

            归并排序既可以是 内排序 (在内存上的数据排序),也可以是 外排序(磁盘上)(硬盘) (在文件中的数据排序)。         其他排序一般都是内排序。         区别于快速排序的非递归,归并排序非递归不适合使用栈。         因为快速排序的本质是一种

    2024年01月18日
    浏览(47)
  • 十大排序算法(中):冒泡排序,快速排序(递归和非递归)、归并排序(递归和非递归)

    这篇文章,我们接着来讲剩下的排序算法:冒泡排序,快速排序(递归和非递归)、归并排序(递归和非递归) 中心思想: 交换就是指根据序列中的两个元素的比较结果来对换这两个元素在序列中的位置,特点就是:将值较大的元素向序列尾部移动,将值较小的元素向序列

    2024年02月05日
    浏览(57)
  • 排序篇:归并排序的递归,非递归以及计数排序的实现(C语言)

    目录 一:归并排序 (1)归并排序的基本思想 (2)递归版本 ①实现思路 ②合并 ③递归实现有序 ④最终代码 (3)非递归版本 ①实现思路 ②控制分组 ③最终代码 (4)时间,空间复杂度分析 (5)小结 二:计数排序 (1)计数排序的基本思想 (2)实现思路 (3)图解加最终代码 (4)时间,空间复杂

    2024年02月04日
    浏览(68)
  • [排序算法]:归并排序(Merge Sort)(递归与非递归实现详解)

            归并排序,是创建在归并操作上的一种有效的排序算法。算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。归并排序思路简单,速度仅次于快速排序,为稳定排序算法,一般用于对总体无序,但是各子项相对有序的数列。

    2024年01月20日
    浏览(45)
  • 快速排序、希尔排序、归并排序、堆排序、插入排序、冒泡排序、选择排序(递归、非递归)C语言详解

    1.排序的概念及其运用 1.1排序的概念 排序 :所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性 :假定在待排序的记录序列中,存在多个具有相同的的记录,若经过排序,这些记录的相对次序保持不变,即在原序

    2024年02月03日
    浏览(50)
  • 数据结构排序——详细讲解归并排序(c语言实现递归及非递归)

    上次是快排和冒泡:数据结构排序——详解快排及其优化和冒泡排序(c语言实现、附有图片与动图示意) 今天为大家带来归并排序 归并排序是一种分治算法,它将序列分成两个子序列,分别对 子序列进行排序 ,然后将排序好的子序列 合并起来 。这个过程可以 递归 地进行,

    2024年01月22日
    浏览(67)
  • 【数据结构与算法】:非递归实现快速排序、归并排序

    🔥 个人主页 : Quitecoder 🔥 专栏 :数据结构与算法 上篇文章我们详细讲解了递归版本的快速排序,本篇我们来探究非递归实现快速排序和归并排序 快速排序的非递归实现主要依赖于栈(stack)来模拟递归过程中的函数调用栈。递归版本的快速排序通过递归调用自身来处理子

    2024年03月24日
    浏览(55)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包