漫画：什么是基数排序？

ゝ一纸荒年。 2023-07-17 12:33 11阅读 0赞

![format_png][]

![format_png 1][]

**—————  第二天  —————**

![format_png 2][]

![format_png 3][]

![format_png 4][]

![format_png 5][]

![format_png 6][]

![format_png 7][]

![format_png 8][]

————————————

![format_png 9][]

![format_png 10][]

![format_png 11][]

![format_png 12][]

![format_png 13][]

什么是计数排序呢？让我们举例说明一下。

给定20个随机整数的值如下：

**9，3，5，4，9，1，2，7，8，1，3，6，5，3，4，0，10，9 ，7，9**

如何最快地把这些无序的随机整数排序？

由于这些整数的范围是从0到10这11个数，我们可以创建一个长度11的**空数组**，数组从0到10的下标，对应着待排序的随机整数值0到10：

![format_png 14][]

接下来遍历这个无序的随机数列，每一个整数按照其值对号入座，对应数组下标的元素进行加1操作。

比如第一个整数是9，那么数组下标为9的元素加1：

![format_png 15][]

第二个整数是3，那么数组下标为3的元素加1：

![format_png 16][]

继续遍历数列并修改数组......

最终，数列遍历完毕时，数组的状态如下：

![format_png 17][]

数组每一个下标位置的值，代表了数列中对应整数出现的次数。

有了这个“统计结果”，排序就很简单了。直接遍历数组，输出数组元素的下标值，元素的值是几，就输出几次：

**0，1，1，2，3，3，3，4，4，5，5，6，7，7，8，9，9，9，9，10**

显然，这个输出的数列已经是有序的了。

这就是**计数排序的朴素版本**。

为了实现稳定排序（排序后，相等元素原本的先后顺序不变），真正的计数排序要稍微复杂一些，感兴趣的小伙伴可以读一读这篇：

[漫画：什么是计数排序？][Link 1]

![format_png 18][]

![format_png 19][]

计数排序有什么局限呢？让我们看两个特殊的需求：

**需求A，为一组给定的手机号排序：**

**18914021920**

**13223132981**

**13566632981**

**13660891039**

**13361323035**

**........**

按照计数排序的思路，我们要根据手机号的取值范围，创建一个空数组。

可是，11位手机号有多少种组合？恐怕要建立一个大得不可想象的数组，才能装下所有可能出现的11位手机号！

**需求B，为一组英文单词排序：**

**banana**

**apple**

**orange**

**peach**

**cherry**

**........**

计数排序适合的场景是对整数做排序，如果遇到英文单词，就无能为力了。

![format_png 20][]

![format_png 21][]

如何有效处理诸如手机号、英文单词等复杂元素的排序呢？仅仅靠一次计数排序很难实现。

这时候，我们不妨**把排序工作拆分成多个阶段，每一个阶段只根据一个字符进行计数排序，一共排序k轮**（k是元素长度）。

或许这样的描述有些抽象，我们来举一个例子。

数组中有若干个字符串元素，每个字符串元素都是由三个英文字母组成：

**bda，****cfd，****qwe，****yui，****abc，****rrr，uee**

如何将这些字符串按照字母顺序排序呢？

由于每个字符串的长度是3个字符，我们可以把排序工作拆分成3轮：

**第一轮：**按照**最低位**字符排序。排序过程使用计数排序，把字母的ascii码对应到数组下标，第一轮排序结果如下：

![format_png 22][]

**第二轮：**在第一轮排序结果的基础上，按照**第二位**字符排序。

![format_png 23][]

需要注意的是，这里使用的计数排序必须是稳定排序，这样才能保证第一轮排出的先后顺序在第二轮还能继续保持。

比如在第一轮排序后，元素uue在元素yui之前。那么第二轮排序时，两者的第二位字符虽然同样是u，但先后顺序万万不能变，否则第一轮排序就白做了。

**第三轮：**在第二轮排序结果的基础上，按照**最高位**字符排序。

![format_png 24][]

如此一来，这些字符串的顺序就排好了。

像这样把字符串元素按位拆分，每一位进行一次计数排序的算法，就是**基数排序（Radix Sort）**。

基数排序既可以从高位优先进行排序（Most Significant Digit first，简称**MSD**），也可以从低位优先进行排序（Least Significant Digit first，简称**LSD**）。

刚才我们所举的例子，就是典型的LSD方式的基数排序。

![format_png 25][]

![format_png 26][]

什么意思呢？比如给定如下几个单词：

**banana**

**apple**

**orange**

**ape**

**he**

这里最长的单词有6个字符，其余不足6个字符的单词在末尾补0即可：

**banana**

**apple****0**

**orange**

**ape****000**

**he****0000**

在排序时，我们把字符0当做是比a更小的字符，排序结果如下：

**ape****000**

**apple****0**

**banana**

**he****0000**

**orange**

![format_png 27][]

![format_png 28][]

