数据结构与算法——基数排序

基数排序属于“分配式排序”，又称“桶子法”，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用

算法要点

1. 基数排序属于桶排序的一种，所以桶排序的问题，在基数排序中依然存在
2. 获取序列中最大元素的位数
3. 依次根据序列中元素的个位数值，将元素放到0-9号十个桶中
4. 将十个桶中的元素一次放回到序列中
5. 继续根据每个元素的十位数值执行3步骤、4步骤，直到最大元素的位数
6. 每个桶中元素出桶的顺序为先进先出，与队列一致
7. 如果需要倒序，则将桶的位置颠倒，即先出9号桶的元素，后出0号桶的元素
8. 如果存在小数，则需要将小数全部转为整数才能排序
9. 如果存在负数，需要对负数求绝对值后，做倒序排序即可

动画演示

代码示例

package Sort;

public class Sort {
    /**
     * 基数排序
     *
     * @param data int[] 数据
     *
     * @return int[]
     **/
    public int[] radixSort(int[] data)
    {
        //获取最大的元素
        int max = data[0];
        for (int i = 0; i < data.length; i++) {
            if (data[i] > max) {
                max = data[i];
            }
        }
        int length = String.valueOf(max).length();

        //创建10个桶
        int[][] bucket = new int[10][data.length];
        int[] bucketIndex = new int[10];

        for (int place = 0; place < length; place++) {
            //入桶
            for (int i = 0; i < data.length; i++) {
                int value = (data[i] / (int) Math.pow(10, place)) % 10;
                bucket[value][bucketIndex[value]] = data[i];
                bucketIndex[value]++;
            }

            //出桶
            int index = 0;
            for (int b = 0; b < 10; b++) {
                if (bucketIndex[b] > 0) {
                    for (int i = 0; i < bucketIndex[b]; i++) {
                        data[index] = bucket[b][i];
                        index++;
                    }


                    //重置桶数据
                    bucketIndex[b] = 0;
                }
            }
        }

        return data;
    }
}