【算法】排序——归并排序和计数排序

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

 =========================================================================

主页点击直达:个人主页

我的小仓库:代码仓库

C语言偷着笑:C语言专栏

数据结构挨打小记:初阶数据结构专栏

Linux被操作记:Linux专栏

LeetCode刷题掉发记:LeetCode刷题

算法头疼记:算法专栏 

=========================================================================

目录

前言

归并排序

 递归实现代码

非递归实现归并排序

计数排序

排序算法复杂度及稳定性分析


前言

上两篇文章讲解了插入排序选择排序以及交换排序,每种类型的排序大类下都有一到两种排序,今天给大家带来的是归并排序,和前面几种排序一样都属于比较排序中的一种,是通过比较数组中的元素来实现排序的,还给大家带来一种非比较排序计数排序,让我们开始今天的排序之吧!!!


归并排序

基本思想:
归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide andConquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

归并排序核心步骤: 

【算法】排序——归并排序和计数排序,算法,算法,排序算法,数据结构,c语言

这张图片看起来是不是非常眼熟?和上篇文章的快速排序非常的相似,归并排序也是一种类似与二叉树结构的排序,我们也是使用递归的思想来实现,归并排序是先将一整个乱序的数组分成若干个数组(极限情况下每一个数字可以看成一个数字)然后将每个有序的数组进行有序的合并,通过多次合并最终成为一个有序的数组。

 递归实现代码

【算法】排序——归并排序和计数排序,算法,算法,排序算法,数据结构,c语言

void _MergerSort(int* a, int* tmp,int begin, int end )
{
	if (begin >= end)
	{
		return;
	}
	int mid = (end + begin) / 2;
	//[begin,mid] [mid+1,end]
	_MergerSort(a, tmp, begin, mid);
	_MergerSort(a, tmp, mid + 1, end);

	//归并到tmp数组
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int index = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1]< a[begin2])
		{
			tmp[index++] = a[begin1++];
		}
		else
		{
			tmp[index++] = a[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		tmp[index++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[index++] = a[begin2++];
	}
	memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
void MergeSort(int* a, int n)
{
	int* tmp =(int *) malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc failed");
		return;
	}
	//不可以自己递归,因为每次都要开辟新的空间
	_MergerSort(a, tmp, 0, n - 1);
	free(tmp);
}

 【算法】排序——归并排序和计数排序,算法,算法,排序算法,数据结构,c语言

递归实现排序确实优点难理解,大家可以根据我画的图和代码结合起来自己多多画图理解。


非递归实现归并排序

上篇文章的快速排序我们可以使用栈数据结构来实现,但是归并排序我们很难用栈数据结构来实现,普通的方法实现起来也不难,递归是将一整个数组分成若干数组(极限情况下每一个数字是一个数组)来实现分治,最后归并。我们逆向着来,根据控制数组的下标来直接实现归并

【算法】排序——归并排序和计数排序,算法,算法,排序算法,数据结构,c语言

非递归实现代码

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc failed");
		return;
	}
	
	int gap = 1;
	while (gap < n)
	{
		//11归并 22归并 44归并
		for (int i = 0; i < n;i=i+2*gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			int index = i;
            //防止越界,防止只能排序个数为2的倍数
            //当begin2大于等于数组个数时end2一定越界了
			if (begin2 >= n)
			{
				break;
			}
			if (end2 >= n)
			{
				end2 = n - 1;
			}
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[index++] = a[begin1++];
				}
				else
				{
					tmp[index++] = a[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				tmp[index++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[index++] = a[begin2++];
			}
			memcpy(a + i, tmp + i, (end2-i+1) * sizeof(int));
		}
		gap *= 2;
	}
	free(tmp);
}

在对数组进行操作时我们一定要注意越界问题,下面是解决上面问题的图解。 

【算法】排序——归并排序和计数排序,算法,算法,排序算法,数据结构,c语言

因此当end2越界时但begin2没越界时我们将end2调到n-1的位置时候就可以了。

归并排序的特性总结:
1. 归并的缺点在于需要O(N)的空间复杂度,归并排序的思考更多的是解决在磁盘中的外排序题。
2. 时间复杂度:O(N*logN)
3. 空间复杂度:O(N)
4. 稳定性:稳定


计数排序

思想:计数排序又称为鸽巢原理,是对哈希直接定址法的变形应用。

操作步骤:
1. 统计相同元素出现次数
2. 根据统计的结果将序列回收到原来的序列中

【算法】排序——归并排序和计数排序,算法,算法,排序算法,数据结构,c语言

开辟一个新的数组利用数组下标统计原数组中每个数出现的次数,因为时从小到大统计的因此直接将每个数字放在原数组中即可,如果原数组全是大数据呢?开辟空间的大小是个问题,因此我们先遍历数组找到最大值和最小值做差作为我们开辟空间大小的基准,每个数的代表下标=数组元素-最小值。

【算法】排序——归并排序和计数排序,算法,算法,排序算法,数据结构,c语言

实现代码

