在介绍计数排序之前，我们先讨论一个问题，为什么比较排序排序下界为Ω(nlgn)。
介绍一下比较排序和线性排序的概念
- 比较排序：各个元素的次序基于输入元素间的比较。下界为Ω(nlgn)。
- 线性排序：用非比较的操作来确定元素的顺序。
1.决策树模型
比较排序可以抽象地视为决策树，表示某排序算法对输入元素的所有比较。下图为插入排序对于三个元素的输入序列上的决策树：
对于n个元素，排序结果有n!种排列，对应与决策树上的每一个叶子。
最坏情况下的下界
从决策树中我们可以看出：从根结点到任意一个可到达叶结点之间的最长简单路径的长度，表示的就是对应排序算法中最坏情况下的比较次数。因此，一个比较排序算法中的最坏情况的排序次数就等于决策树的高度。并且，当决策树中所有排列都是以可到达的叶结点的形式出现时，该决策树高度的下界也就是比较排序算法运行时间的下界。下面我们正式给出证明。
考虑一棵高度为h，具有l个可到达叶结点的决策树。它对应一个对n个元素进行的比较排序。因为输入数据有n！种可能的排列都是叶结点，所以n！≤l。由于在一棵高度为h的二叉树中，叶结点的数目不多于2^h，我们得到：
n! ≤ l ≤ 2^h，
两边取对数得：
h ≥ lg(n!) = Ω(nlgn)
２.计数排序定义：
计数排序假设n个输入元素都是位于[0, k]之间的整数。
基本思想为对于每一个输入元素x，确定出小于x的元素个数，然后直接将x放置>在最终数组的位置上。
下面给出算法的伪代码描述：
其中数组A[1n]是待排序数组；数组B[1n]用来存放已排好序的元素。C[0~k]用来存放上面所说的统计数（具体的说C[i]就表示在数组A中，小于或等于i的元素的总个数）。
下面这幅图描述的是对序列{2,5,3,0,2,3,0,3}排序的过程：
３.java代码实现
/**
* @Project: 10.dataStructure
* @description:
* @author: sunkang
* @create: 2018-08-22 09:47
* @ModificationHistory who when What
**/
public class CountingSort {
/**
*计数排序的核心思想：
* 利用了数组的下标的值来表示数组的值，利用数组的值来表示值的个数问题，最终数组的值进行累计来表示排序好数组的序号，
* 因为下标的值是有序的，需要一个值来记录值出现的次数，于是就用值来记录序号
*
* @param A A表示即将排序的数组
* @param k k表示数组的最大的值，数组的一般值范围从0到k范围内
*/
public int[] countingSort(int[] A,int k){
//1.创建C数组来存储 数组A的每个值出现的次数
int[] C = new int[k + 1];//加上1
//2.对C数组进行初始化
for(int i= 0;i<C.length;i++){
C[i]=0;
}
//3. 统计数组A的值出现的次数存储到数组C中，C中的下标对应B的值，C的值对应着数组A的出现的次数
// A[j]表示数组A的值， C[A[j]]表示C的下标为A[j]的一个位置的值
for(int j=0;j<A.length;j++){
C[A[j]]=C[A[j]]+1;
}
//4. 对C中的值进行累加 A[i]=A[i]+A[i-1]
for(int i=1;i<C.length;i++){
C[i]= C[i]+C[i-1];
}
//5.初始化B来保存排序后的结果
int[] B = new int[A.length];
//6.把C数组的值转换到输出数组B中
// C[A[i]]表示A[i]的累加的个数的位置，此时应该 对应B的下标为 C[A[i]]-1
for(int i=0;i<A.length;i++){
B[C[A[i]]-1]=A[i];
C[A[i]]= C[A[i]] -1;
}
return B;
}
public void display(int[] arr){
for(int in:arr){
System.out.print(in+",");
}
System.out.println();
}
public static void main(String[] args) {
int[] A = new int[]{2,5,3,0,2,3,0,3};
CountingSort countingSort = new CountingSort();
int[] B = countingSort.countingSort(A,9);
countingSort.display(B);
}
}
４.计数排序算法分析
我们现在来分析计数排序的时间代价。
在伪代码中，第2到3行时间代价θ(k)；第4到5行时间为θ(n)；第7到8行时间为θ(k)，第10到12行时间为θ(n)。因此，总的运行时间是θ(k+n)。当k= O(n)时，运行时间为θ(n)。
可以看出，计数排序的下界优于我们上面论证的比较排序算法的下界时间Ω(nlgn)。这是因为计数排序并不是比较排序算法。事实上，在代码中从未出现比较某两个元素大小的代码。相反，计数排序是使用输入元素的实际值来确定其在数组中的位置。此时，比较排序算法的模型对计数排序不再适用。
