計數(shù)排序

基本思想：不通過比較，計下每個元素的出現(xiàn)次數(shù)，統(tǒng)計小于這個元素的個數(shù)N，將其放在N位。例如{7，6，2，4，2，3}這個序列，有5個小于7的元素，那么7在排序后應(yīng)該放在數(shù)組的第5位。

讀完這段話，讀者可能會有疑問，不通過比較怎么統(tǒng)計小于這個元素的個數(shù)？請繼續(xù)向下看

注意！??！計數(shù)排序?qū)⒁判虻臄?shù)組是有限制的
1.只能是整形數(shù)組。
2.數(shù)組元素必須都大于0。
3.計數(shù)排序是一種拿空間換時間的排序算法。

具體步驟如下

1.一個待排序的數(shù)組array

待排序數(shù)組

1.選出數(shù)組的最大值k，創(chuàng)建一個k+1長度的數(shù)組countArray，將所有元素初始化為0（Java數(shù)組默認是0，節(jié)省操作），countArray的數(shù)組下標代表array數(shù)組中的元素值，而countArray中的元素值代表的是array中每一個元素的出現(xiàn)次數(shù)。
疑問：為什么要創(chuàng)建k+1的長度？因為array中最大值為k，那么array的值一定是0-k之間，而且countArray的下標代表array中的數(shù)，0-k之間有k+1個數(shù)。

新創(chuàng)建的數(shù)組

2.遍歷array數(shù)組，統(tǒng)計每個元素的出現(xiàn)次數(shù)。例如array[0]是7，那么countArray[7]++，因為countArray的下標代表array中的數(shù)。統(tǒng)計完如下圖。

統(tǒng)計結(jié)束

3.對countArray進行循環(huán)，對每一個元素countArray[i] = countArray[i] + countArray[i-1]，目的是統(tǒng)計每一個元素前面有多少個小于它的元素。例如下圖countArray[3]的值是4，那么就代表在array中有4-1個元素小于3。

統(tǒng)計

4.復制array數(shù)組存到temp中，循環(huán)temp，將temp中i位置的的元素放到array中的--countArray[temp[i]]位置。也就是array[--countArray[temp[i]]] = temp[i]。
例如i等于1時，temp[i]值時6，countArray[6]的值是6，也就代表6這個元素前面有5個元素小于小于它，那么6應(yīng)該放在array數(shù)組的第6個位置也就是array[5]。

完整代碼如下

/**
 * 計數(shù)排序
 * Created by ShouJingGuo on 2018/3/24.
 */
public class CountSort{

    public static void countSort(int[] array){
        int max = getMax(array);                        //獲取數(shù)組的最大值，數(shù)組所有值都在0 - max之間
        int[] countArray = new int[max + 1];            //創(chuàng)建一個max+1大小的數(shù)組用于表示從0 - max所有數(shù)字的重復次數(shù)
        int[] resultArray = new int[array.length];
        System.arraycopy(array, 0, resultArray, 0, array.length);      //用于存儲排好序的數(shù)組
        for(int i = 0; i < array.length; i++){              //循環(huán)array數(shù)組
            countArray[array[i]]++;                         //因為countArray的下標代表array中的數(shù)字，而值代表array中元素的出現(xiàn)次數(shù)，所以countArray[array[i]]++
        }
        for(int i = 1; i < countArray.length; i++){
            countArray[i] = countArray[i] + countArray[i - 1];      //將countArray中的每一個元素變成與前一個元素相加的和
        }
        for(int i = 0; i < resultArray.length ; i++){
            array[--countArray[resultArray[i]]] = resultArray[i];                //從array的最后一位開始依次放入resultArray中，放入的位置是 --countArray[array[i]]
        }
    }

    private static int getMax(int[] array){
        int max = array[0];
        for(int i = 0; i < array.length; i++){
            if(array[i] < 0){
                throw new RuntimeException("數(shù)組中有數(shù)小于0");
            }
            if(max < array[i]){
                max = array[i];
            }
        }
        return max;
    }

    public static void main(String[] args) {
        int arr[] = {10,5,11,68,20,41,0,24,25,4,7,94,15,5,44,66};
        CountSort.countSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}