前面我们已经分析了各种基于比较的排序算法，它们的最优时间复杂度为 O(nlogn)，这里要介绍三种非基于比较的排序算法，它们的时间复杂度为 O(n)，所以称之为线性排序。
桶排序（Bucket Sort）的核心思想是将要排序的数组直接放入到几个已经有序的桶里，然后再分别对桶里的数据进行排序，依次取出，即完成了整个排序过程。
桶排序队排序数据的要求非常严格：
- 数据能够简单的划分为 m 个桶，并且桶与桶之间天然有序。
- 数据在各个桶之间的分布比较均匀，极端情况下，所有数据都在一个桶里，则退化成基于比较的排序了。
所以，桶排序一般用于外部排序。比如说我们有 10G 的数据，无法一次装载到内存中，可以借助桶排序，先将 10G 的数据分到能装到内存中的桶里，再对桶里的数据进行排序，最后按桶输出为文件。
计数排序（Counting Sort）可以理解为桶排序的一种特殊情况。当我们能确定待排序元素的范围不大时（比如为从 0 到 K），则可以把数据划分为 K 个桶。于是每个桶内的数据都是相同的，无需桶内排序即可得到有序序列。
那么为什么计数排序要叫计数排序呢？这和它非常巧妙的实现过程有关。计数排序的步骤如下：
- 找出待排序的数组中最大和最小元素；
- 统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项；
- 对所有的计数累加（从 C 的第一个元素开始，每一项和前一项相加）；
- 反向（保证排序稳定性）填充目标数组：将每个元素 i 放到新数组的第 C[i] 项，同时将 C[i] 减去 1.
void count_sort(vector<int>& a) {
vector<int> bucket(K, 0);
for (auto i : a) {
bucket[i]++;
}
for (int i = 1; i < 10; ++i) {
bucket[i] += bucket[i-1];
}
vector<int> b(a.size());
for (int i = K-1; i >= 0; --i) {
int j = a[i];
b[bucket[j]-1] = j;
bucket[j]--;
}
swap(a, b);
}基数排序（Radix Sort）的原理是将整数按位数切割为不同的数字，然后按每个位数分别比较。具体来说：
基数排序将所有待比较数值统一为同样的数字长度，数字较短的数前面补零，然后，从最低位开始，依次进行稳定排序（非稳定排序就打乱了之前的顺序了），从最低位一直到最高位排序完成后，数列就变为一个有序数列。
基数排序对数据也是有要求的：
- 数据可以分割出独立的“位”来比较，而且位之间有递进的关系；
- 每一位的数据范围不能太大，要能够使用线性排序算法来排序，否则整体时间复杂度就无法做到 O(n) 了。