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

计数排序基础思路

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;
		}
	}
}