排序算法 —— 计数排序

1.计数排序的思想

2.计数排序的实现

3.计数排序的分析

时间复杂度

空间复杂度

稳定性

优点

缺点

1.计数排序的思想

顾名思义，计数排序就是通过计数的方式来排序，其基本思想为：

开辟一个计数数组，统计每个数出现的次数。
遍历计数数组，将计数数组中的值依次填入待排序序列中，覆盖原来的值之后，排序便完成了。

2.计数排序的实现

计数排序最核心的两步就是统计数据出现的次数和根据数据出现的次数排序。

但是统计数据出现的次数时，我们需要开辟新的数组空间，并且将待排序的元素直接映射计数数组的下标，让对应的位置++，表示统计出了数据出现的次数；这样计数有个缺陷就是，当待排序的序列中的元素取值的最小值不是0时，比如：100、156、195、 163 、 101 、 200。此时我们应该开辟多大的空间呢？应该如何计数呢？

如果我们直接开辟201个空间，也让元素的值作为数组下标，这样直接计数会有空间的浪费，所以，我们可以统计出最小元素和最大元素，最小元素和最大元素的差值就是要开辟的空间的大小，然后我们可以采用间接映射的方式，将待排序元素的数值映射到计数数组对应的位置上。如下图所示：

代码如下：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void CountSort(int* a, int n)
{
	// 统计出最小元素和最大元素 
	int min = a[0], max = a[0];
	int i = 0;
	for (i = 0; i < n; i++)
	{
		if (a[i] < min)
			min = a[i];

		if (a[i] > max)
			max = a[i];
	}
	
	// 计算出取值范围 
	int range = max - min + 1;
	int* count = (int*)malloc(sizeof(int) * range);
	if (count == NULL)
	{
		perror("malloc fail");
		return;
	}
	// 将开辟的空间全部初始化为0 
	memset(count, 0, sizeof(int) * range);

	// 统计数据出现次数
	for (i = 0; i < n; i++)
	{
		count[a[i] - min]++;
	}

	// 排序
	int j = 0;
	for (i = 0; i < range; i++)
	{
		while (count[i]--)
		{
			a[j++] = i + min;
		}
	}
}

int main()
{
	int nums[] = {4,5,8,7,9,6,2,1,3,0};
	
	CountSort(nums,10);
	
	int i = 0;
	while(i < sizeof(nums) / sizeof(int))
	{
		printf("%d ",nums[i]);	
		i++;
	}
	
	return 0;
}