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

简介

基数排序是这样一种排序算法，可以从低位（个位）开始，根据个位数排序一次，然后根据十位数排序，再根据百位数进行排序……最终完成整个数组的排序

对于十进制数而言，每一位只会是 0~9 这十个数字，通常使用桶排序（计数排序）来完成每一位数的排序

此种排序一般适用于记录的关键字为整数类型的情况。所有对于字符串和文字排序不适合

排序图解

排序原理

主要思想是将整数按位数划分，准备 10 个桶，代表 0 – 9，根据整数个位数字的数值将元素放入对应的桶中，之后按照输入赋值到原序列中，依次对十位、百位等进行同样的操作，最终就完成了排序的操作

代码实现

public void radixSort(int[] arr){

    if (arr == null || arr.length == 0) {
        return;
    }

    //获取数组中最大的数的位数
    int max = arr[0];
    for (int j : arr) {
        if (j > max) {
            max = j;
        }
    }
    int maxLength = (max + "").length();

    //定义一个二维数组，表示10个桶，每个桶就是一个一维数组
    //为了防止在放入数的时候，数据溢出，则每个一维数组（桶）大小定为arr.length
    int[][] bucket = new int[10][arr.length];
    //定义一个记录每个桶中元素的个数
    int[] bucketElementCounts = new int[10];

    //循环处理位数
    for (int k = 0,n = 1; k < maxLength; k++,n *=10) {
        //对数组中的每个数的个位数进行处理
        for (int value : arr) {
            //取每个数的k位数（k为 0 表示个位数，1 表示十位数，依次类推）
            int digitOfElement = value / n % 10;
            //将个位数作为bucket的位置，bucketElementCount中的个数作为桶的下标，把arr[i]放到桶对应的位置
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = value;
            bucketElementCounts[digitOfElement]++;
        }

        //按照桶的顺序，一维数组的下标依次取出数据，放入原数组
        int index = 0;
        for (int i = 0; i < bucket.length; i++) {
            if (bucketElementCounts[i] != 0) {
                //循环第i个桶，将第i个一维数组中的元素放入原数组中
                for (int j = 0; j < bucketElementCounts[i]; j++) {
                    //取出元素放到arr
                    arr[index] = bucket[i][j];
                    index++;
                }

                //将第i个桶中元素的个数置为 0
                bucketElementCounts[i] = 0;
            }
        }
    }
}

算法稳定性

基数排序是稳定的

算法稳定性：假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的