算法之排序(下)

前面两篇文章说了时间复杂度为O(n2)的冒泡排序、插入排序和选择排序；也说了时间复杂度为O(nlogn)的归并排序和快速排序；这次来说一下时间复杂度为O(n)的桶排序、计数排序和基数排序，由于它们的时间复杂度是线性的，所以它们也叫做线性排序（Linear sort），之所以能够做到线性复杂度，是因为它们在排序的时候，不涉及元素之间的比较，同时它们的使用条件也是非常苛刻的。

桶排序（Bucket sort）

桶排序，顾名思义，用桶来对数据进行分割，桶排序是将要排序的数组分到几个有序的桶里面，然后对每个桶里面的数据进行排序，最后将所有数据依次取出，就完成了排序。

来看一下它的时间复杂度，假如将n个数据平均分到m个桶中，每一个桶中有x=n/m个数据，每个桶使用快速排序，时间复杂度为O(xlogx)，m个桶的时间复杂度就是O(m*xlogx)，因为x=n/m，所以时间复杂度为O(nlog(n/m))，当桶的个数接近数据n时， log(n/m) 将会是一个非常小的数，时间复杂度就接近与O(n)了。

但是，上面用了假如两个字，因为要使用桶排序所需要的前提条件比较多，首先数据需要很容易就可以划分到m个桶中，而且每一个桶它本身就需要有先后顺序，这样桶就不需要再进行排序了。其次，我们上面把均匀两个字给加粗了，只有在桶中的数据比较平均时才可以，如果每一个桶中的数据差距是非常大的，那桶内排序的时间复杂度就不是常量级了，最极端的情况就是分到了一个桶中，那时间复杂度就变成了O(nlogn)了。

桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。

假如有10个G的订单数据，订单金额都是正整数，要根据金额大小进行排序，而内存又比较小，无法同时装下所有的数据该怎么办？

用桶排序的思路就是，先扫描一遍订单，看一下大概的金额分布，假如金额都分布在1到1万，我们就可以将金额分到10个桶里，第一个桶是1~1000，依此类推，它们的顺序依次是0，1，2…9。

理想情况下，就是它们均匀分布在每一个桶中，然后我们在每一个桶中使用快速排序，最后将它们依次输出出来。那如果1000-2000的金额比较多的话，还是无法直接放到内存中，那就继续使用桶排序进行分割，直到全部排序完成。

计数排序（Counting sort）

计数排序基本上属于桶排序的特殊情况，在要排序的范围不大的时候，比如有x个数据，那我们就分x个桶，每个桶内的数据都是相同的，这样我们就省下了桶内排序的时间。

至于为什么要叫计数，这个是跟计数排序的实现方法有关的，不过我还没有理解清楚，这里就先放下了，这个坑之后再填。

基数排序（Radix sort）

再来一个排序问题来看，如果有十万个手机号码，要将这十万个手机号从小到大排序。如果使用前面的桶排序和计数排序，它的范围比较大，这两种算法明显都不适合。

现在就可以用到第三个排序方法，基数排序。在刚刚的问题里，我们可以明显的看出来，当一个号码前面的几位已经明显大于另一个号码，那后面的也就不需要比较了，也就是说我们需要将手机号排序为第一个数字从小到大排序，第一个数字相同的，按照第二个数字从小到大排序，第二个数字相同的，按照第三个，依此类推，那如何才能排列成这样呢。

这里我们用一个新的思路来考虑，我们先按照最后一位数字的大小来进行排序，然后再按照倒数第二位进行排序，依此类推，经过11次排序以后，就完成了对整个手机号的排序。这里需要注意一下的是，必须用稳定的排序算法来实现，如果是非稳定的排序算法，之前的排序就没有任何的意义了。

用几个字符串表示的话，就是这个样子的

再举一个订单的例子，对于一批订单，我们希望将它按照金额的大小排序，如果金额相同，就按照下单的时间进行排序，一样是使用这样的方法。

那如果我们需要排序的数据并不是等长的，又该如何去处理，比如说要对单词进行排序，有的单词是五个字母，有的单词是十五个字母，那该如何处理？

我们可以把所有的字母都补到一样的长度，不足的后面补0，因为根据ASCII码我们可以发现，所有的字母都在数字0之后，它并不会影响排序的正常进行，所以依旧可以使用基数排序来进行。

参考文档

极客时间-数据结构与算法之美