1. 基数排序的思想
2. 桶
3. 核心算法实现
4. 排序总结

基数排序的思想

桶和用桶排序

1. 先确定每个元素的长度, 即总共需要用桶排几次. 这是控制最外层循环的数量.
2. 每一次排序中, 做如下事情:
   1. 按照某一个位置(一般是由权重低向权重高的部分排序), 将原来的元素分别放入按照大小排列好的桶中.
   2. 从每一个桶中拿出其中所有的元素, 依次放回到原来的数据结构中
   3. 清空桶, 准备下一次对另外一个位置使用桶排序

核心算法实现

public class RadixSort {
    /**
     * 内部类Buckets, 内部是一个ArrayList数组, 长度为10, 对应0-9的桶
     */
    private static class Buckets {

        private static int count = 10;
        private ArrayList<String>[] lists;

        //构造器, 创建一个数组, 其中装着10个桶
        @SuppressWarnings("unchecked")
        public Buckets() {
            lists = new ArrayList[count];
            for (int i = 0; i < count; i++) {
                lists[i] = new ArrayList<String>();
            }
        }

        /**
         * 清除所有的桶, 方便调用.
         */
        public void clearAll() {
            for (int i = 0; i < count; i++) {
                lists[i].clear();
            }
        }

        /**
         * 向编号为index的桶中放入target元素
         *
         * @param index  桶的编号
         * @param target 要放入桶中的元素
         */
        public void putIntoBucket(int index, String target) {
            lists[index].add(target);
        }

        /**
         * 显示桶中所有元素的内容
         */
        public void showBuckets() {
            for (int i = 0; i < count; i++) {
                System.out.println(i + "号桶的内容是:\t" + lists[i]);
            }
        }

        /**
         * 将桶中的元素按桶的顺序全部取出到数组中的方法
         *
         * @param array 要将桶中的元素按顺序装到的数组
         */
        public void getAllToArray(String[] array) {
            int startIndex = 0;


            for (int i = 0; i < count; i++) {
                if (lists[i].size() > 0) {
                    for (String s : lists[i]) {
                        array[startIndex] = s;
                        startIndex++;
                    }
                }
            }

            //装完之后清空桶
            this.clearAll();
        }

    }
}

/**
 * 基数排序的核心方法, 这里就不使用泛型了, 针对的是字符串形式的整数的数组
 *
 * @param array 要排序的数组
 */
private static void sort(String[] array) {
    //这里实际上应该检查一下字符串数组是否合法, 不过就不检查了, 直接来进行使用.

    if (array.length == 0 || array.length == 1) {
        System.out.println("数组无需排序");
        return;
    }

    Buckets buckets = new Buckets();

    //首先应该找到这个数组中最长的字符串
    int max = array[0].length();
    for (String s : array) {
        if (s.length() > max) {
            max = s.length();
        }
    }

    //此时的max就是总循环的次数
    for (int sortTimes = 0; sortTimes < max; sortTimes++) {
        //将数组中的每个字符串元素放入对应的桶中.
        //这里首先需要判断一下, 如果字符串的长度小于当前的sortTimes+1, 比如当前排到右边起第二位, 但是字符串只长1, 则将该位当做0.
        for (int i = 0; i < array.length; i++) {
            if (array[i].length() < sortTimes + 1) {
                buckets.putIntoBucket(0, array[i]);
            }
            //如果长度足够, 则对右侧起的sortTimes+1位进行排序
            else {
                //注意, 这里取到的是字符0-9char类型直接转换成的int, 是ACSII码, 还需要减去48才得到0-9
                int index = array[i].charAt(array[i].length() - 1 - sortTimes) - 48;
                //将元素放进对应index编号的桶里
                buckets.putIntoBucket(index, array[i]);
            }

        }

        //每次放完之后, 再将桶里的所有元素重新放回到数组中
        buckets.getAllToArray(array);

    }

}

private static void sort(String[] array, boolean reverse) {

    if (array.length == 0 || array.length == 1) {
        System.out.println("数组无需排序");
        return;
    }

    Buckets buckets = new Buckets();

    int max = array[0].length();

    for (String s : array) {
        if (s.length() > max) {
            max = s.length();
        }
    }

    for (int sortTimes = 0; sortTimes < max; sortTimes++) {

        for (int i = 0; i < array.length; i++) {
            if (array[i].length() < sortTimes + 1) {

                if (!reverse) {
                    buckets.putIntoBucket(0, array[i]);
                } else {
                    buckets.putIntoBucket(9, array[i]);
                }

            }
            else {
                int index = array[i].charAt(array[i].length() - 1 - sortTimes) - 48;

                if (!reverse) {
                    buckets.putIntoBucket(index, array[i]);
                } else {
                    buckets.putIntoBucket(9 - index, array[i]);
                }

            }

        }

        buckets.getAllToArray(array);
    }

    System.out.println("排序完成");

}

排序总结

1. 基本类型byte char short int long float double, java.util.Arrays.sort()使用快速排序, 还有重载方法, 可以传入两个索引,对两个索引之间的范围进行排序.
2. 对象类型, sort(Object[] a), 内部使用归并排序, 也支持再传入两个索引
3. 对象类型, sort(Object[] a, Comparator<? super T> c), 内部使用归并排序, 可以传入一个函数式接口对象, 也支持再传入两个索引.