记数排序 & 桶排序 & 基数排序 记数排序 桶排序 基数排序
为什么要写这样滴一篇博客捏...因为一个新初一问了一道水题，结果就莫名其妙引起了战斗。
然后突然发现之前理解的桶排序并不是真正的桶排序，所以写一篇来区别下这三个十分相似的排序辣。
老年菜兔的觉醒！！！
记数排序是一种很快的排序算法，但是要很多的空间。
具体的操作：
比如说给一个这样的数列： 6 9 3 2 3 5
我萌需要一个数组 a[i] 表示 数列中 数值为 i 的有多少个
这样 就可以 O（n） 处理出这个数组
read(x);
a[x]++;
比如辣个栗子的a数组是这样滴
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| a[i] | 0 | 1 | 2 | 0 | 1 | 1 | 0 | 0 | 1 |
然后这个数组有什么用捏
可以发现，只需要枚举 i （如栗子里是 1≤i≤9 ）
然后输出 a[i] 个 i 后就是一个从小到大排序后的数列
for i=1 to 9 do (通常可以取数列中的最大数max，这里取栗子的9) for j=1 to a[i] do write(i,' ');
这样之后就会输出 2 3 3 5 6 9
这就是记数排序（老年菜兔之前把计数排序误以为是桶排序QAQ）
效率基本为 O（N） 但是有一个缺陷，就是当数列的值十分十分大的时候，数组就开不下了。
这个问题怎么解决好捏，就是桶排序和基数排序辣！
桶排序
桶排序实际上是对计数排序的一些优化，他把时间又换回了一部分空间（计数排序用空间换时间）。
桶排序思想是什么捏？
继续举个栗子呀 6 9 3 2 3 5 （咦好熟悉）
首先我萌要定一个值 m 这个值可以任意定，但会影响到效率。
m是干什么用的？
不如这样理解一下，计数排序实际上就是用了好多好多个桶 总共 max 个
而桶排序是用了 （max/m） 个桶 所以这个 m 的含义实际上是区间范围。
计数排序是桶排序的一种特殊情况，就是 取 m=1的时候。
这时我萌需要一个数组 a[i,j]表示 第 i 个桶中的第j个元素的数值。
（通常不用数组而是链表，原因是可能有这样的数据 如数列中全都是1-3范围的 这时数组就开不下，如果n十分大）
嗯列个表吧
这里我萌取 m=3 （就是举个栗子）
| 桶中数据的范围 | 1~3 | 4~6 | 7~9 |
| 相应的i（也就是第几个桶） | 1 | 2 | 3 |
| 桶内的元素 | 3,2,3 | 6,5 | 9 |
这时发现什么捏...每一个桶里的元素是无序的。
所以对每一个桶都做一个其他的排序，如快排。
然后排序后再把这些桶合并起来就好啦
诶？？？每一个桶？辣么效率岂不是很低。
答案是否定的，相反，桶排序效率通常比快排快。
快排的平均效率为O(n log n) 而桶排捏是 O(max/m *m log m) 即 O(max log M) 假设max=n=1000000（1百万）
快排的计算量约 23000000（2300万） 而 桶排序如果取M=2500(既省了一点空间，又有很高的时间效率) 的计算量约 12000000（1200万）
可见桶排序效率也比较高。
而且桶排序每个桶的排序算法还可以换为其他的不一定要快排。
桶排序的应用似乎不多，而似乎很多人搞混了基数排序与桶排序。
相比之下把基数排序误认为是桶排序的人会更多的样子。
所以基数排序的应用应该更广。
基数排序
基数排序的方法更是神奇，他用到了计数排序的思想。
基数排序的操作我还是要举个栗子...不过图就不放了QAQ不然水的成分有点大
如：543 123 756 666 841 322 10 799 69 (终于换了个栗子，因为上一次栗子次掉了)
基数排序的操作是这样的。
最低位（个位）为一个关键字，次低位是一个关键字...以此类推。
我萌先对最低位为关键字做一次计数排序。
如果依旧用桶来比喻的话，因为一个位数上只会有0-9 这些数字。
所以就是10个桶
列个表吧
| 桶 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|
第1次操作后 桶里的元素 |
10 | 841 | 322 | 543,123 | 756,666 | 799,69 |
然后第一次操作后再合并起来就是这样的数列 （注意每一个桶内是无序的，都是按原来数列的位置）
10 841 322 543 123 756 666 799 69
还是一个无序的数列，接着对次低位为关键字做记数排序
| 桶 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|
第2次操作后 桶里的元素 |
10 | 322,123 | 841,543 | 756 | 666,69 | 799 |
然后第二次操作后再合并起来就是这样的数列（注意每一个桶内依旧是无序的，都是按第一次操作后的数列的位置）
10 322 123 841 543 756 666 69 799
然后就第三低位为关键字做记数排序
| 桶 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|
第2次操作后 桶里的元素 |
010,069 | 123 | 322 | 543 | 666 | 756,799 | 841 |
然后合并
10 69 123 322 543 666 756 799 841
这时排序结束，数列有序了。
是不是很神奇捏？
为什么要对每一位都做一次计数排序？
实际上就是改变位置。比如如果出现了 123 124 这样的元素，在原来数列是这样的 124 123
辣么对最低位进行计数排序就可以变成 123 124 从而改变了位置。
好了，辣基数排序的效率?
设最大值有 d 位
约O（d*n） 的效率
而d是十分小的，相比桶排序，虽然效率变低了一点，但适用于一些数值十分大的数据。
再扩充一点基排
实际上，这里使用了10个桶，辣么可不可以多用些桶捏？当然可以
我萌可以使用100个桶，将最低位和次低位看成一个整体 为一个关键字，比如 5678 此时 以78 为一个关键字 56为另一个关键字。
然后操作是一样的但是却只有 d/2个关键字了，从而效率又快了，但空间变多了，变成了100个桶。
以此类推，还有1000 10000 ...个桶。辣如果不是整10个桶行不行，当然行，这样的话需要把10进制数看为其他进制的数来做计数排序。具体就不细讲啦~
好啦~讲完啦，总结一下吧，总体来说，三个排序都是用到了计数排序的思想。
桶排序效率高，但数值过大还是无法使用，而基数排序不仅效率高了很多，而且适用数值大的数据。
老年菜兔的讲解结束啦~撒花~