import java.util.ArrayList;

/**
 * 类说明：桶排序
 */
public class BucketSort {
    /**
     *
     * @param array
     * @param bucketSize BucketSize，作为每个桶所能放置多少个不同数值
     *                   （例如当BucketSize==5时，该桶可以存放｛1,2,3,4,5｝这几种数字，
     *                   但是容量不限，即可以存放100个3）；
     * @return
     */
    public static ArrayList<Integer> sort(ArrayList<Integer> array, int bucketSize) {
        if (array == null || array.size() < 2)
            return array;
        int max = array.get(0), min = array.get(0);
        // 找到最大值最小值
        for (int i = 0; i < array.size(); i++) {
            if (array.get(i) > max)
                max = array.get(i);
            if (array.get(i) < min)
                min = array.get(i);
        }
        /*获得桶的数量*/
        int bucketCount = (max - min) / bucketSize + 1;
        /*构建桶*/
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount);
        ArrayList<Integer> resultArr = new ArrayList<>();
        for (int i = 0; i < bucketCount; i++) {
            bucketArr.add(new ArrayList<Integer>());
        }
        /*将原始数组中的数据分配到桶中*/
        for (int i = 0; i < array.size(); i++) {
            bucketArr.get((array.get(i) - min) / bucketSize).add(array.get(i));
        }
        /*看看桶中数据的分布*/
        for (int i = 0; i < bucketArr.size(); i++) {
            System.out.print("第"+i+"个桶包含数据：");
            PrintArray.printObject(bucketArr.get(i));
        }
        for (int i = 0; i < bucketCount; i++) {
            if (bucketSize == 1) {
                for (int j = 0; j < bucketArr.get(i).size(); j++)
                    resultArr.add(bucketArr.get(i).get(j));
            } else {
                if (bucketCount == 1)
                    bucketSize--;
                /*对桶中的数据再次用桶进行排序*/
                ArrayList<Integer> temp = sort(bucketArr.get(i), bucketSize);
                for (int j = 0; j < temp.size(); j++)
                    resultArr.add(temp.get(j));
            }
        }
        return resultArr;
    }
}

基数排序

常见的数据元素一般是由若干位组成的，比如字符串由若干字符组成，整数由若干位0~9数字组成。基数排序按照从右往左的顺序，依次将每一位都当做一次关键字，然后按照该关键字对数组排序，同时每一轮排序都基于上轮排序后的结果；当我们将所有的位排序后，整个数组就达到有序状态。比如对于数字2985，从右往左就是先以个位为关键字进行排序，然后是十位、百位、千位，总共需要四轮。基数排序不是基于比较的算法。

基数是什么意思？对于十进制整数，每一位都只可能是0~9中的某一个，总共10种可能。那10就是它的基，同理二进制数字的基为2；对于字符串，如果它使用的是8位的扩展ASCII字符集，那么它的基就是256。

基数排序 vs 计数排序 vs 桶排序

基数排序有两种方法：
1、MSD 从高位开始进行排序
2、LSD 从低位开始进行排序

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
1、基数排序：根据键值的每位数字来分配桶
2、计数排序：每个桶只存储单一键值
3、桶排序：每个桶存储一定范围的数值

import java.util.ArrayList;

/**
 * 类说明：基数排序
 */
public class RadixSort {
    public static int[] sort(int[] array) {
        if (array == null || array.length < 2)
            return array;
        /*找出最大数*/
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            max = Math.max(max, array[i]);
        }

        /*先算出最大数的位数*/
        int maxDigit = 0;
        while (max != 0) {
            max /= 10;
            maxDigit++;
        }
        int mod = 10, div = 1;
        /*构建桶*/
        ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i < 10; i++)
            bucketList.add(new ArrayList<Integer>());
        /*按照从右往左的顺序，依次将每一位都当做一次关键字，然后按照该关键字对数组排序，
        每一轮排序都基于上轮排序后的结果*/
        for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
            /*遍历原始数组，投入桶中*/
            for (int j = 0; j < array.length; j++) {
                int num = (array[j] % mod) / div;
                bucketList.get(num).add(array[j]);
            }
            /*桶中的数据写回原始数组，清除桶，准备下一轮的排序*/
            int index = 0;
            for (int j = 0; j < bucketList.size(); j++) {
                for (int k = 0; k < bucketList.get(j).size(); k++)
                    array[index++] = bucketList.get(j).get(k);
                bucketList.get(j).clear();
            }
        }
        return array;
    }
}