深入解析基数排序（Radix sort）——线性时间排序算法

缺乏、安全感 2021-12-19 01:57 256阅读 0赞

# 简介 #

众所周知，常见的排序算法例如快速排序，归并排序等都是基于比较的排序算法。正是因为它们基于比较的特性，这些算法在时间复杂度方面无法做到比`O(n*logn)`更好。关于这些排序算法的细节在本文中不做讨论，请参考作者之前的一篇文章[搜索和排序算法总结][Link 1]。

早在1887年，基数排序算法就已经由Herman Hollerith提出，用来解决编表机上的数字排序问题。它实际上是最早被提出的排序算法。

基数排序是一种非比较排序算法。这里所谓的非比较，指的是该算法并非基于比较数组中的每个元素来决定它们的相对位置。以整数排序为例，基数排序的工作原理大致是分别比较整数数组中每一个整数中每一位的数字，然后基于比较结果不断调整顺序。这样一来，如果我们从较低的数位（也就是个位）向较高的数位随着比较不断调整排排序，最终我们就会得到一个排序好的数组。同样的算法也可以运用到实数排序或者字符串排序中，因为这些元素也是由一位一位的数字或字符构成的。

**基数排序还有一个非常好的特性：基数排序是一种稳定排序算法（stable sort）。**

根据比较数位的顺序，基数排序可以分为从最高位开始排序(Most Significant Digit)和从最低位开始排序(Least Significant Digit)两种。

## 最低位起始基数排序法(LSD) ##

简而言之，最低位起始基数排序法流程如下：首先按数字（或字符串等其他元素）长短进行排序，较长的靠后，较短的靠前；接着对于长度一样的元素，再按位比较排序。这样排序过后我们就能得到正常的从小到大排序的数组。例如对于输入数字数组`[1, 2, 10, 3]`其排序结果为`[1, 2, 3, 10]`。

## 最高位起始基数排序法(MSD) ##

最高位起始基数排序法排序的结果是所谓的字典序排序(lexicographical order)。其流程大致是：对于所有输入元素，从最高位开向最低位（也就是从左向右）不断按位排序。对于较短元素，我们默认在其后补空白字符（例如数字补`0`）。例如对于一个输入字符串数组`["b", "c", "d", "ba"]`，其排序结果为`["b", "ba", "c", "d"]`。对于一个输入数字数组`[1,2,3,10]`其排序结果为`[1, 10, 2, 3]`。

# 算法 #

我们以LSD算法为例，如下所示：

1.  找出数组中的最大值
2.  设当前步骤所比较的基数位为第一位。
3.  如果当前基数小于数组中最大值的位数长度，则取当前数组中每一元素的当前基数位数字，并基于这一数字，利用计数排序（counting sort）比较并重新排序整个数组。（我们也可以如上文所述首先按照长度排序整个数组。但这一操作并不影响整个算法的多项式时间复杂度，顾在此不做考虑）。
4.  基数位前移一位。
5.  以上一步中排序过后的数组作为输入，重复过程2-3。

上面过程中利用计数排序比较并重新排序整个数组的算法如下：

1.  初始化一个数组`count[]`，长度与当前数组所包含数字的进制相同。例如对于整数排序，数组长度应该是10。
2.  从前到后计算输入数组中当前数位数字对应的数量。
3.  根据上一步中得到的`count[]`数组计算累积汇总求和。经过这个步骤，则`count[i]`代表当前数位为`i`的数字在输出的排序过的数组中所在的\_\_最后一个位置\_\_的坐标。
4.  **从后到前**，将输入数组中对应数位数字为`i`的数字放入输出数组中`--count[i]`的位置。

## 时间复杂度 ##

`O(n*w)`。其中`n`为输入数组的长度。`w`为输入的数字中最长数字的长度。

## 空间复杂度 ##

`O(n)`

# Java实现 #

下面的代码实现了LSD基数排序以及MSD基数排序，供读者朋友们参考。**这里实现的两个算法都能正确的处理输入数组中有重复的问题。**

import java.util.Arrays;
    
    public class RadixSort {
        
        // the radix, or base of the input
        public int radix;
    
        // the exponential to get the current digit
        public int exp;
    
        public RadixSort(int radix, int exp) {
        
            this.radix = radix;
            this.exp = exp;
        }
    
        public RadixSort() {
        }
    
        public int[] lsdRadixSort(int[] nums) {
        
            int max = Arrays.stream(nums).max().getAsInt();
            int[] aux = new int[nums.length];
            while (max / exp > 0) {
        
                int[] count = new int[radix]; // counting sort for each radix
                // get counts of each digit
                for (int i = 0; i < nums.length; i++) {
        
                    count[(nums[i] / exp) % radix]++;
                }
    
                // cumulative sum for each count
                for (int i = 1; i < count.length; i++) {
        
                    count[i] += count[i - 1];
                }
    
                // counting sort
                for (int i = nums.length - 1; i >= 0; i--) {
        
                    int idx = --count[(nums[i] / exp) % radix];
                    aux[idx] = nums[i];
                }
    
                // copy back the sorted array
                for (int i= 0; i < aux.length; i++) {
        
                    nums[i] = aux[i];
                }
                exp *= radix;
            }
    
            return nums;
        }
    
        public String[] msdRadixSort(String[] arr) {
        
            int idx = 0;
            int maxLen = Integer.MIN_VALUE;
            for (String ele : arr) {
        
                maxLen = Math.max(maxLen, ele.length());
            }
    
            String[] aux = new String[arr.length];
            while (idx < maxLen) {
        
                // English characters
                int[] count = new int[26];
    
                for (int i = 0; i < arr.length; i++) {
        
                    count[getCharAt(idx, arr[i]) - 'a']++;
                }
    
                for (int i = 1; i < count.length; i++) {
        
                    count[i] += count[i - 1];
                }
    
                for (int i = arr.length - 1; i >= 0; i--) {
        
                    int pos = --count[getCharAt(idx, arr[i]) - 'a'];
                    aux[pos] = arr[i];
                }
    
                for (int i = 0; i < arr.length; i++) {
        
                    arr[i] = aux[i];
                }
                idx++;
            }
    
            return aux;
        }
    
        private char getCharAt(int idx, String str) {
        
            if (str.length() <= idx) {
        
                return 'a';
            }
    
            return str.charAt(idx);
        }
    }

[Link 1]: https://blog.csdn.net/Yaokai_AssultMaster/article/details/52869504