桶排序

0x00 不一样的桶排序

​ 前面所讲的排序算法，最快只能打到nlogn（最坏情况下的最快）

​ 而下面这种排序则可以更快

​ 如果n个元素的key值（用来进行比较的值）有m个可能，如果n»m，那么我们可以将所有m都列出来。具体方法是，构造一个链表数组，数组大小和m一样，每个下标对应一个m值，我们线性的把所有成绩遍历一遍，把这个元素挂到对应的链表上。当我们想顺序输出的时候，就把链表数组遍历一遍，把每个链表的的元素都输出。

​ 我们把这种排序称为桶排序，该方法的时间复杂度为为O(n+m)。

0x01 进一步扩展 基数排序

​ 上面是值的可能值相对于数据量来说很少，但如果m»n呢？这个时候要用到升级版的基数排序

​ 基数排序是基于桶排序的，10进制选用0-9做桶，根据数据的位数，分成不同的阶段，如上图的0-999的数，那么分三个阶段进行排序，先对最次位（个位）进行桶排序，把所有元素的个位按照大小桶排序，排序完成后，继续对十位进行桶排序，需要注意的是，这个时候遍历元素的顺序是第一次桶排序后的结果，这样我们才能保留个位数上的顺序，同样最后进行主位（百位）的桶排序 ，最终以主位的桶排序结果为准，进行输出， 我们需要知道每个桶上那一部分的结果主位上桶排序的结果，所以如果每个桶上的元素是以列表的形式或者数组的形式保存，我们就需要一个指针来保存主位桶排序的结果的开始位置，每个桶都需要。时间复杂度位O(p(n+b)) b是桶的数量 也就是基数0-9，而p则是桶排序的次数，p=logbN