上两节中，我带你着重分析了几种常用排序算法的原理、时间复杂度、空间复杂度、稳定性等。今天，我会讲三种时间复杂度是O(n)的排序算法：桶排序、计数排序、基数排序。
因为这些排序算法的时间复杂度是线性的，所以我们把这类排序算法叫作线性排序（Linear sort）。之所以能做到线性的时间复杂度，主要原因是，这三个算法是非基于比较的排序算法，
都不涉及元素之间的比较操作。
这几种排序算法理解起来都不难，时间、空间复杂度分析起来也很简单，但是对要排序的数据要求很苛刻，所以我们今天学习重点的是掌握这些排序算法的适用场景。
按照惯例，我先给你出一道思考题：如何根据年龄给100万用户排序？
你可能会说，我用上一节课讲的归并、快排就可以搞定啊！是的，它们也可以完成功能，但是时间复杂度最低也是O(nlogn)。有没有更快的排序方法呢？让我们一起进入今天的内容！
桶排序的时间复杂度为什么是O(n)呢？我们一块儿来分析一下。
答案当然是否定的。为了让你轻松理解桶排序的核心思想，我刚才做了很多假设。实际上，桶排序对要排序数据的要求是非常苛刻的。
首先：
其次：
桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。
比如说我们有10GB的订单数据：
现在我来讲一下，如何借助桶排序的处理思想来解决这个问题。
我们可以先扫描一遍文件，看订单金额所处的数据范围。假设经过扫描之后我们得到，订单金额最小是1元，最大是10万元。
理想的情况下：
不过，你可能也发现了，订单按照金额在1元到10万元之间并不一定是均匀分布的 ，所以10GB订单数据是无法均匀地被划分到100个文件中的。
有可能某个金额区间的数据特别多，划分之后对应的文件就会很大，没法一次性读到内存。这个该怎么办呢？
def bucket_sort(li, n=100, max_num=10000):
buckets = [[] for _ in range(n)] # 创建桶
for var in li:
i = min(var // (max_num // n), n-1) # i 表示var放到几号桶里
buckets[i].append(var) # 把var加到桶里边
# 保持桶内的顺序
for j in range(len(buckets[i])-1, 0, -1):
if buckets[i][j] < buckets[i][j-1]:
buckets[i][j], buckets[i][j-1] = buckets[i][j-1], buckets[i][j]
else:
break
sorted_li = []
for buc in buckets:
sorted_li.extend(buc)
return sorted_li
图解代码
我个人觉得，计数排序其实是桶排序的一种特殊情况。当要排序的n个数据，所处的范围并不大的时候，比如最大值是k，我们就可以把数据划分成k个桶。每个桶内的数据值都是相同的，
省掉了桶内排序的时间。
我们都经历过高考，高考查分数系统你还记得吗？我们查分数的时候，系统会显示我们的成绩以及所在省的排名。如果你所在的省有50万考生，如何通过成绩快速排序得出名次呢？
计数排序的算法思想就是这么简单，跟桶排序非常类似，只是桶的大小粒度不一样。不过，为什么这个排序算法叫“计数”排序呢？“计数”的含义来自哪里呢？
想弄明白这个问题，我们就要来看计数排序算法的实现方法。我还拿考生那个例自来解释。为了方便说明，我对数据规模做了简化。假设只有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的考生个数。
有了前面的数据准备之后，现在我就要讲计数排序中最复杂、最难理解的一部分了，请集中精力跟着我的思路！
以此类推，当我们扫描到第2个分数为3的考生的时候，就会把它放入数组R中的第6个元素的位置（也就是下标为5的位置）。
当我们扫描完整个数组A后，数组R内的数据就是按照分数从小到大有序排列的了。
上面的过程有点复杂，我写成了代码，你可以对照着看下。
// 计数排序，a是数组，n是数组大小。假设数组中存储的都是非负整数。
public void countingSort(int[] a, int n) {
if (n <= 1) return;
// 查找数组中数据的范围
int max = a[0];
for (int i = 1; i < n; ++i) {
if (max < a[i]) {
max = a[i];
}
}
int[] c = new int[max + 1]; // 申请一个计数数组c，下标大小[0,max]
for (int i = 0; i <= max; ++i) {
c[i] = 0;
}
// 计算每个元素的个数，放入c中
for (int i = 0; i < n; ++i) {
c[a[i]]++;
}
// 依次累加
for (int i = 1; i <= max; ++i) {
c[i] = c[i-1] + c[i];
}
// 临时数组r，存储排序之后的结果
int[] r = new int[n];
// 计算排序的关键步骤，有点难理解
for (int i = n - 1; i >= 0; --i) {
int index = c[a[i]]-1;
r[index] = a[i];
c[a[i]]--;
}
// 将结果拷贝给a数组
for (int i = 0; i < n; ++i) {
a[i] = r[i];
}
}
这种利用另外一个数组来计数的实现方式是不是很巧妙呢？这也是为什么这种排序算法叫计数排序的原因。不过，你千万不要死记硬背上面的排序过程，重要的是理解和会用。
def count_sort(li, max_count=100):
count = [0 for _ in range(max_count+1)]
for val in li:
count[val] += 1
li.clear()
for ind, val in enumerate(count):
for i in range(val):
li.append(ind)
我总结一下，计数排序只能用在数据范围不多的场景中：
比如，还是拿考生这个例子。如果考生成绩精确到小数后一位，
我们再来看这样一个排序问题。假设我们有10万个手机号码，希望将这10万个手机号码从小到大排序，你有什么比较快速的排序方法呢
我们之前讲的快排，时间复杂度可以做到O(nlogn)，还有更高效的排序算法吗？桶排序、计数排序能派上用场吗？手机号码有11位，范围太大，显然不适合用这两种排序算法。
针对这个排序问题，有没有时间复杂度是O(n)的算法呢？现在我就来介绍一种新的排序算法，基数排序。
刚刚这个问题里有这样的规律：假设要比较两个手机号码a，b的大小，如果在前面几位中，a手机号码已经比b手机号码大了，那后面的几位就不用看了。
手机号码稍微有点长，画图比较不容易看清楚，我用字符串排序的例子，画了一张基数排序的过程分解图，你可以看下。
注意，这里按照每位来排序的排序算法要是稳定的，否则这个实现思路就是不正确的。因为如果是非稳定排序算法，那最后一次排序只会考虑最高位的大小顺序，完全不管其他位的大小关系，
那么低位的排序就完全没有意义了。
实际上，有时候要排序的数据并不都是等长的，比如我们排序牛津字典中的20万个英文单词，最短的只有1个字母，最长的我特意去查了下，有45个字目，中文翻译是尘肺病。
对于这种不等昌的数据，基数排序还适合吗？
实际上，我们可以把所有的单词补齐到相同长度，位数不够的可以在后用补“0”，因为根据ASCII值，所有字母都大于“0”，所以补“0”不会影响到原有的大小顺序。这样就可以继续用基数排序了。
我来总结一下：
def radix_sort(li):
max_num = max(li) # 最大值 9->1, 99->2, 888->3, 10000->5
it = 0 #迭代的次数(分桶-顺序输出)
while 10 ** it <= max_num:
buckets = [[] for _ in range(10)]
for var in li:
# 987 it=1 987//10->98 98%10->8; it=2 987//100->9 9%10=9
digit = (var // 10 ** it) % 10
buckets[digit].append(var)
# 分桶完成
li.clear()
for buc in buckets:
li.extend(buc)
# 把数重新写回li
it += 1
1、循环的次数由最大值确定
最大值 9->1, 99->2, 888->3, 10000->5
2、建桶、分十个桶
3、放到几号桶 取余运算
987 it=1 987//10->98 98%10->8; it=2 987//100->9 9%10=9
今天的内容学完了。我们再回过头来看看开篇的思考题：如何根据年龄给100万用户排序？现在思考题是不是变得非常简单了呢？我来说一下我的解决思路。
实际上，根据年龄给100万用户排序，就类似按照成绩给50万考生排序。
今天，我们学习了3种线性时间复杂度的排序算法，有桶排序、计数排序、基数排序。它们对要排序的数据都有比较苛刻的要求，应改不是非常广泛。
但是如果数据特征比较符合这些排序算法的要求，应用这些算法，会非常高效，线性时间复杂度可以达到O(n)。
桶排序和计数排序的排序思想是非常相似的，都是针对范围不大的数据，将数据划分成不同的桶来实现排序。基数排序要求数据可以划分成高低位，位之间有递进关系。比较两个数，
我们只需要比较高位，高位相同的再比较低位。而且每一位的数据范围不能太大，因为基数排序算法需要借助桶排序或者计数排序来完成每一个位的排序工作。
我们今天讲的都是针对特殊数据的排序算法。实际上，还有很多看似是排序但又不需要使用排序算法就能处理的排序问题。
假设我们现在需要对D，a，F，B，c，A，z这个字符串进行排序，要求将其中所有小写字目都排在大写字母的前面，但小写字母内部和大写字母内部不要求有序。
比如经过排序之后为a，c，z，D，F，B，A，这个如何来实现呢？如果字符串中存储的不仅有大小写字母，还有数字。要将小写字母的放到前面，大写字母放在最后，数字放在中间，
不用排序算法，又该怎么解决呢？
课后思考，利用桶排序思想，弄小写，大写，数字三个桶，遍历一遍，都放进去，然后再从桶中取出来就行了。相当于遍历了两遍，复杂度O(n)
原文：https://www.cnblogs.com/luoahong/p/11850680.html