计数排序面试题

001什么是计数排序？

1）计数排序不是一个基于比较的排序算法。它是用一个数组来统计每种数字出现的次数，然后按照大小顺序将其依次放回原数组。但是计数排序有一个很严重的问题，就是其只能对整数进行排序，一旦遇到字符串时，就无能为力了。

2 ）算法图解

第一步：找出原始数组【0,2,5,3,7,9,10,3,7,6】中元素值最大的，记为max=10。

第二步：创建一个计数数组count，数组长度是max值加1，其元素默认值都为0。

第三步：遍历原始数组中的元素，以原始数组中的元素作为计数数组count的索引，以原始数组中的元素出现次数作为计数数组count的元素值。下图可以得到原始数组【0,2,5,3,7,9,10,3,7,6】中元素0出现1次，元素2出现1次，元素3出现2次，元素5出现1次，元素6出现1次，元素7出现2次，元素9出现1次，元素10出现1次。

第四步：遍历计数数组count，找出其中元素值大于0的元素，将其对应的索引作为元素值填充到结果数组result中去，每处理一次，计数数组count中的该元素值减1，直到该元素值不大于0，依次处理计数数组count中剩下的元素。

002计数排序的代码实现？

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;
        }
    }
}