当前位置:网站首页>计数排序基础思路

计数排序基础思路

2022-07-06 22:04:00 就要 宅在家

所谓计数排序,也可以称为散列表 。也是一种简单的哈希桶。

今天,小编带大家来了解计数排序的基本思路。

一。基本思路

以升序为例,计数排序通俗来讲,分为三个步骤。

首先制作包含所有要排序的数的桶(相同的数制作一个桶即可)。

以2,3,6,1,4,1,2,3,7,6,8,9,5,4,3举例,就是制作9个桶,分别代表1,2,3,4,5,6,7,8,9。

第二步, 把所有的数依次放入桶中,桶中的数字代表该数有多少个。

 

第三步,从小到大依次把桶中的数全部拿出来。

排序完成。

小编希望大家自主实现一下代码,难度不大,相信自己!

ps:桶可以用数组下标代替。

 二。代码实现

void CountSort(int* a, int n)
{
	if (n <= 0) return;
	assert(a);
	int min = a[0], max = a[0];
	for (int i = 0; i < n; i++)//找出排序范围,减少空间浪费
	{
		if (min > a[i]) min = a[i];
		if (max < a[i]) max = a[i];
	}
	int* tmp = (int*)new int[max - min + 1], range = max - min + 1;
	memset(tmp, 0, sizeof(int) * range);
	for (int i = 0; i < n; i++)//入桶
	{
		tmp[a[i] - min]++;
	}
	int sub = 0;
	for (int i = 0; i < range; i++)//出桶
	{
		while (tmp[i]--)
		{
			a[sub++] = i + min;
		}
	}
}

三。问题

时间复杂度:O(n)

空间复杂度:O(n)

计数排序的作用范围狭小,浮点数、结构体之类都不适用,且范围越大空间复杂度和空间浪费就越明显。


三连支持一下吧  如有错误,敬请斧正 

原网站

版权声明
本文为[就要 宅在家]所创,转载请带上原文链接,感谢
https://blog.csdn.net/weixin_61857742/article/details/125613704

随机推荐