基数排序 - (sunznx) 振翅飞翔
11 October 2019

下面的这段代码来自神书 《算法 4》

 1: int N = s.length;
 2: String[] aux = new String[N];
 3: int[] count = new int[R+1];
 4: 
 5: for (int i = 0; i < N; i++) {
 6:     count[s[i].key()+1]++;
 7: }
 8: 
 9: for (int r = 1; r <= R; r++) {
10:     count[r] += count[r-1];
11: }
12: 
13: for (int i = 0; i < N; i++) {
14:     int c = count[s[i].key()]++;
15:     aux[c] = s[i];
16: }
17: 
18: for (int i = 0; i < N; i++) {
19:     s[i] = aux[i];
20: }

理解这段代码是基数排序的基础,数组 count 用来记录字符串 s 每个字符出现的次数,即 。注意 第6行 这里是 count[s[i].key()+1] 而不是 count[s[i].key()] ,为什么?首先看,第 9~11 行的意思,这里对 “桶” 的记录做了前缀和。意思是这些 “桶” 装的并非是当前字符出现的次数,而是当前字符前面有多少个比他小的字符。例如:

s = "baac"
# 程序运行到第 11 行之后,count 数组如下:
count['a'] = 0
count['b'] = 2
count['c'] = 3
count['d'] = 4

这段代码处理得很巧妙,看不懂的自己慢慢 debug。上面的程序跑完之后,字符串 s ,便已经排好序了

LSD 和 MSD

LSD 从低位到高位
MSD 从高位到低位

假设有一组数字 [170, 045, 043, 075, 090, 802, 002, 024, 066]

LSD

第 1 次排序
[170, 090, 802, 002, 043, 024, 045, 075, 066]

第 2 次排序
[802, 002, 024, 043, 045, 066, 170, 090, 075]

第 3 次排序
[002, 024, 043, 045, 066, 075, 090, 170, 802]

MSD

第 1 次排序,排序后分桶,如果桶装的数大于 1 个,继续分桶
[045, 043, 075, 090, 002, 024, 066, 170, 802]
[
 0 => [045, 043, 075, 090, 002, 024, 066]
 1 => [170]
 8 => [802]
]

继续分桶
[
 0 => [
   0 => [002]
   2 => [024]
   4 => [045, 043]
   6 => [066]
   7 => [075]
   9 => [090]
 ]
 1 => [170]
 8 => [802]
]

继续分桶
[
 0 => [
   0 => [002]
   2 => [024]
   4 => [
     3 => [043]
     5 => [045]
   ]
   6 => [066]
   7 => [075]
   9 => [090]
 ]
 1 => [170]
 8 => [802]
]

MSD 虽然看起来更啰嗦些,但是对于字符串来说更方便些,因为字符串一般都是从 0 开始往后遍历

代码可以参考:
https://github.com/sunznx/php-datastruct/blob/master/src/LSD/LSD.php
https://github.com/sunznx/php-datastruct/blob/master/src/MSD/MSD.php