[数据结构与算法]基数排序

编程论到极致，核心非代码，即思想。

所以，真正的编程高手同时是思想独到及富有智慧（注意与聪明区别）的人。

每一个算法都是一种智慧的凝聚或萃取，值得我们学习从而提高自己，开拓思路，更重要的是转换思维角度。

其实，我们大多数人都活在“默认状态”下。没有发觉自己的独特可设置选项-----思想。

言归正传（呵呵！恢复默认状态），以下学习基数排序。

【1】基数排序

以前研究的各种排序算法，都是通过比较数据大小的方法对欲排数据序列进行排序整理过程。

而基数排序却不再相同，那么，基数排序是采用怎样的策略进行排序的呢？

简略概述：基数排序是通过“分配”和“收集”过程来实现排序。而这个思想该如何理解呢？请看以下例子。

（1）假设有欲排数据序列如下所示：

73  22  93  43  55  14  28  65  39  81

首先根据个位数的数值，在遍历数据时将它们各自分配到编号0至9的桶（个位数值与桶号一一对应）中。

分配结果（逻辑想象）如下图所示：

分配结束后。接下来将所有桶中所盛数据按照桶号由小到大（桶中由顶至底）依次重新收集串起来，得到如下仍然无序的数据序列：

81  22  73  93  43  14  55  65  28  39

接着，再进行一次分配，这次根据十位数值来分配（原理同上），分配结果（逻辑想象）如下图所示：

分配结束后。接下来再将所有桶中所盛的数据（原理同上）依次重新收集串接起来，得到如下的数据序列：

14  22  28  39  43  55  65  73  81  93

观察可以看到，此时原无序数据序列已经排序完毕。如果排序的数据序列有三位数以上的数据，则重复进行以上的动作直至最高位数为止。

那么，到这里为止，你觉得你是不是一个细心的人？不要不假思索的回答我。不论回答什么样的问题，都要做到心比头快，头比嘴快。

仔细看看你对整个排序的过程中还有哪些疑惑？真看不到？觉得我做得很好？抑或前面没看懂？

如果你看到这里真心没有意识到或发现这个问题，那我告诉你：悄悄去找个墙角蹲下用小拇指画圈圈（好好反省反省）。

追问：观察原无序数据序列中73   93   43 三个数据的顺序，在经过第一次（按照个位数值，它们三者应该是在同一个桶中）分配之后，

在桶中顺序由底至顶应该为73  93  43（即就是装的迟的在最上面，对应我们上面的逻辑想象应该是43  93  73），对吧？这个应该可以想明白吧？理论上应该是这样的。

但是，但是，但是分配后很明显在3号桶中三者的顺序刚好相反。这点难道你没有发现吗？或者是发现了觉得不屑谈及（算我贻笑大方）？

其实这个也正是基数排序稳定性的原因（分配时由末位向首位进行），请看下文的详细分析。

再思考一个问题：既然我们可以从最低位到最高位进行如此的分配收集，那么是否可以由最高位到最低位依次操作呢？ 答案是完全可以的。

基于两种不同的排序顺序，我们将基数排序分为LSD（Least significant digital）或MSD（Most significant digital），

LSD的排序方式由数值的最右边（低位）开始，而MSD则相反，由数值的最左边（高位）开始。

注意一点：LSD的基数排序适用于位数少的数列，如果位数多的话，使用MSD的效率会比较好。

MSD的方式与LSD相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个数组中，而是在每个“桶子”中建立“子桶”，将每个桶子中的数值按照下一数位的值分配到“子桶”中。

在进行完最低位数的分配后再合并回单一的数组中。

（2）我们把扑克牌的排序看成由花色和面值两个数据项组成的主关键字排序。

要求如下：

花色顺序：梅花<方块<红心<黑桃

面值顺序：2<3<4<...<10