线性排序的三大排序算法：桶排序、计数排序、基数排序
这三个算法都不是基于比较的排序算法，所以能做到线性的时间复杂度。
一、桶排序
适用场景：适合在外部磁盘中使用。
时间复杂度：O(n)
例子：现在有 1GB 的订单数据，希望按订单金额（10元，20元，40元。。）进行排序，但内存只有 200MB，无法一次性将 1GB 数据加载到内存中，如何处理？
（1）扫描文件得知：订单金额范围在 1 元和 1 万元之间。
（2）根据订单金额范围划分到 10 个桶里，即 1号桶（1-1000元 ），2号桶（1001-2000元），3号桶（2001-3000元）。。10号桶（9001-10000元）。
（3）理想情况下，每个桶大小为 100MB，利用 快速排序，将每个桶内的数据进行排序，然后依次读入内存中。
（4）不理想的情况下，某一个桶内的数据会特别多，那么这个桶就再分成小桶，快排，再读入内存中。
缺点：
（1）实际数据较难划分成 m 个桶，且桶与桶之间要有着天然的大小顺序
（2）各个桶之间的分布很难是均匀的
二、计数排序
描述：计数排序是桶排序的特殊情况
适用场景：要排序的数据，所处范围不大的情况
例子：查询所在省的高考成绩，该省有 50 万名考生，考生满分是 900 分，如何找到某一考生的排名？
将 0分，1分，2分。。900分的学生成绩，分别装进901个桶中，然后每个桶都进行快速排序，这样就能快速找到某一考生的成绩
计数排序算法的实现
例：现有8个学生，他们的成绩分别为 2、5、3、0、2、3、0、3 分，如何通过计数排序快速计算出他们的排名？
let array=[2,5,3,0,2,3,0,3]
let arrayMax=array[0]
//先获取原数组的最大值
for(let i=1;i<array.length;i++){
if(arrayMax<array[i]) arrayMax=array[i]
}
// console.log(arrayMax) //5
//根据原数组的最大值，定义计数数组的长度
//因为是把最大值当下标的，所以长度=max+1
let countArray=new Array(arrayMax+1)
//计数数组初始化
for(let i=0;i<countArray.length;i++){
countArray[i]=0
}
//计算原数组每个item的个数，并放入计数数组中
for(let i=0;i<array.length;i++){
// 原数组的item当做计数数组的下标
//值是item的个数
countArray[array[i]]++
}
// console.log(countArray) //[2, 0, 2, 3, 0, 1]
//依次累加计数数组的item，
// 即<=0分的个数，<=1分的个数。。<=5分的个数
for(let i=1;i<=arrayMax;i++){
countArray[i]=countArray[i]+countArray[i-1]
}
// console.log(countArray) //[2, 2, 4, 7, 7, 8]
let orderArray=new Array(array.length)
//计数排序的关键步骤==============
//从后往前循环
for(let i=array.length-1;i>=0;i--){
// array=[2,5,3,0,2,3,0,3]
// countArray=[2, 2, 4, 7, 7, 8]
//第一次循环是：array[6]=3，countArray[3]=7,countArray[3]-1=6
//查找array中的每个元素在countArray中出现的个数
let index=countArray[array[i]]-1
//当array[i]的数组放到orderArray中后，
// 小于等于array[i]的元素就只剩下index个了，
//所以countArray要相应减1
orderArray[index]=array[i]
countArray[array[i]]--
}
//===============================
// console.log(orderArray) //[0, 0, 2, 2, 3, 3, 3, 5]
//将结果赋值给原数组，完成计数排序
for(let i=0;i<array.length;i++){
array[i]=orderArray[i]
}
三、基数排序
把一组数据，先补全到相同的位数，然后切割出“位”来一 一比较，要使用稳定的排序算法，即相同大小的位，先后顺序不能变。
例：
（完）
网友评论