排序算法9 - 计数排序

计数排序（Counting Sort）

  计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward提出，通过计数将时间复杂度降到了O(N)。

  它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。

  当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)), 如归并排序，堆排序）

  其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

算法思想

  将输入的数据值转化为键存储在额外开辟的数组空间中，如图：

  你会发现一个主要问题，空间的浪费，上图中[0, 7, 8]元素不存在也为其开辟了空间，当然这点空间可以忽略不计，

  假设我们有组数据 [100, 101, 102, 101, 109, 105, 105]；我们应该开辟多大的空间，因为最大值是109，从0开始需要开辟110个空间吗？那太浪费了。

  那么到底应该开辟多大的空间，怎么计算？

    这时可以使用相对映射元素的位置

      1. 计算出计数数组的大小。（待排序数组中的最大值-最小值+1，max=109, min=100 , max-min+1=10）

      2. 实现相对映射。（公式：i = number - min；如例中的109，109在计数数组中的位置就是 i = 109 - 100 = 9）

      3. 把数据还原至待排序数组中。（公式：number = i + min）

动图演示

代码实现

#include<stdio.h>
#include<stdlib.h>
 
void CountingSort(int* arr, int n)
{
	int max = arr[0];
	int min = arr[0];
	int i, j, countLen;
	int *count;

	// 遍历找出最大值和最小值
	for (i=0; i<n; i++)
	{
		if (arr[i]>max)
		{
			max = arr[i];
		}
 
		if (arr[i]<min)
		{
			min = arr[i];
		}
	}
 
	// 动态开辟计数数组的空间
	countLen = max - min + 1; // 计算计数数组范围
	count = (int*)calloc(countLen, sizeof(int)); 
	if (count==NULL) 
	{
		perror("calloc");
		return;
	}
 
	// 统计数组arr每个元素出现的次数
	for (i=0; i<n; i++)
	{
		count[arr[i] - min]++;
	}

	j = 0;
	for (i=0; i<countLen; i++)
	{
		while (count[i]) // 判断count数组中该元素是否有计数。
		{
			arr[j++] = i+min; // 如果有就把该元素的下标值反映射至数组arr
			count[i]--;
		}
	}

	// 释放动态开辟的空间
	free(count);
	count = NULL;
}
 
// 打印
void Print(int* arr, int n)
{
	int i;

	for (i=0; i<n; i++)
	{
		printf("%d ", arr[i]);
	}
}
 
int main()
{
	int arr[] = {-1, 2, 7, 6, 1, 3, -3, 4, -2, 5};
	int arrLen = sizeof(arr) / sizeof(arr[0]);

	CountingSort(arr, arrLen); // 计数排序
	Print(arr, arrLen); // 打印

	return 0;
}