简介
思想
将阵列分到有限数量的桶子里，每个桶子再进行排序
子桶内排序方法不限，有可能仍是桶排序或其他排序方法
思路
-
大小为[1…1000]范围内的n个整数A[1…n]待排排序；
-
把桶设为大小为10的范围，具体而言，设集合B[1]存储[1…10]的整数，集合B[2]存储 (10…20]的整数，……集合B[i]存储( (i-1)10, i10]的整数，i = 1,2,…100。总共有 100个桶；
-
对A[1…n]从头到尾扫描一遍，把每个A[i]放入对应的桶B[j]中；
-
再对这100个桶中每个桶里的数字排序（方法不限）；
-
依次输出桶中的值，会得到有序序列；
缺点
-
空间复杂度高，需要2个待排序列的空间；
-
待排的元素都要在一定的范围内；
基数排序
思想
是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前
思路
稳定性
基数排序基于分别排序，分别收集，所以是稳定的
关键码排序
设n 个元素的待排序列包含d 个关键码{k1，k2，…，kd}，则称序列对关键码{k1，k2，…，kd}有序是指：对于序列中任两个记录r[i]和rj都满足下列有序关系：
关键码排序方法1
最高位优先（MSD）法
-
先按k1 排序分组，将序列分成若干子序列，同一组序列的记录中，关键码k1 相等；
-
再对各组按k2 排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd 对各子组排序后；
-
再将各组连接起来，便得到一个有序序列。扑克牌按花色、面值排序中介绍的方法一即是MSD 法；
关键码排序方法2
最低位优先（LSD）法
-
先从kd 开始排序，再对kd-1进行排序，依次重复，直到按k1排序分组分成最小的子序列后；
-
最后将各个子序列连接起来，便可得到一个有序的序列, 扑克牌按花色、面值排序中介绍的方法二即是LSD 法；
案例分析
待排序列：52张扑克牌；
优先级：花色：黑心 > 红心 > 方块 > 梅花；
面值：2 …… A
排序方法1
先对花色排序，将其分为4 个组，即梅花组、方块组、红心组、黑心组。再对每个组分别按面值进行排序，最后，将4 个组连接起来即可
排序方法2
- 先按13 个面值给出13 个编号组(2 号，3 号，…，A 号);
- 将牌按面值依次放入对应的编号组，分成13 堆；
- 按花色给出4 个编号组(梅花、方块、红心、黑心)，将13组中的牌取出放入对应花色组；
- 将4个花色组l连接起来就是目标有序列表；