计数排序

计数排序和原来说过的几个排序算法有一个特别大的不同之处：它是一个不基于比较的排序算法。不管是快排，归并，还是堆排，它们都难以突破NlogN的运行时间下限，而计数排序是一个线性时间级别的排序算法。对NlogN的突破凭借的就是不基于比较对元素进行排序，当然了，它也有很大的局限性，比如它只能对整数进行排序。总之，计数排序是一种对整数进行排序非常有效的排序算法。 计数排序的思想就是记录每个元素出现的次数，通过数组下标确定每个元素的先后关系。比如对数组A{2，5，6，8，4，2，5，4，8，6}进行排序

1. 找出最大元素2和最小元素8，确定元素范围。
2. 这个范围内最多有7（8-2+1）个元素，我们创建一个大小为8（7+1）的数组B来记录每个元素出现次数的信息。（为什么是8不是7？只是为了后边更容易操作，看后边就明白了）
3. 我们通过（A[i]-min+1）来计算每个元素在B中的个数信息位置。比如数组A中的2通过这个公式计算出为1，所以B[1]++。如此，数组B中下标1所在位置存放的信息就是数组A中通过这个公式计算出结果为1的元素的个数。这个过程之后，B中所存信息为：

1. 其实B中存放的就是每个元素出现的频率，下标1的位置记录的是2出现的频率，下边3处记录的是4出现的频率等等。我们通过这些频率信息可以计算出每个元素在排序之后在数组中的所在位置，首先我们进行这样一步 for (int i=0;i<BLength-1;i++){ B[i+1] +=B[i]; }
2. 如此之后，B中发生了这样的变化

这样，你可以发现，很巧妙的事发生了（这都取决于先去我们进行+1操作，空出了下标为零的位置）。现在B中下标A[i]-min处存放的信息代表的就是数组A中元素A[i]在新数组中的起始下标位置。通过一下代码我们就将所有排好序的元素信息存到了数组C中

        for (int i=0;i<n;i++){
            C[B[A[i]-min]++] = A[i];
        }

下面给出完整代码：

public class CountSort {
    public static void sort(int[] A){
        System.out.println("开始计数排序");
        int n = A.length;
        int max=0,min=0;
        for (int i=0;i<n;i++){
            if (A[i]>max)max=A[i];
            else if (A[i]<min)min = A[i];
        }
        int BLength = max-min+2;
        int[] B = new int[BLength];
        for (int i=0;i<n;i++){
            B[A[i]-min+1]++;
        }
        for (int i=0;i<BLength-1;i++){
            B[i+1] +=B[i];
        }
        int[] C = new int[n];
        for (int i=0;i<n;i++){
            C[B[A[i]-min]++] = A[i];
        }
        for (int i=0;i<n;i++){
            A[i] = C[i];
        }
    }
}