如何根据年龄给100万用户数据排序?
我们有10GB的订单数据，我们希望按订单金额(假设金额都是正整数)进行排序，但是我们的内存有限，只有几百MB，没办法一次性把10GB的数据都加 载到内存中。这个时候该怎么办呢?
桶排序(Bucket sort)
桶排序，顾名思义，会用到“桶”，核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。比如说我们有10GB的订单数据，我们希望按订单金额(假设金额都是正整数)进行排序，但是我们的内存有限，只有几百MB，没办法一次性把10GB的数据都加 载到内存中。这个时候该怎么办呢?
我们可以先扫描一遍文件，看订单金额所处的数据范围。假设经过扫描之后我们得到，订单金额最小是1元，最大是10万元。我们将所有订单根据金额划分 到100个桶里，第一个桶我们存储金额在1元到1000元之内的订单，第二桶存储金额在1001元到2000元之内的订单，以此类推。每一个桶对应一个文件，并且按照 金额范围的大小顺序编号命名(00，01，02...99)。
理想的情况下，如果订单金额在1到10万之间均匀分布，那订单会被均匀划分到100个文件中，每个小文件中存储大约100MB的订单数据，我们就可以将这100个小 文件依次放到内存中，用快排来排序。等所有文件都排好序之后，我们只需要按照文件编号，从小到大依次读取每个小文件中的订单数据，并将其写入到一个文 件中，那这个文件中存储的就是按照金额从小到大排序的订单数据了。
订单按照金额在1元到10万元之间并不一定是均匀分布的 ，所以10GB订单数据是无法均匀地被划分到100个文件中的。有可能某个金额区 间的数据特别多，划分之后对应的文件就会很大，没法一次性读入内存。这又该怎么办呢?
针对这些划分之后还是比较大的文件，我们可以继续划分，比如，订单金额在1元到1000元之间的比较多，我们就将这个区间继续划分为10个小区间，1元 到100元，101元到200元，201元到300元...901元到1000元。如果划分之后，101元到200元之间的订单还是太多，无法一次性读入内存，那就继续再划分，直到所 有的文件都能读入内存为止。
计数排序(Counting sort)
计数排序其实是桶排序的一种特殊情况。当要排序的n个数据，所处的范围并不大的时候，比如最大值是k，我们就可以把数据划分成k个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。
我们都经历过高考，高考查分数系统你还记得吗?我们查分数的时候，系统会显示我们的成绩以及所在省的排名。如果你所在的省有50万考生，如何通过成绩快 速排序得出名次呢?
考生的满分是900分，最小是0分，这个数据的范围很小，所以我们可以分成901个桶，对应分数从0分到900分。根据考生的成绩，我们将这50万考生划分到 这901个桶里。桶内的数据都是分数相同的考生，所以并不需要再进行排序。我们只需要依次扫描每个桶，将桶内的考生依次输出到一个数组中，就实现了50万考 生的排序。因为只涉及扫描遍历操作，所以时间复杂度是O(n)。
为什么这个排序算法叫“计数”排序呢?“计数”的含义来自哪里呢?
我对数据规模做了简化。假设只有8个考生，分数 在0到5分之间。这8个考生的成绩我们放在一个数组A[8]中，它们分别是:2，5，3，0，2，3，0，3。考生的成绩从0到5分，我们使用大小为6的数组C[6]表示桶，其中下标对应分数。不过，C[6]内存储的并不是考生，而是对应的考生个数。像我刚刚举的那个例 子，我们只需要遍历一遍考生分数，就可以得到C[6]的值。
分数为3分的考生有3个，小于3分的考生有4个，所以，成绩为3分的考生在排序之后的有序数组R[8]中，会保存下标4，5，6的位置。
我们对C[6]数组顺序求和，C[6]存储的数据就变成了下面这样子。C[k]里存储小于等于分数k的考生个数。
我们从后到前依次扫描数组A。比如，当扫描到3时，我们可以从数组C中取出下标为3的值7，也就是说，到目前为止，包括自己在内，分数小于等于3的考生有7个，也就是说3是数组R中的第7个元素(也就是数组R中下标为6的位置)。当3放入到数组R中后，小于等于3的元素就只剩下了6个了，所以相应的C[3]要减1， 变成6。
以此类推，当我们扫描到第2个分数为3的考生的时候，就会把它放入数组R中的第6个元素的位置(也就是下标为5的位置)。当我们扫描完整个数组A后，数 组R内的数据就是按照分数从小到大有序排列的了。
基数排序(Radix sort)
假设我们有10万个手机号码，希望将这10万个手机号码从小到大排序，你有什么比较快速的排序方法呢?
桶排序、计数排序能派上用场吗?手机号码有11位，范围太大，显然不适合用这两 种排序算法。针对这个排序问题，有没有时间复杂度是O(n)的算法呢?现在我就来介绍一种新的排序算法，基数排序。
这个问题里有这样的规律:假设要比较两个手机号码a，b的大小，如果在前面几位中，a手机号码已经比b手机号码大了，那后面的几位就不用看了。
先按照最后一位来排序手机号码，然后，再按照倒数第二位重新排序，以此类推，最后按照第一位重新排序。
经过11次排序之后，手机号码就都有序了。 手机号码稍微有点长，画图比较不容易看清楚，我用字符串排序的例子，画了一张基数排序的过程分解图，你可以看下。
这里按照每位来排序的排序算法要是稳定的，否则这个实现思路就是不正确的。因为如果是非稳定排序算法，那最后一次排序只会考虑最高位的大小顺 序，完全不管其他位的大小关系，那么低位的排序就完全没有意义了。
根据每一位来排序，我们可以用刚讲过的桶排序或者计数排序，它们的时间复杂度可以做到O(n)。如果要排序的数据有k位，那我们就需要k次桶排序或者计数排 序，总的时间复杂度是O(k*n)。当k不大的时候，比如手机号码排序的例子，k最大就是11，所以基数排序的时间复杂度就近似于O(n)。
实际上，有时候要排序的数据并不都是等长的，比如我们排序牛津字典中的 万个英文单词，最短的只有 个字母，最长的我特意去查了下，有 个字母，中文翻 译是尘肺病。对于这种不等长的数据，基数排序还适用吗?
实际上，我们可以把所有的单词补齐到相同长度，位数不够的可以在后面补“0”，因为根据ASCII值，所有字母都大于“0”，所以补“0”不会影响到原有的大小顺 序。这样就可以继续用基数排序了。
