数据结构——lesson13排序之计数排序

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

💞💞 前言

hello hello~ ,这里是大耳朵土土垚~💖💖 ,欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹
数据结构——lesson13排序之计数排序,数据结构,排序合集,数据结构,排序算法,算法,c语言

💥个人主页:大耳朵土土垚的博客
💥 所属专栏:数据结构学习笔记 、排序算法合集
💥对于数据结构顺序表、链表、堆以及排序有疑问的都可以在上面数据结构专栏和排序合集专栏进行学习哦~ 有问题可以写在评论区或者私信我哦~

前面我们学习过七种排序——直接插入排序、希尔排序、直接选择排序、堆排序、冒泡排序、快速排序和归并排序,它们都是通过两数之间进行比较来排序的,今天我们就来学习非比较排序中的计数排序🥳🥳🥳

1.计数排序

基本思想

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

我们这里利用malloc开辟一个数组来统计相同元素出现的次数,用该数字下标表示相同元素,下标对应的值来统计次数
图示如下:
数据结构——lesson13排序之计数排序,数据结构,排序合集,数据结构,排序算法,算法,c语言

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
void CountSort(int* a, int n)
{
	//开辟数组
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}
	//将tmp数组的值初始化为0
	for (int i = 0; i < n; i++)
	{
		tmp[i] = 0;
	}
	//遍历a
	for (int i = 0; i < n; i++)
	{
		//tmp下标对应值要++
		tmp[a[i]]++;
	}

	//拷贝回元素组a
	int j = 0;//记录a下标
	for (int i = 0; i < n; i++)
	{
		while (tmp[i]--)
		{
			a[j++] = i;
		}
	}
	free(tmp);
}
int main()
{
	int a[] = { 1,3,3,9,7,5,8,7,6 };
	printf("排序前:");

	for (int i = 0; i < 9; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");

	CountSort(a, 9);
	printf("排序后:");
	for (int i = 0; i < 9; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	return 0;
}

结果如下:
数据结构——lesson13排序之计数排序,数据结构,排序合集,数据结构,排序算法,算法,c语言

🥲我们仔细观察发现我们开辟tmp数组的大小是n:
int* tmp = (int*)malloc(sizeof(int) * n);
而数组a里面有九个数,也就是tmp大小为9,下标最大也就是8,那么当a中出现比8大的数9时应该怎么计数呢?就不可以计数了,所以出错了;
✨✨那么我们应该开辟多大的数组呢?应该根据什么来开辟才可以呢?
根据a数组最大最小值之差来开辟好像可以,a数组之间的范围就可以作为判断标准;但是这次我们得考虑得全面一点,如果a数组是这样得:a[] = {45,43,36,50,49,44,47}这些呢?那我们岂不是要开辟50个int大小的数组才可以有这么大的下标,如果是考虑范围就是最大50-最小36 = 14,更不可以了;
✨✨解决办法
利用相对值,还是开辟最大-最小的范围大小数组,然后最后拷贝数据的时候让下标+最小的数即可:
代码如下:

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
void CountSort(int* a, int n)
{
	//求a数组最大最小差的范围
	int small = a[0];
	int big = a[0];
	for (int i = 1; i < n; i++)
	{
		//求最大值
		if (a[i] > big)
		{
			big = a[i];
		}
		//求最小值
		if (a[i] < small)
		{
			small = a[i];
		}
	}
	//范围
	
	int gap = big - small;
	//比如0~4,差就是4,但是对应开辟的大小得是5,0~4有五个数
	//开辟数组
	int* tmp = (int*)malloc(sizeof(int) * (gap+1));
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}
	//将tmp数组的值初始化为0
	for (int i = 0; i < gap+1; i++)
	{
		tmp[i] = 0;
	}
	//遍历a
	for (int i = 0; i < n; i++)
	{
		//tmp下标(a数组对应值-small)对应值要++
		tmp[a[i]-small]++;
	}

	//拷贝回元素组a,记得+samll
	int j = 0;//记录a下标
	for (int i = 0; i < gap+1; i++)
	{
		while (tmp[i]--)
		{
			a[j++] = i + small;
		}
	}
	free(tmp);
}
int main()
{
	int a[] = { 1,3,3,9,7,5,8,7,6 };
	printf("排序前:");

	for (int i = 0; i < 9; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");

	CountSort(a, 9);
	printf("排序后:");
	for (int i = 0; i < 9; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	return 0;
}

结果如下:
数据结构——lesson13排序之计数排序,数据结构,排序合集,数据结构,排序算法,算法,c语言
当int a[] = {45,43,36,50,49,44,47}时结果如下:
数据结构——lesson13排序之计数排序,数据结构,排序合集,数据结构,排序算法,算法,c语言
可以发现,计数排序成功啦~🥳🥳🥳

2.计数排序复杂度分析

2.1空间复杂度

我们根据上述代码实现可以知道计数排序开辟了大小为gap的数组,而gap对应的是最大与最小值的差也就是范围,所以其空间复杂度应该为O(gap);

2.2时间复杂度

时间复杂度:
①求数组a最大最小值时遍历了一遍数组a,次数为n;
②初始化tmp数组为0时遍历了数组tmp,次数为gap;
③统计下标出现次数时遍历数组a,次数为n;
④拷贝回原数组时,遍历了数组tmp,次数为gap;
所以其时间复杂度应该是n+gap+n+gap,简化为O(n+gap);

3.计数排序缺陷分析

前面我们学习的七大排序,时间复杂度最好也要O(n*logn);
而计数排序时间复杂度却可以达到O(n);
俗话说金无足赤,人无完人;计数排序达到这么好的时间复杂度其对应的缺陷也是非常明显的:
💥 缺陷1:依赖数据范围,适用于范围集中的数组
💥 缺陷2:只能用于整形(因为使用数组下标来统计)
所以计数排序使用的条件是非常苛刻的

4.结语

计数排序的关键在于理解并运用它的思想, 以上就是计数排序的介绍与实现啦~,完结撒花 ~🥳🥳🎉🎉🎉文章来源地址https://www.toymoban.com/news/detail-846712.html

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

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

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

相关文章

  • 【Java数据结构与算法】Day2-高级排序(希尔、归并、快速、计数)

    ✅作者简介:热爱Java后端开发的一名学习者,大家可以跟我一起讨论各种问题喔。 🍎个人主页:Hhzzy99 🍊个人信条:坚持就是胜利! 💞当前专栏:【Java数据结构与算法】 🥭本文内容:Java数据结构与算法中的比较高级的排序,希尔排序、归并排序、快速排序、计数排序

    2024年02月02日
    浏览(64)
  • 数据结构——lesson12排序之归并排序

    hello hello~ ,这里是大耳朵土土垚~💖💖 ,欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹 💥 个人主页:大耳朵土土垚的博客 💥 所属专栏:数据结构学习笔记 、排序算法合集 💥对于数据结构顺序表、链表、堆以及排序有疑问的都可以在上面数据结构专栏和排序合集专栏进行

    2024年04月10日
    浏览(59)
  • 数据结构——lesson11排序之快速排序

    hello hello~ ,这里是大耳朵土土垚~💖💖 ,欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹 💥 个人主页:大耳朵土土垚的博客 💥 所属专栏:数据结构学习笔记 、排序算法合集 💥对于数据结构顺序表、链表、堆以及排序有疑问的都可以在上面数据结构专栏和排序合集专栏进行

    2024年04月16日
    浏览(64)
  • 【数据结构与算法】万字剖析八大排序(直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序、计数排序)

    初窥直接插入排序我们先来看一张动图: 由动图我们可以分析出直接插入排序是从 第二个数据开始遍历 ,与 前面的数据进行比较 如果小于 则让前面的数据向前移动 自己接着向前面的数据比较 直到比较到 大于等于自己的 数据或者 没有数据能进行比较 时停止 插入当前的位

    2023年04月13日
    浏览(67)
  • 【数据结构】——归并排序和计数排序

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

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

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

    2024年01月17日
    浏览(49)
  • 【数据结构】-计数排序

    🎇作者:小树苗渴望变成参天大树 🎉 作者宣言:认真写好每一篇博客 🎊作者gitee:link 如 果 你 喜 欢 作 者 的 文 章 ,就 给 作 者 点 点 关 注 吧! 答应大家的计数排序今天它来了,这也是一个非常巧妙的方法,不通过比较元素的大小就可以排序出来,通过用另一个人数组

    2023年04月17日
    浏览(33)
  • 数据结构——归并排序和计数排序的介绍

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

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

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

    2024年02月03日
    浏览(133)
  • 【C语言】数据结构——排序三(归并与计数排序)

    💗个人主页💗 ⭐个人专栏——数据结构学习⭐ 💫点击关注🤩一起学习C语言💯💫 我们在前面学习了排序,包括直接插入排序,希尔排序,选择排序,堆排序,冒泡排序和快排。 今天我们来讲一讲归并排序和计数排序。 关注博主或是订阅专栏,掌握第一消息。 归并排序的

    2024年01月19日
    浏览(58)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包