什么时基数排序

基数排序（radix sort）又称“桶子法”（bucket sort）顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,以达到排序的作用,基数排序法是属于稳定性的排序,在某些时候,基数排序法的效率高于其它的稳定性排序法。

思路分析

基数排序是桶排序的扩展,它的基本思想是：将整数按位数切割成不同的数字,然后按每个位数分别比较。将所有待比较数值统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

代码实现

public class RadixSort {
    public static void main(String[] args) {
        int[] array = {72,538,627,56,332,453,312,4};
        radixSort(array);
    }

    /** * 基数排序 */
    public static void radixSort(int[] array){
        //初始化桶
        int[][] bucket = new int[10][array.length];
        //初始化一个数组用来存放指向每个桶中最大的元素的指针
        int[] bucketIndex = new int[10];
        //获取数组中最大的元素
        int max = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] > max){
                max = array[i];
            }
        }
        //获取最大元素的长度
        int maxLength = (max+"").length();
        //将数组中的元素按照指定规则放入到桶中
        for (int i = 0; i < maxLength; i++) {
            int div = (int)Math.pow(10,i);
            for (int j = 0; j < array.length; j++) {
                //获取元素的个位、十位、百位、千位...
                int element = (array[j]/div)%10;
                bucket[element][bucketIndex[element]] = array[j];
                bucketIndex[element]++;
            }
            int index = 0;
            for (int k = 0; k < bucketIndex.length; k++) {
                //桶中有元素
                if (bucketIndex[k] != 0){
                    //取出桶中元素
                    for (int j = 0; j < bucketIndex[k]; j++) {
                        array[index++] = bucket[k][j];
                    }
                }
                bucketIndex[k] = 0;
            }
            System.out.println("第"+(i+1)+"次排序的结果为"+Arrays.toString(array));
        }
    }
}

运行结果

第1次排序的结果为[72, 332, 312, 453, 4, 56, 627, 538]
第2次排序的结果为[4, 312, 627, 332, 538, 453, 56, 72]
第3次排序的结果为[4, 56, 72, 312, 332, 453, 538, 627]

Process finished with exit code 0

基数排序的优缺点

优点：

• 速度快且稳定

缺点：

• 如果有负数需要做另外的处理
• 基数排序利用的是时间换空间如果数据量非常庞大可能会导致栈溢出