线性排序（Linear sort），指的是 时间复杂度为 O(n) 的排序算法。之所以时间复杂度能达到线性，是因为这种排序不是基于比较的，但它的适用场景也有很大的局限性。
线性排序有三种：桶排序、计数排序、基数排序。
复杂度总结
| 排序算法 | 时间复杂度 | 空间复杂度 | 是否稳定 |
|---|---|---|---|
| 桶排序 | O(n) | O(n) | 稳定 |
| 计数排序 | O(n) | O(n+k) | 稳定 |
| 基数排序 | O(k*n) | O(n) | 稳定 |
桶排序
桶排序（Bucket sort），顾名思义，就是用很多桶来存放元素。这里的桶其实是一个区间，一个用来存放在某个数值范围内的元素。比如一个 0-9 的桶表示存放数值大于等于0，小于等于9的元素。
我们有 n 个元素，m 个 桶，假设数据很均匀地放到每个桶里面，每个桶就是 k = n/m 个元素，每个桶进行快速排序，时间复杂度是 O(klogk)，那 m 个桶的时间复杂度是 O(m * klogk)，即 O(nlog(n/m))。当 m 接近于 n 时，n/m 就是一个很小的常量，这样时间复杂度就是 O(n) 了。
根据前面时间复杂度的推导，我们会发现，可以进行桶排序的场景要求很高。
首先，它要求数据可以较为均匀地分布到每个桶里。假如某些桶的数据相比其它桶非常少，其实等同于将它被合并放到另一个桶里，本质就是少了一个桶，m 就会变小，n/m 就会接近于 n。一种极端情况下，数据全放到一个桶里，时间复杂度就退化为 O(nlogn)。
虽然一般情况下，能用桶排序的场景比较少，但有一种场景就很适合桶排序，那就是 外部排序。
外部排序（External sorting）是指能够处理极大量数据的排序算法。通常外部排序会用到外存。在数据量很大，内存无法一次全部读取的情况下，就需要用到外部排序。除了可以用 桶排序，我们还可以用 归并排序 来做外部排序。
假设我们有一个很大的文件，里面保存了很多数据，要对它们进行排序，具体做法是：
- 扫描大文件的数据得到数值范围，确定合适的桶的数量（保证 n/m 的数据量可以一次读入到内存中）。这里的桶会对应一个个小文件。
- 从头往后扫描大文件，将数据按照范围放到小文件中。
- 每个小文件的数据全部读取到内存中，进行排序。这里注意使用的排序算法是否为原地排序，且是否为稳定排序。具体根据实际情况进行选择合适的排序算法。另外，如果小文件里的数据（一般来说是数据分布不均匀导致的）仍不能一次读取到内存中，可以对小文件继续进行拆分，得到第二小文件。
- 按顺序合并多个小文件为一个大的文件。
代码实现
暂无实现。
算法分析
1. 桶排序不是原地排序
因为我们需要创建多个桶，需要额外的内存空间，桶如果是用数组实现，理论上是创建要 m 个 长度为 n 大小的数组。不过一般来说不会这样做，我们会考虑使用链表、动态数组、跳表和红黑树等动态数据结构来保存。桶排序的空间复杂度我们可以大概说成是 O(n) 。
2. 桶排序是稳定的排序
其实桶排序是否稳定，是取决于桶内部使用的排序算法，如果使用的是一种稳定的排序算法，那这种桶排序算法就是稳定的排序算法。
3. 桶排序的时间复杂度是 O(n)
桶排序的时间复杂度是 O(n) 是有前提条件的，那就是桶的数量 m 接近于 n，且数据要尽量均匀分布。极端情况下所有的数据都放到一个桶里，此时桶排序的时间复杂度就会退化为 桶内部使用的排序算法 的时间复杂度。
计数排序
计数排序不好理解，因为脑子要拐几个弯。
当数据有大量重复时，且都为正整数时，我们可以考虑使用计数排序。
计算排序算是比较特殊的桶排序，因为它的桶只有一种值。假设一组数据的最大值为 k，那我们就分为 k 个桶。
首先我们遍历原数组，用数组 c 统计每个值出现的次数，然后我们在让数组 c 的数组元素和前面的元素累加，即 c[1] = c[0] + c[1], c[2] = c[2] + c[1], ...。这样得到了新的数组 c ，此时数组元素 c[i] 表示的就是原数组中小于等于 i 的数据的个数。
然后我们从后往前遍历原数组，将元素的数值 v 找到数组 c 中对应索引的值。这个值 c[v] 代表原数组中小于等于 v 的数据个数。又因为我们是从后往前遍历数组，所以当前的原数组的元素就是排序后的第 c[v] 个元素。于是我们就把这个元素放到一个新开的空数组 r 的第 v 个位置。另外我们不要忘记 c[v]自减一，因为我们已经取走了一个数，小于等于 v 的数据的个数也要跟着减1。
遍历完后，r就是我们要的排序好的数组了。
代码实现
const countingSort = (a) => {
// 找出数组的最大的数。
let i, max = a[0];
for (let i = 1; i < a.length; i++) {
if (a[i] > max) {
max = a[i];
}
}
let c = [];
for (i = 0; i <= max; i++) {
c[i] = 0;
}
for (i = 0; i < a.length; i++) {
c[a[i]]++;
}
console.log('数组C（值表示小于等于索引的数量）：', c.toString());
// 计数累加
for (i = 1; i < c.length; i++) {
c[i] = c[i - 1] + c[i];
}
// 从后往前扫描 数组a（从后往前可以保证是 稳定 排序）
let r = [];
for(i = a.length - 1; i >= 0; i--) {
let index = c[a[i]] - 1;
// 为什么要减1？？
// 因为 c[] 记录的是小于等于索引的元素数量，比如小于等于 3 的有 4个，
// 所以 3 必然是这第4个（索引对应3，所以要减1）。
// 你会说小于等于并不是等于啊，但我们现在是正在遍历原数组，且确实发现有这个 3 了。
r[index] = a[i];
c[a[i]]--;
}
return r;
}
算法分析
1. 计数排序不是原地排序算法
计数排序使用了额外的两个数组（数组 c 和 数组 r），他们的长度分别为 k 和 n，所以空间复杂度是 O(k+n)，所以 线性排序不是原地排序算法。
2. 计数排序是稳定的排序算法
不过线性排序是 稳定 的排序算法，因为它没有进行元素的交换。
3. 计数排序的时间复杂度是 O(n)
这个毫无疑问时间复杂度是 O(n)，当然也可以说时间复杂度是 O(n+k)，只是前面的被省略的系数发生了变化。
另外，计数排序的局限性还是挺大的，首先计数排序只能用在 数据范围不大的场景 中，因为数据范围越大（尤其是 k 远大于 n 的情况），需要创建的两个数组长度也越长。此外因为要用到数组的索引，所以只能对 非负整数 进行排序，当然我们可以对不符合情况的数据进行一些处理（不改变相对大小），转换为非负数。比如对于小树，可以乘以 10 的倍数，有负整数则可以每个数据加相同大小的值，使负整数变成非负整数。
基数排序（Radix sort）
较短的数值前面补0，从右往左 每一位 上的数进行排序，直到最高位。
基数排序的对比排序是基于 位的，我们想要基数排序的时间复杂度为 O(n)，那每一位的排序都必须是线性排序，网上比较常见的是配合桶排序的基数排序（我也不知道为什么反正我配合使用的是计数排序）。
代码实现
const radixSort = (a) => {
// 从低到高排序
// 位数拆分
let i, tmp = [];
const size = 11; // 正数的位数
let radix = 1;
for (let j = 0; j < size; j++) {
for (i = 0; i < a.length; i++) {
let k = Math.floor(a[i] / radix) % 10 // 获取j位上的值。
tmp[i] = k;
}
a = cSInRadixSort(tmp, a);
radix *= 10;
// console.log(a.toString());
// 计数排序一下。（要专门为基数排序写一个计数排序，因为排序的是 a，而不是 tmp）
// return c
}
return a;
}
/**
* // 基数排序专用的 计数排序
* @param {Array} a 提炼出的某位上的值
* @param {Array} o 原数组
*/
const cSInRadixSort = (a, o) => {
// 找出数组的最大的数。
let i, max = a[0];
for (let i = 1; i < a.length; i++) {
if (a[i] > max) {
max = a[i];
}
}
let c = [];
for (i = 0; i <= max; i++) {
c[i] = 0;
}
for (i = 0; i < a.length; i++) {
c[a[i]]++;
}
// console.log('数组C（值表示小于等于索引的数量）：', c.toString());
// 计数累加
for (i = 1; i < c.length; i++) {
c[i] = c[i - 1] + c[i];
}
// 从后往前扫描 数组a（从后往前可以保证是 稳定 排序）
let r = [];
for(i = a.length - 1; i >= 0; i--) {
let index = c[a[i]] - 1;
r[index] = o[i]; // 这里 的 a[i] 改成 o[i]
c[a[i]]--;
}
return r;
}
算法分析
1. 基数排序不是原地排序算法
因为它要配合一种线性排序算法（桶排序或计数排序），这些线性排序算法都需要额外内存空间。
2. 基数排序是稳定的排序算法
其实还是取决于和基数排序配合使用的线性排序算法的稳定性
3. 基数排序的时间复杂度是 O(k*n)
k 指的是数据最大值的位数。基数排序是基于 位 进行排序的，每次排序使用线性排序算法进行排序，时间复杂度是 O(n)，一共进行 k 次排序，所以时间复杂度是 O(k * n)
网友评论