计数排序

核心思想：哈希表的思想，确定元素在整个数组的排第几来确定它在最终排序数组中的位置。

计数排序示意图：

public class CountSort {

//数组数字在0 ~ k之间
public static int[] countSort(int[] a,int k){

    int[] elementCounter = new int[k+1];

    for(int i = 0;i<a.length;i++){
        elementCounter[a[i]]++;
    }

    //构造计数数组(即小于等于该元素的个数)
    for(int j = 1;j<elementCounter.length;j++){
        elementCounter[j] = elementCounter[j-1]+elementCounter[j];
    }


    int[] result = new int[a.length];

    //从原数组末尾开始遍历
    for(int i = a.length-1;i>=0;i--){
        result[elementCounter[a[i]]-1] = a[i];
        elementCounter[a[i]]--;
    }

    return result;
}

//优化方法只用了一个辅助数组
public static void optCountSort(int[] a,int k){
    int[] c = new int[k+1];
    for(int i = 0;i < a.length;i++){
        c[a[i]]++;
    }
    int z = 0;
    for(int j = 0;j <= k;j++){
        while (c[j] > 0){
            a[z++] = j;
            c[j]--;
        }
    }
}

public static void main(String[] args){
    int[] a = {6,5,4,3,2,1};
    int[] result = new int[a.length];
    result = CountSort.countSort(a,6);
    System.out.println(Arrays.toString(result));
}
}