十大经典排序算法之基数排序

基数排序

基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数

基数排序的发明可以追溯到 1887 年赫尔曼·何乐礼在打孔卡片制表机 (Tabulation Machine)上的贡献。

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

这三种排序算法都利用了桶的概念,但对桶的使用方法上有明显差异:

  1. 基数排序:根据键值的每位数字来分配桶;
  2. 计数排序:每个桶只存储单一键值;
  3. 桶排序:每个桶存储一定范围的数值;

LSD 基数排序动图演示

计数排序

java code 1

import org.junit.Test;
import java.util.Arrays;

/**
 * 基数排序
 * 考虑负数的情况还可以参考: https://code.i-harness.com/zh-CN/q/e98fa9
 */

public class RadixSort {

    @Test
    public void sort() throws Exception {
        int[] sourceArray = new int[]{389, 254, 1344};
        // 对 arr 进行拷贝,不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        int maxDigit = getMaxDigit(arr);
        radixSort(arr, maxDigit);
    }

    /**
     * 获取最高位数
     */
    private int getMaxDigit(int[] arr) {
        int maxValue = getMaxValue(arr);
        return getNumLenght(maxValue);
    }

    private int getMaxValue(int[] arr) {
        int maxValue = arr[0];
        for (int value : arr) {
            if (maxValue < value) {
                maxValue = value;
            }
        }
        return maxValue;
    }

    protected int getNumLenght(long num) {
        if (num == 0) {
            return 1;
        }
        int lenght = 0;
        for (long temp = num; temp != 0; temp /= 10) {
            lenght++;
        }
        return lenght;
    }

    private int[] radixSort(int[] arr, int maxDigit) {
        int mod = 10;
        int dev = 1;

        for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
            // 考虑负数的情况,这里扩展一倍队列数,其中 [0-9]对应负数,[10-19]对应正数 (bucket + 10)
            int[][] counter = new int[mod * 2][0];

            for (int j = 0; j < arr.length; j++) {
                int bucket = ((arr[j] % mod) / dev) + mod;
                counter[bucket] = arrayAppend(counter[bucket], arr[j]);
            }

            int pos = 0;
            for (int[] bucket : counter) {
                for (int value : bucket) {
                    arr[pos++] = value;
                }
            }
        }

        return arr;
    }

    /**
     * 自动扩容,并保存数据
     *
     * @param arr
     * @param value
     */
    private int[] arrayAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }
}

java code 2

import java.util.Arrays;

/**
 * 基数排序
 */
public class RadixSort2 {
    public static void main(String[] args) {
        System.out.println("123456/1:" + (123456 / 1));
        System.out.println("123456/10:" + (123456 / 10));
        System.out.println("123456/100:" + (123456 / 100));
        System.out.println("123456/1000:" + (123456 / 1000));
        Integer[] array = new Integer[]{1200, 292, 121, 72, 233, 44, 12};
        radixSort(array, 10, 4);
        System.out.println("排序后的数组:");
        print(array);
    }

    /*
     * 基数排序  稳定的排序算法
     * array    代表数组
     * radix    代表基数
     * d        代表排序元素的位数
     */
    public static void radixSort(Integer[] array, int radix, int d) {
        // 临时数组    
        Integer[] tempArray = new Integer[array.length];
        // count用于记录待排序元素的信息,用来表示该位是i的数的个数    
        Integer[] count = new Integer[radix];

        int rate = 1;
        for (int i = 0; i < d; i++) {
            //重置count数组,开始统计下一个关键字    
            Arrays.fill(count, 0);
            //将array中的元素完全复制到tempArray数组中
            System.arraycopy(array, 0, tempArray, 0, array.length);

            //计算每个待排序数据的子关键字
            for (int j = 0; j < array.length; j++) {
                int subKey = (tempArray[j] / rate) % radix;
                count[subKey]++;
            }
            print(count);

            //统计count数组的前j位(包含j)共有多少个数  
            for (int j = 1; j < radix; j++) {
                count[j] = count[j] + count[j - 1];
                System.out.print(count[j]);
            }
            System.out.println();

            //按子关键字对指定的数据进行排序 ,因为开始是从前往后放,现在从后忘前读取,保证基数排序的稳定性  
            for (int m = array.length - 1; m >= 0; m--) {
                int subKey = (tempArray[m] / rate) % radix;
                array[--count[subKey]] = tempArray[m]; //插入到第--count[subKey]位,因为数组下标从0开始
                print(count);
                print(array);
            }
            rate *= radix;//前进一位    
            System.out.print("第" + (i + 1) + "次:");
            print(array);
        }
    }

    //输出数组===============  
    public static void print(Integer[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + "\t");
        }
        System.out.println();
    }
}  

两个问题:

为什么要从低位开始向高位排序?

如果要从高位排序, 那么次高位的排序会影响高位已经排好的大小关系. 在数学中, 数位越高,数位值对数的大小的影响就越大.从低位开始排序,就是对这种影响的排序. 数位按照影响力从低到高的顺序排序, 数位影响力相同则比较数位值.

为什么同一数位的排序子程序要使用稳定排序?

稳定排序的意思是指, 待排序相同元素之间的相对前后关系,在各次排序中不会改变.比如实例中具有十位数字5的两个数字58和356, 在十位排序之前356在58之前,在十位排序之后, 356依然在58之前.

稳定排序能保证,上一次的排序成果被保留,十位数的排序过程能保留个位数的排序成果,百位数的排序过程能保留十位数的排序成果.