【排序算法】—— 计数排序

一、简介

        计数排序，顾名思义就是记录数据出现的次数进行排序，时间复杂度为O(N+K)，空间复杂度为O(N)。只能用于整型，对于比较集中重复率比较高数据更为适用。

二、排序原理

比如对接下来这些数进行排序

                arr[11] = { 8,6,4,1,6,2,9,6,2,4,3 }

        定义一个tmp用来记录数字出现的次数，那么tmp的长度可以设为需要排序的最大的数字加1，因为我们要做的是用下标来表示这个数，

                比如tmp[6]=2，其中下标6表示6这个数字，2表示出现两次

        所以得先把tmp初始化为0，然后进行计数，比如第一个数字为1那么就在1下标位置加1，以此类推遍历完数组arr。然后根据每个数出现的个数依次赋值给原数组arr。

#include<stdio.h>
int main()
{
	int arr[11] = { 8,6,4,1,6,2,9,6,2,4,3 };
	int tmp[10] = { 0 };
	for (int i = 0; i < 11; i++)
		tmp[arr[i]]++;
	for (int i = 0, j = 0; i < 10; i++)
	{
		while (tmp[i]--)
		{
			arr[j++] = i;
		}
	}
	for (int i = 0; i < 11; i++)
		printf("%d ", arr[i]);
	return 0;
}

        那这些数据比较大呢，比如下面这组数据
                {1004 1003 1000 1015 1004 1004 1012 1006 1003 1014}
        需要申请长为1015的数组大小吗？
        其实并不需要，只需要申请长度为16的数组进行记录就行，记录的时候先减去1000，等赋值给原数组的时候再加回去就行。

        所以到底如何考虑申请多少空间呢？，其实只需要最大的值减最小的值再加1的长度的数组空间就够用了。同样在记录时先减去最小值，等赋值给原数组的时候再加回去。

void Sort(int* arr, int size)
{
	int max = arr[0], min = arr[0];
	for (int i = 0; i < size; i++)
	{
		if (max < arr[i])
			max = arr[i];
		if (min > arr[i])
			min = arr[i];
	}
	int ret = max - min + 1;
	int* tmp = (int*)calloc(ret,sizeof(int));
	assert(tmp);
	for (int i = 0; i < size; i++)
		tmp[arr[i]-min]++;
	for (int i = 0, j = 0; i < ret; i++)
	{
		while (tmp[i]--)
			arr[j++] = i + min;
	}
}

三、适用范围

        计数排序的缺点就是只能对整型数据进行排序，不能对字符，浮点形还有结构体类型进行排序。而且对于整形的排序他更适合的是最小值和最大值跨度比较小的数据，或者重复率比较高的数据。比如10个整数最小的是1最大的那个是100万。使用计数排序就会导致空间的开销很大，效率也比较低。

四、源码

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<time.h>
void Sort(int* arr, int size)
{
	int max = arr[0], min = arr[0];
	for (int i = 0; i < size; i++)
	{
		if (max < arr[i])
			max = arr[i];
		if (min > arr[i])
			min = arr[i];
	}
	int ret = max - min + 1;
	int* tmp = (int*)calloc(ret,sizeof(int));
	assert(tmp);
	for (int i = 0; i < size; i++)
		tmp[arr[i]-min]++;
	for (int i = 0, j = 0; i < ret; i++)
	{
		while (tmp[i]--)
			arr[j++] = i + min;
	}
}
int main()
{
	srand((unsigned int)time(NULL));
	int arr[15];
	for (int i = 0; i < 15; i++)
		arr[i] = rand() % 100 + 1;
	for (int i = 0; i < 15; i++)
		printf("%d ", arr[i]);
	Sort(arr, 15);
	printf("\n");
	for (int i = 0; i < 15; i++)
		printf("%d ", arr[i]);
	return 0;
}