桶排序，计数排序，基数排序

本文创作灵感来源于极客时间王争老师的《数据结构与算法之美》课程，通过课后反思以及借鉴各位学友的发言总结，现整理出自己的知识架构，以便日后温故知新，查漏补缺。

上述三种排序算法的时间复杂度为 O(n)，所以称之为线性排序。之所以能做到线性排序，是因为上述排序实现的思想不是基于比较的排序。这三种排序对数据的要求比较苛刻，所以重要的是理解这三种排序应用的场景。

桶排序

桶排序重点在于理解桶的概念。对于待排序的数据，我们先设置一定数量的桶用来存放待排序的数据。其中这些桶是按照一定顺序划分好的，然后针对每个桶内的数据进行排序，最后按照桶的大小顺序依次取出其中元素，就实现了排序的目的。
桶排序的时间复杂度分析。假如我们有 n 个数据需要排序，首先分出 m 个桶，那么每个桶中的元素个数就是 k = n/m。每个桶内的数据用快速排序，时间复杂度就是 O(klogk)，那么 m 个桶的时间复杂度就是 O(mklogk)。将 k = n/m 带入表达式，则时间复杂度就是O(nlog(n/m))，当桶的个数等于数据个数时：m = n 的时候， log(n/m) 就是个非常小的数值，这个时候时间复杂度就是 O(n)。
桶排序对数据有着严格的要求。对于桶排序，待排序的数据要能很容易的分配到桶中，而且桶也已经是有序的。这样，桶内的数据排序后，就可以按照桶的顺序依次取数据。数据要保证能均匀的分配到各个桶中，如果每个桶中的数据量差别比较大，那桶排序的时间复杂度就不再是线性的了。比如极端的情况，只分出了一个桶，所有数据都放在一个桶中，那么时间复杂度就是等于快速排序的时间复杂度了，变成 O(nlogn)。
桶排序这种算法，适合应用在外部排序中。外部排序指的就是，内存空间无法一次加载完所有的数据，所以需要划分出桶，针对每个桶进行排序。举个理想的情况：一批订单，订单的金额均匀的分布在1-10000元之间，我们就可以划分出第一个桶放入订单金额 1 到 100 元之间的数据，第二个桶放入订单金额 101 到 200 元之间的数据，依次类推，最后一个桶放入 9901 到 10000 元之间的数据。然后每个桶内对数据排序，最后按照划分桶的顺序依次取出数据，就实现了排序。

实际情况中，订单金额并不会如此均匀的分布。如果部分桶中的数据量过大，我们可以针对这个桶内的数据，再次进行桶排序的操作。这样，我们就保证了每一个桶(无论是第几次划分的桶)的数据都能加载到内存中进行排序。

基数排序

我们引入场景来解释这个排序算法：对 10 万个手机号进行排序。
对手机号排序，我们从手机号的最后一位开始排序，然后在第一次排序的基础上排序倒数第二位，直到对手机号的第一位排序结束，那么 10 万个手机号就是有序的了。因为在手机号排序中，如果前几位已经比较出大小，那么我们就不用比较后面的位数的大小了。但是如果每次比较的高位都相等，那么我们就必须比较更低位的大小了。如果从高位往低位开始比较，如果高位比较的值相等，那么我们比较低位的时候，必须记录高位相等的数据的区间，这样排序算法中会增加非常多的逻辑判断，所以我们选择从低位往高位排序，每次的排序都是稳定排序，那么比较高位的时候，我们就不用顾忌低位的排序了。
时间复杂度分析，每次排序我们都用桶排序，时间复杂度为 O(n)，排序 k 次，时间复杂度就是 O(kn)，当 k 值不大的时候，时间复杂度就近似于 O(n)。
基数排序对数据的要求也十分严格。待排序的数据要能明确的划分出“位”，并且“位”与“位”之间是有递进关系的，所谓的递进关系就是高位排序区分出大小后，低位就不需要在排序了。另外，每个“位”上的数据范围不能太大，要可以用线性排序算法。
举一个应用例子：对于单词的排序，一样可以用基数排序。我们把单词长度补齐，位数不够的补 0 ，在ASCII值中 0 的值是小于所有字母的。然后我们就可以按照基数排序对单词进行排序了。

计数排序

这个我感觉好复杂，暂时还没有理解透彻，后续彻底理解了，再把计数排序补充出来。

总结

王争老师开篇给出了一个思考题，给 100 万用户按照年龄排序。假设最大岁数120，我们按照年龄划分出120个桶，然后每个桶中分配用户，最后依次遍历所有桶以及桶内的数据取出来，就完成了排序。

初入算法学习，必是步履蹒跚，一路磕磕绊绊跌跌撞撞。看不懂别慌，也别忙着总结，先读五遍文章先，无他，唯手熟尔~
与诸君共勉