动画：什么是基数排序？

水深无声 2022-12-02 01:13 124阅读 0赞

![format_png][]

![format_png 1][]

![format_png 2][]

## 基数排序    ##

与基于比较的排序算法（归并排序、堆排序、快速排序、冒泡排序、插入排序等等）相比，基于比较的排序算法的时间复杂度最好也就是，而且不能比更小了。

计数排序（Counting Sort）的时间复杂度为量级，更准确的说，计数排序的时间复杂度为，其中表示待排序元素的取值范围（最大与最小元素之差加 1 ）。

那么问题来了，当这个元素的的范围在 1 到怎么办呢？

此时就不能用计数排序了奥，因为这种情况下，计数排序的时间复杂度达到了量级。

比如对数组 `[170, 45, 75, 90, 802, 24, 2, 66]` 这个而言，数组总共包含 **8** 个元素，而数组中的最大值和最小值之差为 **`802 - 2 = 800`** ，这种情况下，计数排序就 ”失灵了“ 。

那么有没有那种排序算法可以在线性时间对这个数组进行排序呢？

答案就是今天要讲的 **基数排序（Radix Sorting）** 。基数排序的总体思想就是从待排序数组当中，元素的最低有效位到最高有效位 **逐位** 进行比较排序；此外，基数排序使用计数排序作为一个排序的子过程。

下面我们就以数组 **`[170, 45, 75, 90, 802, 24, 2, 66]`** ，快乐学习基数排序！

数组当中的最大值 **802** 为三位数，所以我们在不足三位的数字前面补 **0** ，即**`[170, 045, 075, 090, 802, 024, 002, 066]`**方便后续说明基数排序。

![format_png 3][]

第一步：按数组当中元素的最低有效位，个位 **\[170 ,045 ,075 , 090 ,802 , 024 , 002 , 066 \]**，进行计数排序：

![format_png 4][]

第二步：按数组当中元素的次最低有效位，十位数 **\[1****7****0, 0****9****0, 8****0****2, 0****0****2, 0****2****4, 0****4****5, 0****7****5, 0****6****6\]** ，进行计数排序：

![format_png 5][]

第三步：按数组当中元素的最高有效位，百位 **\[****8****02,** **0****02,** **0****24,** **0****45,** **0****66,** **1****70,** **0****75,** **0****90\]** ，进行计数排序：

![format_png 6][]

这样我们就完成了基数排序，得到了一个有序数组 **\[2, 24, 45, 66, 75, 90, 170, 802\]** .

### 高清视频动画 ###

## 实现代码 ##

import java.io.*; 
    import java.util.*; 
      
    class Radix { 
      
        // 获取数组中的最大值 
        static int getMax(int arr[], int n) 
        { 
            int max = arr[0]; 
            for (int i = 1; i < n; i++) 
                if (arr[i] > mx) 
                    max = arr[i]; 
            return max; 
        } 
      
        // 计数排序
        static void countSort(int arr[], int n, int exp) 
        { 
            int output[] = new int[n]; //输出数组 
            int i; 
            int count[] = new int[10]; 
            Arrays.fill(count,0); 
      
            // 统计数组中元素第 exp 位的数目
            for (i = 0; i < n; i++){
                count[(arr[i]/exp)%10]++; 
            }
      
            // 对 count[] 数组进行转
            for (i = 1; i < 10; i++){
                count[i] += count[i - 1]; 
            }
      
            // 进行计数排序 
            for (i = n - 1; i >= 0; i--) 
            { 
                output[count[ (arr[i]/exp)%10 ] - 1] = arr[i]; 
                count[ (arr[i]/exp)%10 ]--; 
            } 
      
            // 输出到数组arr[]中
            for (i = 0; i < n; i++){ 
                arr[i] = output[i]; 
            }
        } 
      
        // 基数排序
        static void radixsort(int arr[], int n) 
        { 
            // Find the maximum number to know number of digits 
            int m = getMax(arr, n); 
      
            // 对数组当中的数字按照每一个有效位进行一趟计数排序。 
            for (int exp = 1; m/exp > 0; exp *= 10){
                countSort(arr, n, exp);         
            } 
        } 
      
        // 进行输出
        static void print(int arr[], int n) 
        { 
            for (int i=0; i<n; i++) 
                System.out.print(arr[i]+" "); 
        } 
      
      
        /*Driver function to check for above function*/
        public static void main (String[] args) 
        { 
            int arr[] = {170, 45, 75, 90, 802, 24, 2, 66}; 
            int n = arr.length; 
            radixsort(arr, n); 
            print(arr, n); 
        } 
    }

