计数排序基础思路

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

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

一。基本思路

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

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

以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)

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

---

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