思想

当我们需要对一组数据进行排序时，常规的排序算法（如快速排序、归并排序等）通常是比较排序，即通过比较元素之间的大小关系来进行排序。但有时候我们需要对一组数据按照它们的“数字位”进行排序，此时比较排序并不是最优的选择，这时候基数排序就显得非常有效了。

基数排序是一种非比较排序算法，它根据元素的每个“数字位”（比如个位、十位、百位等）来对元素进行排序，其基本思想是将整数按照位数切割成不同的数字，然后按照每个位数分别比较。具体来说，基数排序可以分为以下几个步骤：

1. 将数组中的元素按照个位数进行排序：从个位数开始，对于每个数字，将其放到对应的桶中；
2. 将桶中的元素按照顺序依次取出来，组成新的数组；
3. 将新数组中的元素按照十位数进行排序：从十位数开始，对于每个数字，将其放到对应的桶中；
4. 将桶中的元素按照顺序依次取出来，组成新的数组；
5. 依次按照百位数、千位数......对元素进行排序，直到所有位数均已考虑。

基数排序的时间复杂度为O(d(n+k))，其中d表示位数，k表示每一位可能的取值范围，n表示元素的数量。显然，基数排序的效率与每一位的取值范围k有关，当k较小而d较大时，基数排序的效率会很高。

代码

public class RadixSort {

    public static void radixSort(int[] arr) {
    
        // 先找到最大的数
        int max = Integer.MIN_VALUE;
        for (int num : arr) {
            max = Math.max(num, max);
        }
        // 最大数的位数
        int maxDigit = 0;
        while (max != 0) {
            ++maxDigit;
            max = max / 10;
        }
        // 10进制
        int base = 10;
        // 新建桶, 0-9是10个数所以有10个桶
        int[][] buckets = new int[base][arr.length];

        // 有多少位就进行多少轮的排序
        for (int i = 0; i < maxDigit; i++) {
            int[] bucketsCount = new int[base];
            for (int num : arr) {
                // 获取位数上的值,这里要是不会写也可以用字符串
                int digit = (int) (num / Math.pow(base, i)) % 10;
                // 把它加到桶里
                buckets[digit][bucketsCount[digit]] = num;
                // 这一位的数的数量++，即记录每个桶中元素的数量，为了之后还能把它放回原数组
                bucketsCount[digit]++;
            }
            int index = 0;
            // 有几个桶循环几次
            for (int j = 0; j < bucketsCount.length; ++j) {
                // 一个桶里有多少个数
                int count = bucketsCount[j];
                // 如果桶里有数
                if (count != 0) {
                    // 取出放回原数组，这里其实已经排序了，因为桶本身是有序的
                    for (int k = 0; k < count; ++k) {
                        arr[index++] = buckets[j][k];
                    }
                }
            }
        }
    }

    public static void main(String... args) {
        int[] arr = { 170, 45, 75, 90, 802, 24, 2, 66 };
        RadixSort.radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

过程举例

假设有一个整数数组 arr = [170, 45, 75, 90, 802, 24, 2, 66]，要求使用基数排序将其从小到大排序。

首先，我们需要确定最大数的位数。最大数是802，所以它的位数是3。因此，我们需要进行3轮排序。

第一轮排序按个位数排序。遍历整个数组，把每个数按个位数的值分到0-9的桶中。比如170、90、802在个位数上分别是0、0、2，它们分别被放入编号为0、2的桶中。排序后的数组为[170, 90, 802, 2, 24, 45, 75, 66]。

第二轮排序按十位数排序。遍历排序后的数组，把每个数按十位数的值分到0-9的桶中。比如802、45、75在十位数上分别是0、4、7，它们分别被放入编号为0、4、7的桶中。排序后的数组为[2, 24, 45, 66, 75, 170, 802, 90]。

第三轮排序按百位数排序。遍历排序后的数组，把每个数按百位数的值分到0-9的桶中。比如2、45、66在百位数上分别是0、4、6，它们分别被放入编号为0、4、6的桶中。排序后的数组为[2, 24, 45, 66, 75, 90, 170, 802]。

最终得到的就是一个有序数组了。