本文为原创文章，未经本人允许，禁止转载。转载请注明出处。

1.基数排序

基数排序（radix sort）又称“桶子法”（bucket sort或bin sort）。分为LSD（Least Significant Digit first，最低位优先）和MSD（Most Significant Digit first，最高位优先）两种方式。

1.1.LSD

假设待排序列为：

73	22	93	43	55	14	28	65	39	81

首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中：

0
1	81
2	22
3	73	93	43
4	14
5	55	65
6
7
8	28
9	39

接下来将这些桶子中的数值重新串接起来，成为以下的数列：

81	22	73	93	43	14	55	65	28	39

接着再进行一次分配，这次是根据十位数来分配：

0
1	14
2	22	28
3	39
4	43
5	55
6	65
7	73
8	81
9	93

接下来将这些桶子中的数值再次重新串接起来，成为以下的数列：

14	22	28	39	43	55	65	73	81	93

这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。

1.2.MSD

LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好。MSD的方式与LSD相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个数组中，而是在每个“桶子”中建立“子桶”，将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。

2.代码地址

基数排序

3.参考资料

基数排序（百度百科）

【算法基础】【排序】基数排序

基数排序，LSD（Least Significant Digit first，最低位优先），MSD（Most Significant Digit first，最高位优先）

1.基数排序

1.1.LSD

1.2.MSD

2.代码地址

3.参考资料

CATALOG

FEATURED TAGS