什么是计数排序？
计数排序（Counting Sort）是一种线性时间复杂度的排序算法，它通过统计数组中元素的出现次数，来确定每个元素在排序后的数组中的正确位置。
为了让大家更好地理解计数排序，这里展示其流程图：
计数排序的算法思路
- 统计相同元素出现的次数
- 根据统计的结果将序列回收到原来的序列中
上述流程提示了两个关键问题：
怎么将待排序的数组中的数字映射到计数的数组中？如何将计数数组中的元素回写到待排序的数组中，从而达到排序的效果？
绝对位置和相对位置
绝对位置：从数组首元素开始计算，剩余每个元素的位置都是按照数组首元素为参照的。
举个例子：数组 a：[1,5,6,8,9,7,3,2,0,4]，那对于计数数组来说用绝对位置就比较好，原因是这个待排序的数组 a 的元素最小值是为 0，最大值为 9，这里用绝对位置就比较舒服！
相对位置：先选取待排序数组中的最小值，以这个最小值为基准，从而给剩余的元素在计数数组中确定位置。
举个例子：数组 a：[101,100,106,103,105,104]，如果你这里硬是要使用绝对位置的话，你就要申请 106 个整型数据的空间，而我只有 6 个数据需要排序，开这么大的数据空间就有点得不偿失了。所以我们得采用相对位置，以数组 a 中的最小值（100）为基准，其余元素按照大小关系依次记录到计数数组中。
所以我建议大家使用相对位置来实现计数排序。
根据计数数组的信息来确认
我们创建了计数数组之后，我们要如何将信息还原到原序列中呢？
就根据我们设定的相对位置加上原本的最小值，就可以还原出待排序数组中元素的值。然后再建立一个循环，根据 count 数组中的位置元素的值决定循环这个相对位置加上原本的最小值多少次。
计数排序的代码
#include <stdio.h>
#include <stdlib.h>
// 计数排序 -- 是一个非比较的排序方式
// 通过统计数组中每个数字出现的次数，通过创建一个 count 数组记录这些数字对应出现的次数。（利用相对位置进行对应）
void CountSort(int* a, int n) {
// 1. 为获得相对位置，我们要想找到数组中的最小值还要找最大值
int min = a[0], max = a[0];
for (int i = 1; i < n; i++) {
if (a[i] < min) min = a[i];
(a[i] > max) max = a[i];
}
range = max - min + ;
* count = (*)(range, ());
(count == ) ;
( i = ; i < n; i++) {
count[a[i] - min]++;
}
index = ;
( i = ; i < range; i++) {
(count[i] > ) {
a[index++] = i + min;
count[i]--;
}
}
(count);
}
