1、介绍

桶排序比我想象的简单的多，也不是什么非常神奇的思路。借用维基百科的一句话：将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。那么他的流程很简单了：

1、设置一个定量的数组当作空桶子。
2、寻访序列，并且把项目一个一个放到对应的桶子去。
3、对每个不是空的桶子进行排序。
4、从不是空的桶子里把项目再放回原来的序列中。

2、代码

package com.example.demo.easy;

import java.util.ArrayList;
import java.util.List;

/**
 * @author xushu
 * @create 2020/6/11 3:07 下午
 * @desc
 */
public class BucketSort {

    private int indexFor(int a, int min, int step) {
        return (a - min) / step;
    }

    public void bucketSort(int[] arr) {

        int max = arr[0], min = arr[0];
        for (int a : arr) {
            if (max < a)
                max = a;
            if (min > a)
                min = a;
        }
        // 該值也可根據實際情況選擇
        int bucketNum = max / 10 - min / 10 + 1;
        List buckList = new ArrayList<List<Integer>>();
        // create bucket
        for (int i = 1; i <= bucketNum; i++) {
            buckList.add(new ArrayList<Integer>());
        }
        // push into the bucket
        for (int i = 0; i < arr.length; i++) {
            int index = indexFor(arr[i], min, 10);
            ((ArrayList<Integer>) buckList.get(index)).add(arr[i]);
        }
        ArrayList<Integer> bucket = null;
        int index = 0;
        for (int i = 0; i < bucketNum; i++) {
            bucket = (ArrayList<Integer>) buckList.get(i);
            insertSort(bucket);
            for (int k : bucket) {
                arr[index++] = k;
            }
        }

    }

    // 把桶內元素插入排序（桶内的排序各种排序算法都可以）
    private void insertSort(List<Integer> bucket) {
        for (int i = 1; i < bucket.size(); i++) {
            int temp = bucket.get(i);
            int j = i - 1;
            for (; j >= 0 && bucket.get(j) > temp; j--) {
                bucket.set(j + 1, bucket.get(j));
            }
            bucket.set(j + 1, temp);
        }
    }

    public static void main(String[] args) {
        int[] array = new int[]{9, 11, 2, 5, 4, 8};
        BucketSort sort = new BucketSort();
        sort.bucketSort(array);
        for (int i : array) {
            System.out.println(i);
        }
    }
}