个人主页：https://chengang.plus/

文章将会同步到个人微信公众号：Android部落格

1.1 描述

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

• 设置一个定量的数组当作空桶；
• 遍历输入数据，并且把数据一个一个放到对应的桶里去；
• 对每个不是空的桶进行排序；
• 从不是空的桶里把排好序的数据拼接起来。

1.2 代码

private static int getIndex(int value,int min){
    return (value - min) / 10;
}

public static void bucketSort(){
    int minValue = numbers[0];
    int maxValue = numbers[0];
    for(int index = 0;index < size;index++){
        if(numbers[index] < minValue){
            minValue = numbers[index];
        }
        if(numbers[index1] > maxValue){
            maxValue = numbers[index1];
        }
    }
    int bucketSize = maxValue / 10 - minValue / 10 + 1;
    int bucketIndex = 0;
    List<List<Integer>> bucketList = new ArrayList<List<Integer>>();
    for(int x = 0; x < bucketSize;x++){
        bucketList.add(new ArrayList<Integer>());
    }
    for(int index2 = 0;index2 < size;index2++){
        int tempIndex = getIndex(numbers[index2],minValue);
        List<Integer> tempList  = bucketList.get(tempIndex);
        tempList.add(numbers[index2]);  
    }
    int originIndex = 0;
    for(int index3 = 0;index3 < bucketSize;index3++){
        List<Integer> tempList = bucketList.get(index3);
        if(tempList == null || tempList.size() == 0){
            continue;
        }
        int tempSize = tempList.size();
        for(int i = 0;i < tempSize - 1;i++){
            for(int j = 0;j < tempSize - i - 1;j++){
                if(tempList.get(j) > tempList.get(j + 1)){
                    int tempValue = tempList.get(j);
                    tempList.set(j,tempList.get(j + 1));
                    tempList.set(j + 1,tempValue);
                }
            }
        }
        for(int index4 = 0;index4 < tempSize;index4++){
            numbers[originIndex++] = tempList.get(index4);
        }
    }
}

public static void main(String []args) {
    bucketSort();
    for(int value : numbers){
        System.out.println("count value is:" + value);
    }
}

1.3 总结

• 先遍历计算出最大值和最小值；
• 最大值的高位减去最小值的高位，就是桶的数量，比如最大值为999，最小值为100，那么桶的数量等于99 - 10 + 1 = 90个，也就是每100个数设置10个桶；
• 将元素值减去最小值，除以10，等于元素所属桶的序号；
• 每一个桶内部再次使用排序算法排序，达到总体有序。

示意图如下：

桶排序.jpg