1.  `//ascii码的取值范围`
2.  `public static final int ASCII_RANGE = 128;`
3.   
4.   
5.  `public static String[] radixSort(String[] array,int maxLength)`
6.  `{`
7.  `//排序结果数组，用于存储每一次按位排序的临时结果`
8.  `String[] sortedArray = new String[array.length];`
9.  `//从个位开始比较，一直比较到最高位`
10. `for(int k=maxLength-1;k>=0;k--)`
11. `{`
12. `//计数排序的过程，分成三步：`
13. `//1.创建辅助排序的统计数组，并把待排序的字符对号入座，`
14. `        //这里为了代码简洁，直接使用ascii码范围作为数组长度`
15. `int[] count = new int[ASCII_RANGE];`
16. `for(int i=0;i<array.length;i++)`
17. `{`
18. `int index = getCharIndex(array[i],k);`
19. `count[index]++;`
20. `}`
21. `//2.统计数组做变形，后面的元素等于前面的元素之和`
22. `for(int i=1;i<count.length;i++)`
23. `{`
24. `count[i] = count[i] + count[i-1];`
25. `}`
26. `//3.倒序遍历原始数列，从统计数组找到正确位置，输出到结果数组`
27. `for(int i=array.length-1;i>=0;i--) {`
28. `int index = getCharIndex(array[i],k);`
29. `int sortedIndex = count[index]-1;`
30. `sortedArray[sortedIndex] = array[i];`
31. `count[index]--;`
32. `}`
33. `//下一轮排序需要以上一轮的排序结果为基础，因此把结果复制给array`
34. `array = sortedArray.clone();`
35. `}`
36.  
37. `return array;`
38. `}`
39.  
40.  
41. `//获取字符串第k位字符所对应的ascii码序号`
42. `private static int getCharIndex(String str, int k){`
43. `//如果字符串长度小于k，直接返回0，相当于给不存在的位置补0`
44. `if(str.length() < k+1){`
45. `return 0;`
46. `}`
47. `return str.charAt(k);`
48. `}`
49.  
50.  
51. `public static void main(String[] args)`
52. `{`
53. `String[] array = {"qd","abc", "qwe","hhh","a","cws", "ope"};`
54. `System.out.println(Arrays.toString(radixSort(array, 3)));`
55. `}`

这段代码基于一个大循环来实现，循环进行k次，k就是数组中最长字符串元素的字符数。

在循环体内，执行的是计数排序的逻辑。这个稳定的计数排序算法不太好理解，在小灰往期的漫画中有进行详细讲解（[漫画：什么是计数排序？][Link 1]）。

![format_png 29][]

![format_png 30][]

![format_png 31][]

![format_png 32][]

![format_png 33][]

[format_png]: /images/20230528/476da235cc494dc5a3829f80dd67b02b.png
[format_png 1]: /images/20230528/67f495503f6c4caa9bffea939fa714ff.png
[format_png 2]: /images/20230528/a783958d6a644678be367acc6af5c345.png
[format_png 3]: /images/20230528/ab8d39540a614f749b3b84a45a4117de.png
[format_png 4]: /images/20230528/e88e00f505e14b949fd912705832f3a7.png
[format_png 5]: /images/20230528/49f84e533dd348f6aec5f2e679d66855.png
[format_png 6]: /images/20230528/0b0eaff88e5046b69dead573f856a235.png
[format_png 7]: /images/20230528/267502b4486f4fddb68e9d5645e5762d.png
[format_png 8]: /images/20230528/67b7ee5f8a324b0ca2544aa8050a54da.png
[format_png 9]: /images/20230528/90e9223a924e43a1adf4a28b97f31278.png
[format_png 10]: /images/20230528/9dfaa81d2498408594e09c64375f2644.png
[format_png 11]: /images/20230528/7895feef074546a096b2e289f95b45fe.png
[format_png 12]: /images/20230528/dda38c9e392d475fab4e85d977e68bc0.png
[format_png 13]: /images/20230528/7df2c332d02f4d279e405f5f0eb6a300.png
[format_png 14]: /images/20230528/f3b1aa471f2c4d1c9eb0f27276805c3e.png
[format_png 15]: /images/20230528/55d46012ab714ed485c51cb98ecc398f.png
[format_png 16]: /images/20230528/ccf4c1bad1ae423b87ee035cc8d44518.png
[format_png 17]: /images/20230528/76e902c938af45498b38428ea92e5021.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653195533&idx=1&sn=02918dc51b07837ce1119f00d7900dbc&chksm=8c99ffd7bbee76c1d2e2e9b198259795285ec2c305d3613a5e39622195fd1c32bb6dbe52fa08&scene=21#wechat_redirect
[format_png 18]: /images/20230528/c882111ca9e5442f90900140d5614edf.png
[format_png 19]: /images/20230528/6e4e7459613242ed82b3b8738a9a03e6.png
[format_png 20]: /images/20230528/5da26b9055f44943852c1f0352680608.png
[format_png 21]: /images/20230528/e51158b202c34effbc2cfb8857087ce5.png
[format_png 22]: /images/20230528/a30807efba5e4df4a537cde6ef6bc27a.png
[format_png 23]: /images/20230528/06b76ec64c2e4156a06e2f1bcb4e46c7.png
[format_png 24]: /images/20230528/26e5cf7f7d97496cad829741c9b4ee36.png
[format_png 25]: /images/20230528/b88b658e32f24a15b2dd3c26af69cff8.png
[format_png 26]: /images/20230528/d7bdd9ce2fef4dbb9cdb8ca764e45b93.png
[format_png 27]: /images/20230528/e801c5dbccd04a6594ca4da4587818c1.png
[format_png 28]: /images/20230528/2a3612b0c4ce44d5bd03b0a4c3523b09.png
[format_png 29]: /images/20230528/ad49538970584c84a8dbdc82dbd0341f.png
[format_png 30]: /images/20230528/d972ef806a314deba274d226e3f7fa7e.png
[format_png 31]: /images/20230528/02f1e64c327a45f2abab5298c8e9eedc.png
[format_png 32]: /images/20230528/5964593565d0424d9cf0899f25afaf7c.png
[format_png 33]: /images/20230528/d17be7455678492e9d5191dc65568cad.png