三种时间复杂度是 O(n) 的排序算法：桶排序、计数排序、计数排序。这些排序算法的时间复杂度是线性的，因而也叫线性排序。之所以能做到线性的复杂度，主要原因这三种算法都是非基于比较的排序算法，不涉及元素间的比较操作；但是这几种排序算法对数据的要求很苛刻，因而需要重点掌握它们的使用场景。
问题
如何根据年龄给100万用户排序？（时间复杂度最好要是线性的）
桶排序（Bucket sort）
核心原理
桶排序，顾名思义，会用到“桶”，这些“桶”，按区间划分，核心思想是将要排序的数据将其分到所属的桶里去，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就有序了。
为什么时间复杂度为 O(n)？
如果要排序的数据有 n 个，将其均匀地划分到 m 个桶内，每个桶里就有 k = n/m 个元素。每个桶内部用快速排序，时间复杂度就为 O(k * logk) 。 m 个桶排序的时间复杂度就是 O(m * k * logk)，又因为 k = n/m，所以整个桶排序的时间复杂度就是 O(n* logn/m)。当桶的个数 m 接近数据个数 n 时，logn/m 就是一个很小的常量，这个时候桶排序的时间复杂度接近 O(n)
对数据的苛刻要求
1 . 首先，要排序的数据需要很容易就能划分成 m 个桶，并且，桶与桶之间有着天然的大小顺序。这样每个桶内的数据都排序完之后，桶与桶之间的数据不需要再进行排序。
2 . 其次，数据在各个桶之间的分布是比较均匀的。如果数据经过桶的划分之后，有些桶里的数据非常多，有些非常少，很不平均，那桶内数据排序的时间复杂度就不是常量级了。在极端情况下，如果数据都被划分到一个桶里，那就退化为 O(nlogn) 的排序算法了。
适用场景
桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。
栗子
问题描述
有 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分。
#数组A8
数组 [2] [5] [3] [0] [2] [3] [0] [3]
下标 0 1 2 3 4 5 6 7
考生的成绩从 0 到 5 分，使用大小为 6 的数组 C[6] 表示桶，其中下标对应分数。 C[6] 中的每个元素存对应分数的考生个数。
#数组C6：
数组-出现次数： [2] [0] [2] [3] [0] [1]
下标-对应分数： 0 1 2 3 4 5
现在的问题是，如何快速计算出，每个分数的考生在有序数组 (最后排好序的结果数组) 中对应的存储位置呢？
巧妙的思路
1 . 首先对 C6 数组顺序求和（前面一个位置的值+当前自己本身的值 = 当前的新值），得到新的 C6 数组：
#新的数组C6：
数组-出现次数： [2] [2] [4] [7] [7] [8]
下标-对应分数： 0 1 2 3 4 5
2 . 然后从后到前依次扫描数组 A。
过程如下：扫描到第一个3时，从数组 C 中取出下标为3的值，即7， 7在这里的含义是，到目前位置，包括当前这个在内，小于等于3分的考生个数是7个，即3是结果数组 R 中的第7个元素（对应于数组下标为6的位置R[6] = 3）。将这个3放进 R 数组后，数组 C 中小于等于3的元素个数减一就变成6个，即 C[3] = 6。以此推类，扫描完整个数组A后，数组 R 内的数据就是按照分数从小到大有序排列。
过程图：
代码
from typing import List
import itertools
def counting_sort(a: List[int]):
if len(a) <= 1:return
counts = [0] * (max(a) + 1) #创建桶，初始值为0
for num in a: #统计数组中每个元素出现的次数
counts[num] += 1
counts = list(itertools.accumulate(counts)) #对counts数组顺序求和，得到新的counts数组
a_sorted = [0] * len(a) #创建一个临时结果数组，存储排序后的结果
for num in reversed(a): #从后往前扫描需要被排序的数组
index = counts[num] - 1 #找到num在临时结果数组中位置
a_sorted[index] = num #将num放到临时结果数组中
counts[num] -= 1 #num对应的个数减1
a = a_sorted #将临时结果数组赋给原数组
适用场景
计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。
栗子说明
比如，如果考生成绩精确到小数后一位，就需要将所有的分数都先乘以 10，转化成整数，然后再放到 9010 个桶内。再比如，如果要排序的数据中有负数，数据的范围是 [-1000, 1000]，那就需要先对每个数据都加 1000，转化成非负整数。
基数排序（Radix sort）
首先按照最低有效位进行排序，最低位优先 (Least Significant Digit first) 法，简称 LSD 法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。
应用
假设有 10 万个手机号码，希望将这 10 万个手机号码从小到大排序，什么排序方法比较快速？
手机号码有 11 位，范围太大，显然不适合用桶排序和计数排序两种算法，基数排序就很适合。
处理思路
先按照最后一位来排序手机号码，然后，再按照倒数第二位重新排序，以此类推，最后按照第一位重新排序。经过 11 次排序之后，手机号码就都有序了。
注意，这里按照每位来排序的排序算法要是稳定的，否则这个实现思路就是不正确的。因为如果是非稳定排序算法，那最后一次排序只会考虑最高位的大小顺序，完全不管其他位的大小关系，那么低位的排序就完全没有意义了。
根据每一位来排序，可以用桶排序或者计数排序，它们的时间复杂度可以做到 O(n)。如果要排序的数据有 k 位，那就需要 k 次桶排序或者计数排序，总的时间复杂度是 O(k*n)。当 k 不大的时候，比如手机号码排序，k 最大就是 11，所以基数排序的时间复杂度就近似于 O(n)。
实际上，有时候要排序的数据并不都是等长的。
解决办法
可以把所有的数字补齐到相同长度，位数不够的可以在前面补0。而对于不等长的字符串排序，位数不够的可以在后面补"0"，因为根据ASCII 值，所有字母都大于"0"，所以补"0"不会影响到原有的大小顺序。这样就可以继续用基数排序了。
代码
def radix_sort(lt, d): #d表示d轮排序,取决于数组元素的长度
for k in xrange(d):
s = [[] for i in xrange(10)] #创建10个桶，因为每位数字最大的就是9
#对数组中每个元素，按照最低有效数字进行排序，然后依次到高位
for i in lt:
s[i/(10**k)%10].append(i)
lt = [j for i in s for j in i]
return lt
例如
对数组[321,22,890]排序，第一轮对个位排，s[0]=[890],s[1]=[321],s[2]=[22]，第一轮排序结果lt[890,321,22]
第二轮对十位排，s[2] =[321,22],s[9]=[890]，第二轮排序结果lt[321,22,890]
第三轮百位排，s[0] =[22],s[3]=[321],s[8]=[890]，第三轮排序结果lt[22,321,890]，结束。
适用场景
基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果 a 数据的高位比 b 数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到 O(n) 了。
解答开篇
实际上，根据年龄给 100 万用户排序，就类似按照成绩给 50 万考生排序。
假设年龄的范围最小 1 岁，最大不超过 120 岁。
遍历这 100 万用户，根据年龄将其划分到120 个桶里，然后依次顺序遍历这 120 个桶中的元素。
这样就得到了按照年龄排序的 100 万用户数据。