13、线性排序

思考：如何根据年龄给 100 万用户数据排序？

主要内容

今天讲解的是时间复杂度为 O(n) 的，所以也称为线性排序算法

桶排序（Bucket sort）

定义

核心思想：将数据分到几个桶内，先在桶内进行快速排序，之后再顺序取出桶内的数据，组成的数据就是有序的了

时间复杂度推导：将 n 个数据，分到 m 个桶内，则每个桶内数量为 k = n/m，然后每个桶进行快排，其时间复杂度为 O(k logk)，那 m 个桶则为 O(m k logk)，将 k = n/m 带入可得 O(n log(n/m))
当桶的数量 m 接近 n 时，log(n/m) 是一个非常小的常数，所以时间复杂度就接近 O(n)

限制

对数据要求很高，首先要能很容易的划分出 m 个桶，并且桶之间要求有顺序，这样桶内排序后，直接可组合，无需桶与桶的数据再排序
其次要求各桶内数据均匀，若不均匀(都在一个桶内)则可能退化为 O(n * log(n/m)) = O(nlogn)

场景

适合用于数据存储在外部磁盘中并且量大，然后运行内存有限，无法加载所有数据的情况。

比如：有 10GB 的订单数据，我们希望按订单金额（假设金额都是正整数）进行排序，但是我们的内存有限，只有几百 MB，没办法一次性把 10GB 的数据都加载到内存中。这个时候该怎么办呢？

先扫描订单数据，获得金额最小、最大值，然后根据这两个值创建 10 个桶，存入对应的金额订单，若某个桶数据太多了，则在这个桶内继续分桶，直到运行内存能读取每一个桶内的数据。分桶完毕后就依次读取桶内数据，进行桶内快排，最后再组合写入到一个文件中即可。

计数排序（Counting sort）

定义

本质是桶排序的特殊情况，桶大小的颗粒度更小。
核心思想：若数据的范围不大，最大的为 k 时，则将数据分到 k 个桶内，每个桶内的数据值是相等的，省掉了桶内排序的时间。

举例：省内有 50 万考生，如何在分数查询时显示排名

高考成绩的范围为[0，900]，则可以分为 901 个桶，对应 0 到 900 分，这样每个桶内都是一样的分数，所以桶内不需要排序。然后依次遍历每个桶，将数据依次放入一个总排名的数组中。
时间复杂度推导：将 n 个数据，分到 m 个桶内，则每个桶内数量为 k = n/m，但桶内不需要排序了。然后又依次遍历 m 个桶，将桶内的 k 个数据拿出来，所以只涉及到拿数据，拿的数据量为 m k，所以为 O(m k)，代入 k = n/m，则最终为 O(n)

核心逻辑为：原始数组 A 中找到最大值 k，创建长度为 k+1 的中间数组 C，C 内先存储 A 中每个值的数量。然后再存储累加的数量。最后基于 A.length 创建结果数组 R，然后倒序遍历 A，将 A[i] 作为 C 的下标，取出 C[A[i]] 的值 CValue，然后作为 R 的下标存储对应的 A[i]，即 R[CValue - 1] = A[i]，然后对 CValue 减一

使用 计数排序 实现 2，5，3，0，2，3，0，3 升序操作

function countingSort(list) {
  const len = list.length;

  if (len <= 1) return list;

  let max = list[0];

  for (let i = 1; i < len; i++) {
    if (list[i] > max) max = list[i]; // 找到最大值
  }

  const cArray = new Array(max + 1); // 基于[最大值+1]创建数组 cArray

  for (let i = 0; i <= max; i++) cArray[i] = 0; // 给 cArray 赋初值 0

  for (let i = 0; i < len; i++) { // 循环原始数组
    cArray[list[i]]++; // 将原始数据的每个值的数量放入 cArray 中
  }

  for (let i = 1; i <= max; i++) { // 循环 cArray
    cArray[i] = cArray[i - 1] + cArray[i]; // 累加
  }

  const rArray = new Array(len); // 基于 list 的长度创建数组 rArray

  // ⭐️ 计算排序的关键步骤，有点难理解
  for (let i = len - 1; i >= 0; i--) { // 倒序循环原始数组
    const cValue = cArray[list[i]];
    rArray[cValue - 1] = list[i];
    cArray[list[i]] = cValue - 1;
  }

  return rArray;
}

const sortArray = countingSort([2, 5, 3, 0, 2, 3, 0, 3]);
console.log("[ sortArray ] >", sortArray); // [0, 0, 2, 2, 3, 3, 3, 5]

限制

不适合最大值 K 大于 数据量 n 很多的，并且只适合非负整数排序

基数排序（Radix sort）

定义

核心思想：将要排序的数据，按照低位到高位一位位的进行排序，要符合“稳定”

限制

首先数据可以分割出“位”并且“位”数不能太大，其次“位”之间有递进关系，最后每一位的范围也不能太大，可以用线性排序(桶排序、计数排序)
要求：每个数据的长度要一致
这样的时间复杂度为 O(n)

场景

比如：10 万个手机号排序
手机号总共可以分为 11 位，每一位范围为[0~9]，其次最前面的位等级越高，比如前几位为 138 的就已经比 134 的高了

解答思考

思考：如何根据年龄给 100 万用户数据排序？
年龄为[13]位数，每位数范围为[09]，所以可以用基数排序
年龄最大值为 1**，远小于数量 n，也可以用计数排序

内容总结

桶、计数、基数排序对数据有要求，实际使用少，但有场景时可使用，毕竟时间复杂度低，为 O(n)

新的思考

假设我们现在需要对 D，a，F，B，c，A，z 这个字符串进行排序，要求将其中所有小写字母都排在大写字母的前面，但小写字母内部和大写字母内部不要求有序。比如经过排序之后为 a，c，z，D，F，B，A，这个如何来实现呢？如果字符串中存储的不仅有大小写字母，还有数字。要将小写字母的放到前面，大写字母放在最后，数字放在中间，不用排序算法，又该怎么解决呢？
仅排序大小写字符时：
使用 a、b 两个指针，a 从前往后，b 从后往前，a 遇到大写字母停下，b 遇到小写字母停下，都停下后就交换 a、b，然后继续指针 a、b 相交。

 function sortChars(str) {
  let a = 0;
  let b = str.length - 1;

  while (a < b) {
    while (a < b && /[a-z]/.test(str[a])) {
      a++; // 移动指针a，直到找到大写字母或者到达字符串尾部
    }
    while (a < b && /[A-Z]/.test(str[b])) {
      b--; // 移动指针b，直到找到小写字母或者到达字符串头部
    }

    // 当 a 和 b 都停下来时，交换它们指向的字符
    if (a < b) {
      [str[a], str[b]] = [str[b], str[a]]; // 使用解构赋值进行交换
      a++;
      b--;
    }
  }

  return str.join("");
}

排序大小写字符、数字时：
现将数据分为两类：小写字母与非小写字母，还是使用 a、b 两个指针，进行交换。完成后又将非小写字母的数据分为两类：大写字母与数字，然后重新使用 a、b 两个指针，进行交换