八大排序（五）：基数排序

蔚落 2022-05-25 03:53 124阅读 0赞

源码地址：  
[https://github.com/TimePickerWang/aimed-at-offer/blob/master/java%E6%BA%90%E7%A0%81/Sort.java][https_github.com_TimePickerWang_aimed-at-offer_blob_master_java_E6_BA_90_E7_A0_81_Sort.java]

基数排序与之前的其他七种排序方法都不同，它不需要比较关键字的大小。  
以下用一个例子来讲解基数排序：  
假设有一个数组：73, 22, 93, 43, 55, 14, 28, 65, 39, 81  
1.首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中，分配结果如下图：  
![这里写图片描述][70]

2.将这些桶子中的数值按顺序重新串接起来，成为数列：81, 22, 73, 93, 43, 14, 55, 65, 28, 39

3.接着再按顺序进行一次分配，这次是根据十位数来分配，这次的分配结果如下图：  
![这里写图片描述][70 1]

4.接下来将这些桶子中的数值重新串接起来，成为数列：14, 22, 28, 39, 43, 55, 65, 73, 81, 93。这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。

基数排序的代码如下（以下代码是基于最低位优先LSD（Least Significant Digit first）实现的，即从最低位开始，另外还有MSD方式，从最高位开始分组，在位数较多的情况下，使用MSD的效率会更高）：

基数排序：

// 基数排序（LSD）,参数d为数组中最大数的位数,123是3位,1234是4位
        public int[] radixSort(int[] array, int d) {
            int[] tempArray = new int[array.length];
            System.arraycopy(array, 0, tempArray, 0, array.length);
    
            int m = 1;// 表示当前操作的从右往左数第几位
            int n = 1;
            int[][] bucket = new int[10][array.length];// 10个桶
            int[] numInBucket = new int[10]; // 每个桶内元素个数
            while (m <= d) {
                int k = 0;
                for (int i = 0; i < tempArray.length; i++) {
                    int value = (tempArray[i] / n) % 10;
                    bucket[value][numInBucket[value]] = tempArray[i];
                    numInBucket[value]++;
                }
                for (int i = 0; i < 10; i++) {
                    if (numInBucket[i] != 0) {
                        for (int j = 0; j < numInBucket[i]; j++) {
                            tempArray[k] = bucket[i][j];
                            k++;
                        }
                    }
                    numInBucket[i] = 0;
                }
                m++;
                n *= 10;
            }
            return tempArray;
        }

基数排序的时间复杂度是O(d(n+radix))。其中，n为待排序数据个数，d为关键码即数据的位数，关键码的取值范围为radix。则一趟分配时间复杂度为O(n)，一趟收集时间复杂度为O(radix)，共进行d趟分配和收集。

ref:  
[基数排序][Link 1]

[https_github.com_TimePickerWang_aimed-at-offer_blob_master_java_E6_BA_90_E7_A0_81_Sort.java]: https://github.com/TimePickerWang/aimed-at-offer/blob/master/java%E6%BA%90%E7%A0%81/Sort.java
[70]: /images/20220525/6f829b3cacae4cc09e77b411419b84e3.png
[70 1]: /images/20220525/ffe4a0c1ac5f441886ad7dc769880911.png
[Link 1]: https://baike.baidu.com/item/%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F/7875498?fr=aladdin