非比较排序------计数排序

目录

导入

计数排序的思想

计数排序的思想优化

计数排序代码实现

---

导入

之前我的博客介绍了七大排序：插入、希尔、选择、堆排、冒泡、快排、归并。

插入排序、希尔排序_SAKURAjinx的博客-CSDN博客

选择排序、堆排序、冒泡排序_SAKURAjinx的博客-CSDN博客

快速排序详解_SAKURAjinx的博客-CSDN博客

归并排序详解（递归+非递归）_SAKURAjinx的博客-CSDN博客

这些都是常见的比较类排序，所谓的比较类，就是按数的大小（如果是字符按ASCLL值）进行比较后排序。今天介绍的计数排序则是非比较排序，也就是说它不需要比较数的大小。

计数排序的思想

对于一个数组 {6,1,5,9,3,8,1,6,2,1} ，它的最大值是9，最小值是1，创建一个0~9 的数组，将原数组里的数按出现的次数放到对应的位置上。新的数组里各个位置上就是对应的数出现的次数。

然后按对应的数及它出现的次数将数组还原（出现0次的去掉），就排好了，这就是计数排序。

 上图是计数排序的大致过程。

计数排序的思想优化

有人在其中发现了一些问题，比如如果数字太大的话，那开辟的数组就很大，这种方法就变得很不方便了。

确实，假设数组的值是这样的：1000,1500,2000,2500,1000,1000,2000   。这样数组最大值是2500，数组个数却只有7个，难道要开辟 0~2,500的数组吗？太过于浪费了。

于是，又有人想出了解决方法：既然嫌开辟的数组太大，又要包含最大最小数，那我们可以开辟一个相对于最大最小数的合理数组。如这里最小为1000，最大是2500，那么不用下标从0开始开辟，可以将1000转化为0,2500转化为1500，这样就节省了1000个int大小的空间。

这种方式叫相对映射，而一开始介绍的叫绝对映射。

这样调整一下创建新数组的下标，就可以较好的解决数过大的问题。

而且，相对映射还有一个优点：如果有负数的话，绝对映射就不行了，数组下标为负，越界了。

此时只能用相对映射。

计数排序代码实现

void CountSort(int* a, int n)
{
	int max = a[0], min = a[0];
	for (int i = 0; i < n; ++i)
	{
		if (a[i] > max)
		{
			max = a[i];
		}
		if (a[i] < min)
		{
			min = a[i];
		}
	}
	int range = max - min + 1;
	/*int* tmp = (int*)malloc(sizeof(int) * range);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}
	memset(tmp, 0, sizeof(int) * range);*/
 
	int* tmp = (int*)calloc(range,sizeof(int));
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}
 
	for (int i = 0; i < n; ++i)
	{
		tmp[a[i] - min]++;
	}
 
	int j = 0;
	for (int i = 0; i < range; ++i)
	{
		while (tmp[i]--)
		{
			a[j++] = i + min;
		}
	}
	free(tmp);
	tmp = NULL;
}
int main()
{
	int a[] = { 5,9,6,1,0,3,4,-8,-1,0,2 };
	int n = sizeof(a) / sizeof(a[0]);
	CountSort(a, n);
	for (int i = 0; i < n; ++i)
	{
		printf("%d ", a[i]);
	}
	return 0;
}

计数排序的时间复杂度是O(N+range），空间复杂度是O(range)。

不难发现，当N >= range 时，时间复杂度很小，计数排序很快；

当range远大于N（数比较分散），那么计数排序就比较慢了。

附送一张表