实现当中有一个细节需要解释一下，那就是如何从最低位到最高位取每一个数字的该位的值。答案很简单了，就是除 **10** 取余。

比如 **802** ，要取最低位，**`802 % 10 = 2`** ，就取到了个位；紧接着除 **10** 取商数 **802 / 10 = 80** ，然后对商数 80 进行除 10 取余数，就可以得到十位了，**80 % 10 = 0** ；最后再对 **80** 除 **10** 取商数 **80 / 10 = 8** ， 然后对商数 **8** 进行除 **10** 取余数，**8 % 10 = 8** 就可以得到百位数。

代码中的 **`(arr[i] / exp) % 10`** 就可以轻松理解啦， **`exp`** 就相当于控制位数，而取余操作就相当于取出第 **`exp`** 位的值。

当然彻底搞懂基数排序，前提是你要清楚计数排序（Counting Sort），又到打广告的时间了，推荐看一下 [漫画：什么是计数排序？][Link 1]。

## 复杂度分析 ##

### 时间复杂度 ###

设表示输入的数组当中最大值的位数（比如 802，3位，），那么基数排序的时间复杂度就是，其中表示数组的长度，而则是表示一个数的基础，对十进制而言，；

设是一个计算机可表示的最大整数，那么；

则基数排序整个时间复杂度为。

对于一个较大的数，计数排序的这个时间复杂度似乎比基于比较的排序算法都慢，但是事实未必，接着看。

假设取一个最大整数，其中是一个常量；

那么基数排序的时间复杂度就为，其中和都是常数，我们可以忽略不计，那么基数排序的时间复杂度就变成了，但是这依旧不比基于排序算法的最好时间复杂度好呀？

可是当我们将这个取足够大呢？取多少的时候基数排序的时间复杂度才能变成线性呢？

当的时候，，基数排序的时间复杂度就变成了，线性时间复杂度。

也就说，当数字用进制表示的时候，我们就可以对 1 到范围之内的数组进行线性排序。

![format_png 7][]

![format_png 8][]

对于元素的跨度（范围）比较大的数组而言，基数排序的运行时间可能比快速排序要好。但是对于基数排序而言，其渐近时间复杂度中隐含了更高的常量因子，并非完全的线性；而快速排序更有效地利用硬件缓存，提高其效率。此外，基数排序使用计数排序作为子过程，计数排序占用额外的空间来对数组进行排序。

但是基数排序解决我们最开始所提出的问题，当数据范围在 1 到时，计数排序的复杂度将变为量级，而基数排序依旧可以在线性时间进行排序！

### 空间复杂度 ###

计数排序使用了额外的空间进行排序，空间复杂度为。

\---

由 五分钟学算法 原班人马打造的公众号：图解面试算法，现已正式上线！
    接下来我们将会在该公众号上，为大家分享优质的算法解题思路，坚持每天一篇原创文章的输出，视频动画制作不易，感兴趣的小伙伴可以关注点赞一下哈！

[format_png]: /images/20221123/02927a63d14146c68e7c046791dda9ce.png
[format_png 1]: /images/20221123/e757e3c0cada491aacbbbdc57f71bfd2.png
[format_png 2]: /images/20221123/c1c79d96a5864c5983bcee3dd8b389a9.png
[format_png 3]: /images/20221123/eb27239f9101487c97760ae703269f08.png
[format_png 4]: /images/20221123/e7581bc174744f8d9c0705c9087bc825.png
[format_png 5]: /images/20221123/8c4a0f5ab49f40cb8c84306c4835d92b.png
[format_png 6]: /images/20221123/8e46619e16f245b0aae97fc27ba21cfa.png
[Link 1]: https://mp.weixin.qq.com/s?__biz=MzA4NDE4MzY2MA%3D%3D&idx=1&mid=2647522892&scene=21&sn=e77db7b84d0951432bbfd0a96c87f06a#wechat_redirect
[format_png 7]: /images/20221123/207485c8603f4c1b9b4b645043709b30.png
[format_png 8]: /images/20221123/9bc1670c54c64819a28e46387158221f.png