数据结构与算法-算法篇：排序—计数排序（八）
数据结构与算法系列文章：数据结构与算法目录
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
计数排序的特征：
数组的元素都要是大于0的整数，计数排序不是比较排序，排序的速度快于任何比较排序算法。
由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。
所以计数排序是用来排序1到100之间的数字的最好的算法。
#######图解计数排序：
以[ 3，5，8，2，5，4 ]这组数字示例：
1、首先，我们找到这组数字中最大的数： 8，创建一个最大下标为 8 （数组中最大值+1）的空数组 arr 。
计数排序1.png
2、遍历数据，将数据的出现次数填入arr中对应的下标位置中。数组中的值为新创建数组的索引，对应内容为该值出现的次数。
计数排序2.png
3、遍历 arr ，将数据依次取出即可。
计数排序3.png
实现：
/// <summary>
/// 计数排序
/// </summary>
/// <param name="arr"></param>
public void CountingSort(int[] arr)
{
// 找出数组中最大的
int max = arr[0];
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] > max)
{
max = arr[i];
}
}
// 创建计数数组
int[] countArr = new int[max + 1];
// 开始计数
for (int i = 0; i < arr.Length; i++)
{
countArr[arr[i]]++;
}
// 排序
int sortedIndex = 0;
for (int i = 0; i < countArr.Length; i++)
{
while (countArr[i] > 0)
{
arr[sortedIndex++] = i;
countArr[i]--;
}
}
}
稳定排序：
有一个需求就是当对成绩进行排名次的时候，如何在原来排前面的人，排序后还是处于相同成绩的人的前面。
解题的思路是对 countArr 计数数组进行一个变形，来和名次挂钩，我们知道 countArr 存放的是分数的出现次数，那么其实我们可以算出每个分数的最大名次，就是将 countArr 中的每个元素顺序求和。
如下图：
稳定排序.png
变形意思：
我们把原数组[ 2，5，8，2，5，4 ]中的数据依次拿来去 countArr 去找，你会发现 3 这个数在 countArr[3] 中的值是 2 ，代表着排名第二名，（因为第一名是最小的 2，对吧？），5 这个数在 countArr[5] 中的值是 5 ，为什么是 5 呢？我们来数数，排序后的数组应该是[ 2，3，4，5，5，8 ]，5 的排名是第五名，那 4 的排名是第几名呢？对应 countArr[4] 的值是 3 ，第三名，5 的排名是第五名是因为 5 这个数有两个，自然占据了第 4 名和第 5 名。
所以我们取排名的时候应该特别注意，原数组中的数据要从右往左取，从 countArr 取出排名后要把 countArr 中的排名减 1 ，以便于再次取重复数据的时候排名往前一位。
实现：
/// <summary>
/// 计数排序
/// </summary>
/// <param name="arr"></param>
public void CountingSort(int[] arr)
{
// 找出数组中最大的
int max = arr[0];
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] > max)
{
max = arr[i];
}
}
// 创建计数数组
int[] countArr = new int[max + 1];
// 开始计数
for (int i = 0; i < arr.Length; i++)
{
countArr[arr[i]]++;
}
//顺序累加
for (int i = 1; i < max + 1; ++i)
{
countArr[i] = countArr[i - 1] + countArr[i];
}
//排序后的数组
int[] sortedArr = new int[arr.Length];
//排序
for (int i = arr.Length - 1; i >= 0; --i)
{
int value = arr[i];
sortedArr[countArr[value] - 1] = value;
countArr[value]--;
}
//将排序后的数据拷贝到原数组
for (int i = 0; i < arr.Length; ++i)
{
arr[i] = sortedArr[i];
}
}
计数局限性:
计数排序对数据范围偏差比较大的，比如数组 1，9999 ]，则会比较耗时；
如果是[ 9998，9999 ]这种虽然值大但是相差范围不大的数据我们可以使用偏移量解决，比如这两个数据，减掉 9997 后只需要申请一个 int[3] 的数组就可以进行计数。
所以，计数排序只适用于正整数并且取值范围相差不大的数组排序使用，如1到100之间，它的排序的速度是非常可观的。
