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

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

2 ）算法圖解

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

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

第三步：遍歷原始數(shù)組中的元素，以原始數(shù)組中的元素作為計(jì)數(shù)數(shù)組count的索引，以原始數(shù)組中的元素出現(xiàn)次數(shù)作為計(jì)數(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次。

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

002計(jì)數(shù)排序的代碼實(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;
        }
    }
}