三种线性排序之计数排序

一.算法简介

       通过统计元素出现的次数进而排序，需要一个辅助数组，大小是最大元素值（想想计数的过程），为了更好的理解计数排序，我们先来想象一下如果一个数组里所有元素都是非负整数(数组下标是整数)，而且都在0-max(由于内存的原因，这个值要小一些)以内，那对于数组里每个元素来说，如果我能知道数组里有多少项小于或等于该元素，就能准确地给出该元素在排序后的数组的位置。

        局限性：通过上面的描述可以看出需要非负整数，而且最大值要在能开数组范围内。

        算法是稳定的，算法第五步从后往前保证了稳定性，希望读者细细体会……

二.算法描述

1. 求得元素最大值max(看算法实现过程，体会这个方法需要独立，就是说max需要事先确定)
2. 开辅助数组c[max]和res[原数组大小]并全部初始化为0
3. 计数：统计元素出现次数并把次数放在c数组的以该元素为下标的位置
4. 针对c数组从下标1开始，前一项加上后一项并存入后一项获得数组里有多少项小于或等于该元素
5. 对原数组中的每一个元素temp存入res[c[temp]-1](减一是因为下标从0开始)并更新c[temp]--(不必担心小于0，因为一旦等于0就不会再减小了，因为原数组没该元素了)

三.算法的Java实现

public class CountSort {
    public static void main(String[] args) {
        int[] a = { 3, 1, 6, 0, 3, 0, 1, 5, 3, 6 };
        int max = getMax(a);
        arrDisplay(a, "Before mySort:");
        a = mySort(a, max);
        arrDisplay(a, "After  mySort:");
    }

    public static int[] mySort(int[] a, int max) {
        int[] res = new int[a.length];
        int[] c = new int[max + 1];
        for (int i = 0; i < res.length; i++) {
            res[i] = 0;
        }
        for (int i = 0; i < c.length; i++) {
            c[i] = 0;
        }
        int temp = 0;
        /*统计元素出现次数并把次数放在c数组的以该元素为下标的位置
        不可以在这个遍历过程中取最大值，就是说getMax不可合并，因为需要事先c的大小；
        能否直接开为整形最大值，这样不可能，超内存*/
        for (int i = 0; i < a.length; i++) {
            temp = a[i];
            c[temp] = c[temp] + 1;
        }
        for (int i = 1; i < c.length; i++) {
            c[i] = c[i] + c[i - 1];
        }
        
        //必须从后往前，这样保证了稳定性
        for (int i = a.length - 1; i >= 0; i--) {
            temp = a[i];
            res[c[temp] - 1] = temp;
            //不必担心小于0，因为一旦等于0就不会再减小了，因为原数组没该元素了
            c[temp] = c[temp] - 1;
        }
        return res;
    }

    public static int getMax(int[] a) {
        int max = a[0];
        for (int i = 1; i < a.length; i++) {
            if (a[i] > max)
                max = a[i];
        }
        return max;
    }

    public static void arrDisplay(int[] a, String str) {    
        System.out.println(str);
        for (int i = 0; i < a.length; i++)
            System.out.print(a[i] + " ");
        System.out.println();
    }
}