001什么是計數(shù)排序？

1）計數(shù)排序不是一個基于比較的排序算法。它是用一個數(shù)組來統(tǒng)計每種數(shù)字出現(xiàn)的次數(shù)，然后按照大小順序?qū)⑵湟来畏呕卦瓟?shù)組。但是計數(shù)排序有一個很嚴重的問題，就是其只能對整數(shù)進行排序，一旦遇到字符串時，就無能為力了。

2 ）算法圖解

第一步：找出原始數(shù)組【0,2,5,3,7,9,10,3,7,6】中元素值最大的，記為max=10。

第二步：創(chuàng)建一個計數(shù)數(shù)組count，數(shù)組長度是max值加1，其元素默認值都為0。

第三步：遍歷原始數(shù)組中的元素，以原始數(shù)組中的元素作為計數(shù)數(shù)組count的索引，以原始數(shù)組中的元素出現(xiàn)次數(shù)作為計數(shù)數(shù)組count的元素值。下圖可以得到原始數(shù)組【0,2,5,3,7,9,10,3,7,6】中元素0出現(xiàn)1次，元素2出現(xiàn)1次，元素3出現(xiàn)2次，元素5出現(xiàn)1次，元素6出現(xiàn)1次，元素7出現(xiàn)2次，元素9出現(xiàn)1次，元素10出現(xiàn)1次。

第四步：遍歷計數(shù)數(shù)組count，找出其中元素值大于0的元素，將其對應(yīng)的索引作為元素值填充到結(jié)果數(shù)組result中去，每處理一次，計數(shù)數(shù)組count中的該元素值減1，直到該元素值不大于0，依次處理計數(shù)數(shù)組count中剩下的元素。

002計數(shù)排序的代碼實現(xiàn)？

public static void countSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < arr.length; i++) {
        max = Math.max(max, arr[i]);
    }
    int[] bucket = new int[max + 1];
    for (int i = 0; i < arr.length; i++) {
        bucket[arr[i]]++;
    }
    int i = 0;
    for (int j = 0; j < bucket.length; j++) {
        while (bucket[j]-- > 0) {
            arr[i++] = j;
        }
    }
}