排序（3）-线性排序
在前面两节中我们介绍了时间复杂度为O(n2)和O(nlogn)的排序算法，它们都是基于比价的排序算法。在这一节我们介绍时间复杂度为O(n)的非基于比较的排序算法：桶排序、计数排序、基数排序。非基于比较，是指算法内部不涉及（较少涉及）元素之间的比较操作。
这种算法的时间复杂度比较低，但是对数据有额外的要求。所以我们还需要学习这些排序算法的适用场景。
桶排序（Bucket sort）
桶排序需要用到“桶”，核心思想是将数据分配到有序的桶中，再在桶内进行排序。桶内排序完成后，再把每个桶里的数据按照顺序取出，它们组成的序列就是有序的了。
桶排序.jpg
桶排序的分析：
性能：
- 稳定性：在桶内使用稳定的排序算法，桶排序就可以是稳定的。
- 空间复杂度：O(n)
- 时间复杂度：假设要排序的数据有 n 个，将他们均匀地分配到 m 个桶内，每个桶内就有k=n/m个元素。在桶内使用快速排序，时间复杂度为O(klogk)。m个桶的复杂度为O(m*klogk),也就是O(n*log(n/m))。当 n/m 确定，log(n/m)近似可看为一个常量。这时时间复杂度为O(n)。
应用条件
桶排序看起来很优秀，但是却无法代替之前我们说过的排序算法，因为桶排序对要排序的数据的要求非常苛刻：
- 首先，要很容易地选取桶存放数据的范围，且桶与桶之间要有顺序关系，这样从桶中取出的数据就不必再排序。
- 其次，要排序的数据需要很容易且均匀地分配到桶中。如果桶内数据不均匀，在极端条件下将会退化成O(nlogn)的排序算法。
- 如果面临桶内数据庞大的情况，我们可以选择再在桶内进行桶排序。
- 最后，桶排序比较适合在外部排序中。
有时候我们会遇到这种情况：排序数据的数据量非常庞大，内存有限，以至于无法将所有数据完全装入内存。面临这样的问题，我们必须借助外部磁盘完成存储排序，这种排序方式就叫外部排序
计数排序（Counting sort）
当排序数据所处的范围不大的时候，我们可以使用计数排序进行排序。计数排序的思想和桶排序的思想大致相同，你甚至可以认为计数排序是桶排序的一种特殊情况：
当 n 个数据所处的范围不大，比如最大值为 k 的时候，我们可以将数据分成 k 个桶，每个桶内的数据都是相同的，这样省去了桶内排序的时间。
你会发现，数值为 x 的桶内放入了所有值为 x 的数据，如果你对这些数据进行计数，就可以很容易地得到数值为 x 的数据的个数。是不是觉得这种思想和计数器很像呢？没错，这就是计数排序中计数的由来。
这里我们举个例子：假设有 8 名考生参加考试，考试分数为 0~5，我们将这八名考生的成绩放在一个数组 A[8] 中，他们分别是 ： 2，5，3，0，2，3，0，3。
使用数组 C[6] 进行计数，其中下标对应分数，数值对应考生的个数，我们通过一遍遍历就很容易得到 C[6] :
计数排序中的c数组.jpg
如果我们使用 R[8] 作为排序后的数组，C[3] 在 R 中的含义可以表示如下：
计数排序的排序数组.jpg
OK，现在我们得到了计数，那么如何对数据进行排序呢？（如何构造一个完整正确的 R[8] 数组呢？）处理的方法非常巧妙，你需要多看几遍：
首先我们将 C[6] 数组编程累加数组，此时 C[k] 的数据是 小于等于 k 分的考生的个数：
计数排序中的c_累加数组.jpg
你可以将这个图和 R[8] 结合着看（注意，此时我们还没有构造 R 数组，但是你要直到累加 C[6] 数组在 R 数组中的含义）。
现在，我们从后往前扫描数组A。例如，当扫描到 3 时，查询 C[3]=7（这代表当前扫描到的 3 排名第七），我们对这个 -1 ，就可以得到这个数据排序后的位置，6（数组从 0 开始计数）,所以我们将 R[6] 设置为 3 ，随后对计数数组 C[3] 进行 -1 操作。
以此类推，我们从后往前扫描完成 数组A ，同时我们构造完成了排序后的数组 R ：
计数排序的排序构造.jpg
下面是老师给出的代码：
// 计数排序，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];
}
}
计数排序的分析
性能
- 稳定性：如果你按照上文给出的思路实现，那么排序是稳定的。
- 空间复杂度：排序数组 R 保存了和 A 相同的数据量，空间复杂度为O(n)。
- 时间复杂度：我们只需要有限次遍历 A 就可以完成排序，时间复杂度为O(n)。
应用场景
- 计数排序只能用在数据范围不大的场景中，例如对高考成绩进行排序，我们只需要750个计数的“桶”。
- 计数排序只能对非负整数进行排序，如果数据存在小数或负数，则需要对数据预先进行处理，将数据转为非负整数。例如：数据保留一位小数，则对数据先乘以10；如果数据存在负数，则对所有数据预先加 最小值的绝对值，将所有数转为非负数。
基数排序（Radix sort）
先思考一个应用场景：请对100万个手机号码进行排序。
分析：手机号码有11位，由于这样的数据范围，显然难以使用桶排序和计数排序完成，这时我们就需要使用基数排序完成。
为了方便，我们举个例子：398 和 752 比较，他们的最高位为 3 和 7 ，仅仅用最高位的比较我们就可以得到两个数的大小。记住这个性质，当待排序的数据具有这个特点的时候我们就可以考虑使用基数排序。
注意，我们从最高位往最低位进行比较，上面的性质是数学性质。但是编码过程不能从前往后，你可以尝试一下，你会发现其中的错误。综上，我们需要从后往前进行比较。
还记得在介绍排序算法中的稳定性的意义时的购物单排序的例子吗？沿用相同的思路，我们对电话从最后开始排序，然后对倒数第二位排序，以此类推，直到第一位排序完成。下面给一个字符串排序的例子：
基数排序.jpg
注意：这里按位排序的算法需要是稳定的，否则排序顺序仍然是混乱的。
基数排序的分析
性能
- 稳定性：基数排序是稳定的，同时我们对每一位的排序算法也要是稳定的。
- 空间复杂度：对空间复杂度的分析，要涉及对 每一位排序算法 的分析，一般来说，我们使用桶排序或者计数排序作为 对每一位排序 的排序算法，所以基数排序的空间复杂度和它们的复杂度相同。
- 时间复杂度：如上一条所述，对每一位的排序，我们使用桶排序或者计数排序，它们的时间复杂度可以达到O(n)，如果数据有 k 位，则我们要进行 k 次桶排序或计数排序，总体的时间复杂度为O(k*n)。当 k 不大的时候，（例如手机号是 11 位）基数排序的时间复杂度近似于O(n)。
应用场景
- 需要排序的数据可以被分割出独立的位，而且位之间有递进的关系。
- 每一位的数据范围不要太大，因为对位的排序我们使用线性排序算法来进行，否则基数排序的时间复杂度会上升。
- 如果数据的位数不同，我们可以在数据前方进行 “补0” 操作。
总结
我们学习了三种线性时间复杂度的排序算法：桶排序、计数排序、基数排序。他们对于数据有比较苛刻的要求，所以应用范围有限。
桶排序和计数排序的思想很像，都是针对范围不大的数据。将数据划分成为不同范围的桶来实现。
基数排序要求数据可以划分高低位，同时高低位之间要有递进关系。在基数排序中，我们需要借助桶排序或者计数排序来完成 位的排序工作。
以上就是线性排序算法的所有内容。
注：本文章的主要内容来自我对极客时间app的《数据结构与算法之美》专栏的总结，我大量引用了其中的代码和截图，如果想要了解具体内容，可以前往极客时间