void CoutSort(int* a, int n)
{
	int max = a[0];
	int min = a[0];
	//遍历数组求出最大值
	for (int i = 0; i < n; i++)
	{
		if (max < a[i])
		{
			max = a[i];
		}
		if (min > a[i])
		{
			min = a[i];
		}
	}
	//根据最大值和最小值的差值开辟空间
	int range = max - min+1;
	int* cout = (int*)malloc(sizeof(int) * range);
	if (cout == NULL)
	{
		perror("malloc failed");
		return;
	}
	//将开辟的空间所有值置为0
	memset(cout, 0, sizeof(int) * range);
	for (int i = 0; i < n; i++)
	{
		//计数
		//防止数值过大
		cout[a[i] - min]++;
		//3 4 5 6 7 8 9 10
		//0 1 2 3 4 5 6 7
		//2 1 1 2 1 1 2 1
	}
	int j = 0;
	for (int i = 0; i < range; i++)
	{
		while (cout[i]--)
		{
			a[j++] = i + min;
		}
	}
}

 计数排序的特性总结:
1. 计数排序在数据范围集中时,效率很高,但是适用范围及场景有限。
2. 时间复杂度:O(MAX(N,范围))
3. 空间复杂度:O(范围)


排序算法复杂度及稳定性分析

【算法】排序——归并排序和计数排序,算法,算法,排序算法,数据结构,c语言

【算法】排序——归并排序和计数排序,算法,算法,排序算法,数据结构,c语言


 经典的几大排序本片文章就彻底完结了,大家可以根据这三篇文章对排序有新的认识。希望大家阅读完可以有所收获,同时也感谢各位看官的三连支持。文章有问题可以直接留言,我一定及时认真的修改。 文章来源地址https://www.toymoban.com/news/detail-715483.html

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

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

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

相关文章

  • 【数据结构】——归并排序和计数排序

    🌇个人主页:_麦麦_ 📚今日名言:繁华落尽,我心中仍有花落的声音。一朵,一朵,在无人的山间轻轻飘落。——席慕蓉《桐花》 目录 一、前言 二、正文 1.归并排序 1.1 基本思想 1.2【递归版】具体实现  1.3【递归版】代码部分  1.4【非递归版】具体实现  1.5【非递归版】

    2023年04月15日
    浏览(48)
  • 【数据结构】排序之归并排序与计数排序

    个人主页 : zxctsclrjjjcph 文章封面来自:艺术家–贤海林 如有转载请先通知 在前面的文章中介绍了 插入排序和交换排序,今天来分享的是归并排序和计数排序。 话不多说,正文开始。 归并排序既是内排序也是外排序。 基本思想: 归并排序(MERGE-SORT)是建立在归并操作上的

    2024年01月17日
    浏览(49)
  • 数据结构——归并排序和计数排序的介绍

    归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治(Divide andConquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列。即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

    2024年02月11日
    浏览(58)
  • 【数据结构初阶】八大排序(三)——归并排序&&计数排序

    大家好我是沐曦希💕 往期博客:【数据结构初阶】八大排序(一)——希尔排序堆排序直接插入排序直接选择排序 【数据结构初阶】八大排序(二)——快速排序冒泡排序 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一

    2024年02月03日
    浏览(133)
  • 【数据结构】归并排序的两种实现方式与计数排序

    前言:在前面我们讲了各种常见的排序,今天我们就来对排序部分收个尾,再来对归并排序通过递归和非递归的方法进行实现,与对计数排序进行简单的学习。 💖 博主CSDN主页:卫卫卫的个人主页 💞 👉 专栏分类:数据结构 👈 💯代码仓库:卫卫周大胖的学习日记💫 💪关注博

    2024年01月18日
    浏览(50)
  • 【数据结构】一文带你全面了解排序(下)——冒泡排序、快速排序、归并排序、计数排序

      目录 一、常见排序算法的实现   1.1 交换排序 1.1.1 基本思想 1.1.2 冒泡排序  1.1.3 快速排序 1.2 归并排序 1.3 非比较排序 二、排序算法复杂度及稳定性分析  人总得为过去的懒惰而付出点代价! 1.1.1 基本思想 基本思想:所谓交换,就是根据序列中两个记录键值的比较结

    2024年02月16日
    浏览(50)
  • 数据结构:直接插入排序,希尔排序,选择排序,堆排序,冒泡排序,快速排序,归并排序,计数排序(C实现)

    个人主页 : 个人主页 个人专栏 : 《数据结构》 《C语言》 排序:使一串数据,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 插入排序的思路:把待排序数组,逐个插入到已经排好序的有序数组中,直到所有待排序数组插入完成,的到一个新的有序

    2024年02月11日
    浏览(54)
  • 【数据结构与算法】归并排序详解:归并排序算法,归并排序非递归实现

    归并排序是一种经典的排序算法,它使用了分治法的思想。下面是归并排序的算法思想: 递归地将数组划分成较小的子数组,直到每个子数组的长度为1或者0。 将相邻的子数组合并,形成更大的已排序的数组,直到最终得到一个完全排序的数组。 归并排序的过程可以分为三

    2024年01月22日
    浏览(70)
  • 数据结构——排序算法——归并排序

    在第二个列表向第一个列表逐个插入的过程中,由于第二个列表已经有序,所以后续插入的元素一定不会在前面插入的元素之前。在逐个插入的过程中,每次插入时,只需要从上次插入的位置开始,继续向后寻找插入位置即可。这样一来,我们最多只需要将两个有序数组遍历

    2024年02月09日
    浏览(47)
  • 数据结构和算法笔记4:排序算法-归并排序

    归并排序算法完全遵循分治模式。直观上其操作如下: 分解:分解待排序的n个元素的序列成各具n/2个元素的两个子序列。 解决:使用归并排序递归地排序两个子序列。 合并:合并两个已排序的子序列以产生已排序的答案。 我们直接来看例子理解算法的过程,下面是要排序

    2024年01月21日
    浏览(64)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包