数据结构与算法之线性排序

线性排序的三大排序算法：桶排序、计数排序、基数排序

这三个算法都不是基于比较的排序算法，所以能做到线性的时间复杂度。

---

一、桶排序
适用场景：适合在外部磁盘中使用。
时间复杂度：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]
    }

---

三、基数排序
把一组数据，先补全到相同的位数，然后切割出“位”来一 一比较，要使用稳定的排序算法，即相同大小的位，先后顺序不能变。

例：

（完）