排序算法

算法概述

时间复杂度

一个算法的时间复杂度反映了程序运行从开始到结束所需要的时间。把算法中基本操作重复执行的次数（频度）作为算法的时间复杂度。

没有循环语句，记作O(1)，也称为常数阶。只有一重循环，则算法的基本操作的执行频度与问题规模 n 呈线性增大关系，记作O（n），也叫线性阶。

常见的时间复杂度有：

• O(1): Constant Complexity: Constant 常数复杂度
• O(log n): Logarithmic Complexity: 对数复杂度
• O(n): Linear Complexity: 线性时间复杂度
• O(n^2): N square Complexity 平⽅方
• O(n^3): N square Complexity ⽴立⽅方
• O(2^n): Exponential Growth 指数
• O(n!): Factorial 阶乘

空间复杂度

一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。

一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。

十大排序算法

1.算法分类

• 比较类排序

  • 通过比较来决定元素之间的相对次序，由于其时间复杂度不能突破 O(nlogn),因此也称为非线性时间比较类排序.

• 非比较类排序

  • 不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此也称为线性时间非比较类排序.

2.算法复杂度

3.相关概念

• 稳定: 如果 a 原本在 b 前面,而 a=b,排序之后 a 仍然在 b 前面.
• 不稳定: 如果 a 原本在 b 前面,而 a=b,排序之后 a 可能会出现在 b 的后面.
• 时间复杂度: 对排序数据的总的操作次数,反映当 n 变化时,操作次数呈现什么规律.
• 空间复杂度: 是指算法在计算机内执行是所需存储空间的度量,它也是数据规模 n 的函数.

(一) 冒泡排序 Bubble Sort

冒泡排序是一种简单的排序算法.它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换位置.走访数列的工作是重复地进行直到没有再需要交换的数据,也就说明该数列已经排序完成.这个算法的名字由来是因为越小的元素会经由交换慢慢’冒泡’到数列的顶端.

1. 算法执行过程描述

• 比较相邻的元素.如果第一个比第二个大,就交换它们两个.
• 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数.
• 针对所有的元素重复以上的步骤,除了最后一个 j-i
• 重复步骤 1~3,直到排序完成,

2. 动图演示

3. 代码实现

const bubbleSort = (arr) => {
  const length = arr.length,
    array = [...arr];
  // 元素两两相比
  for (let i = 0; i < length; i++) {
    for (let j = 0; j < length - i - 1; j++) {
      if (array[j] > array[j + 1]) {
        [array[j + 1], array[j]] = [array[j], array[j + 1]]; // 元素交换
      }
    }
  }
  return array;
};

(一) 冒泡排序 Bubble Sort

冒泡排序是一种简单的排序算法.它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换位置.走访数列的工作是重复地进行直到没有再需要交换的数据,也就说明该数列已经排序完成.这个算法的名字由来是因为越小的元素会经由交换慢慢’冒泡’到数列的顶端.

1. 算法执行过程描述

• 比较相邻的元素.如果第一个比第二个大,就交换它们两个.
• 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数.
• 针对所有的元素重复以上的步骤,除了最后一个 j-i
• 重复步骤 1~3,直到排序完成,

2. 动图演示

3. 代码实现

/* 
    ---------- 冒泡排序 ---------- 
    比较数组中任意两个相邻的数值，如果第一个比第二个大，则交换他们的位置
*/
const bubbleSort = (arr) => {
  const length = arr.length,
    array = [...arr];
  // 元素两两相比
  for (let i = 0; i < length; i++) {
    for (let j = 0; j < length - i - 1; j++) {
      if (array[j] > array[j + 1]) {
        [array[j + 1], array[j]] = [array[j], array[j + 1]]; // 元素交换
      }
    }
  }
  return array;
};

(二) 选择排序 Selection Sort

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小(大)元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

1. 算法执行过程描述

n 个记录的直接选择排序可经过 n-1 趟直接选择排序得到有序结果。具体算法描述如下：

• 初始状态：无序区为 R[1..n]，有序区为空；
• 第 i 趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为 R[1..i-1]和 R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第 1 个记录 R 交换，使 R[1..i]和 R[i+1..n)分别变为记录个数增加 1 个的新有序区和记录个数减少 1 个的新无序区；
• n-1 趟结束，数组有序化了。

2. 动图演示

3. 代码实现

/* 
    ---------- 选择排序 ---------- 
    找到数据结构中的最小值，将其放到第一位，接着找第二小的值，放在第二位，以此类推，反之亦然
*/
const selectionSort = (arr) => {
  let length = arr.length,
    array = [...arr],
    minIndex;
  for (let i = 0; i < length - 1; i++) {
    // 进来先默认最小index为 i
    minIndex = i;
    for (let j = i; j < length; j++) {
      // 寻找最小的数
      if (array[minIndex] > array[j]) minIndex = j;
    }
    // 如果minIndex不等于i 说明遍历完以后，minIndex变小了，则交换他们的位置
    if (minIndex !== i) {
      [array[i], array[minIndex]] = [array[minIndex], array[i]];
    }
  }
  return array;
};

4. 算法分析

表现最稳定的排序算法之一,因无论什么数据进去都是 O(n²)的时间复杂度,所以用到它的时候,数据规模越小越好.唯一的好处可能就算不占用额外的内存空间.

(三) 插入排序 Insertion Sort

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

1. 算法执行过程描述

一般来说，插入排序都采用 in-place 在数组上实现。具体算法描述如下：

• 从第一个元素开始，该元素可以认为已经被排序；
• 取出下一个元素，在已经排序的元素序列中从后向前扫描；
• 如果该元素（已排序）大于新元素，将该元素移到下一位置；
• 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置；
• 将新元素插入到该位置后；
• 重复步骤 2~5。

2. 动图演示

3. 代码实现

/* 
    ---------- 直接插入排序 ---------- 
    假设第一个元素已经被排序，然后从后往前扫，如果该假设的元素大于新元素，将元素往下移动一个位置
*/
const insertSort = (arr) => {
  let length = arr.length,
    array = [...arr],
    preIndex,
    current;
  for (let i = 1; i < length; i++) {
    preIndex = i;
    current = array[i];
    while (preIndex > 0 && array[preIndex - 1] > current) {
      array[preIndex] = array[preIndex - 1];
      preIndex--;
    }
    array[preIndex] = current;
  }
  return array;
};

4. 算法分析

插入排序在实现上，通常采用 in-place 排序（即只需用到 O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

(四) 希尔排序 Shell Sort

1959 年 Shell 发明，第一个突破 O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

1. 算法执行过程描述

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
• 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

• 选择一个增量序列 t1，t2，…，tk，其中 ti>tj，tk=1；
• 按增量序列个数 k，对序列进行 k 趟排序；
• 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

2. 动图演示

3. 代码实现

/* 
    ---------- 希尔排序 ---------- 
    先将整个待排序的记录序列分割成为若干子序列。
    分别进行直接插入排序。
    待整个序列中的记录基本有序时，再对全体记录进行依次直接插入排序
*/
const shellSort = (arr) => {
  let length = arr.length,
    temp,
    gap = 1;
  while (gap < length / 3) {
    gap = gap * 3 + 1;
  }
  for (gap; gap > 0; gap = Math.floor(gap / 3)) {
    for (let i = gap; i < length; i++) {
      temp = arr[i];
      let j = i - gap;
      for (; j >= 0 && arr[j] > temp; j -= gap) {
        arr[j + gap] = arr[j];
      }
      arr[j + gap] = temp;
    }
  }
  return arr;
};

4. 算法分析

希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第 4 版）》的合著者 Robert Sedgewick 提出的

(五) 归并排序 Merge Sort

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为 2-路归并。

1. 算法执行过程描述

• 把长度为 n 的输入序列分成两个长度为 n/2 的子序列；
• 对这两个子序列分别采用归并排序；
• 将两个排序好的子序列合并成一个最终的排序序列。

2. 动图演示

3. 代码实现

/* 
    ---------- 归并排序 ---------- 
   归并排序属于一种分治算法。归并排序的思想就是将原始数组切分成一个一个较小的数组，直到每一个数组只有一个元素为止，然后再把一个一个小数组，一点一点的结合成一个最终排序后的数组。
   其实简单来说，就是先分，再合。归并排序的实现有两种方法，一种是递归，一种是迭代。
   1. mergeSortRec([55,44,22,99,11,33]) => mergeSortRec([55,44,22]),mergeSortRec([99,11,33]) => ... => [55] [44] [22] [99] [11] [33]
   2. merge([55],[44]) => [44,55]
   3. merge([22],[99]) => [22,99]
   4. merge([44,55],[22,99]) => [22,44,55,99]
*/
const mergeSortRec = (arr) => {
  const length = arr.length;
  // 如果length为1，说明已经分到底了
  if (length === 1) {
    return arr;
  }
  const mid = Math.floor(length / 2),
    left = arr.slice(0, mid),
    right = arr.slice(mid, length);
  return merge(mergeSortRec(left), mergeSortRec(right));
};

const merge = (left, right) => {
  let result = [],
    il = 0,
    ir = 0;
  // 如果左侧的比右侧的小，则放入左侧数值，并将il++，这样下次比较的时候，就是左侧下一个元素与右侧那个大的元素比较了
  while (il < left.length && ir < right.length) {
    if (left[il] < right[ir]) {
      result.push(left[il++]);
    } else {
      result.push(right[ir++]);
    }
  }
  // 前面比较完之后，会剩下一个元素没有对应的数据进行比较，所以将剩下的元素放入集合中
  while (il < left.length) {
    result.push(left[il++]);
  }
  while (ir < right.length) {
    result.push(right[ir++]);
  }
  return result;
};

4. 算法分析

归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn）的时间复杂度。代价是需要额外的内存空间。

(六) 快速排序 Quick Sort

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

1. 算法执行过程描述

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

• 从数列中挑出一个元素，称为 “基准”（pivot）；
• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
• 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

2. 动图演示

3. 代码实现

/* 
    ---------- 快速排序 ---------- 
    先找到一个基准点（一般指数组的中部），然后数组被该基准点分为两部分，依次与该基准点数据比较，如果比它小，放左边；反之，放右边。
    左右分别用一个空数组去存储比较后的数据。
    最后递归执行上述操作，直到数组长度 <= 1;
*/
const quickSort = (arr) => {
  if (arr.length <= 1) {
    return arr;
  }
  // 取基准点
  const midIndex = Math.floor(arr.length / 2);
  // 取基准点的值，
  const midArr = arr.splice(midIndex, 1);
  const midVal = midArr[0];
  // 存放比基准点小的值
  const left = [];
  // 存放比基准点大的值
  const right = [];
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < midVal) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  // 递归调用，直到元素长度<=1
  return [...quickSort(left), midVal, ...quickSort(right)];
};

(七) 堆排序 Heap Sort

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

1. 算法执行过程描述

• 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
• 将堆顶元素 R[1]与最后一个元素 R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足 R[1,2…n-1]<=R[n]；
• 由于交换后新的堆顶 R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将 R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为 n-1，则整个排序过程完成。

2. 动图演示

3. 代码实现

/* 
    ---------- 堆排序 ---------- 
    堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
    1.将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
    2.将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
    3.由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
*/
const heapSort = (arr) => {
  // 初始化大顶堆，从第一个非叶子节点开始
  for (let i = Math.floor(arr.length / 2 - 1); i >= 0; i--) {
    heapify(arr, i, arr.length);
  }
  // 排序，每一次循环找出一个当前最大值，数组长度减一
  for (let i = Math.floor(arr.length - 1); i > 0; i--) {
    // 根节点与最后一个节点交换
    [arr[0], arr[i]] = [arr[i], arr[0]];
    // 从根节点开始调整，并且最后一个节点已经为当前最大值，不需要参与比较，所以第三个参数为i，即比较到i的前一个节点即可
    heapify(arr, 0, i);
  }
  return arr;
};

/* 
  将i节点以下的堆整理为大顶堆，注意这一步实现的基础实际上是：
    假设节点i以下的子堆已经是一个大顶堆，heapify函数实现的功能实际上是：找到节点i在包括节点i的堆中的正确位置。
    后面将写一个for循环，从第一个非叶子节点开始，对每一个非叶子节点都执行heapify操作，所以就满足了i以下的子堆已经是一个大顶堆。 
*/
const heapify = (arr, i, length) => {
  let temp = arr[i];
  for (let j = 2 * i + 1; j < length; j = 2 * j + 1) {
    temp = arr[i];
    if (j + 1 < length && arr[j] < arr[j + 1]) {
      j++;
    }
    if (temp < arr[j]) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i = j;
    } else {
      break;
    }
  }
};

(八) 计数排序 Counting Sort

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

1. 算法执行过程描述

• 找出待排序的数组中最大和最小的元素；
• 统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项；
• 对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）；
• 反向填充目标数组：将每个元素 i 放在新数组的第 C(i)项，每放一个元素就将 C(i)减去 1。

2. 动图演示

3. 代码实现

/* 
    ---------- 计数排序 ---------- 
    计数排序就是遍历数组记录数组下的元素出现过多次，然后把这个元素找个位置先安置下来，简单点说就是以原数组每个元素的值作为新数组的下标，而对应小标的新数组元素的值作为出现的次数，相当于是通过下标进行排序。
    计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
    1.找出待排序的数组中最大和最小的元素；
    2.统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
    3.对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
    4.反向填充目标数组：将每个元素i放在新数组的第B(i)项，每放一个元素就将C(i)减去1。
*/
const countingSort = (arr) => {
  let length = arr.length,
    B = [],
    C = [],
    max = (min = arr[0]);
  // 将数组中的val作为C中的key存储，值为val出现的次数
  for (let i = 0; i < length; i++) {
    min = min <= arr[i] ? min : arr[i];
    max = max >= arr[i] ? max : arr[i];
    C[arr[i]] = C[arr[i]] ? C[arr[i]] + 1 : 1;
  }
  // 计算排序后的元素下标，从C「min]开始，如果min为1,C[min]为1，C[5]的值为1，则C[1]-C[4]的值都为1，C[5]的值为2，以此类推
  for (let j = min; j < max; j++) {
    C[j + 1] = (C[j + 1] || 0) + (C[j] || 0);
  }
  // 从后往前遍历原数组，找到对应数据在C中的下标，C中下标存储的就是对应元素在数组中的下标，在B中的对应下标位置存储元素
  for (let k = length - 1; k >= 0; k--) {
    B[C[arr[k]] - 1] = arr[k];
    C[arr[k]]--;
  }
  return B;
};

4. 算法分析

计数排序是一个稳定的排序算法。当输入的元素是 n 个 0 到 k 之间的整数时，时间复杂度是 O(n+k)，空间复杂度也是 O(n+k)，其排序速度快于任何比较排序算法。当 k 不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。

(九) 桶排序 Bucket Sort

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

1. 算法执行过程描述

• 设置一个定量的数组当作空桶；
• 遍历输入数据，并且把数据一个一个放到对应的桶里去；
• 对每个不是空的桶进行排序；
• 从不是空的桶里把排好序的数据拼接起来。

2. 动图演示

3. 代码实现

/* 
    ---------- 桶排序 ---------- 
    桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。
    桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。
    1.设置一个定量的数组当作空桶；
    2.遍历输入数据，并且把数据一个一个放到对应的桶里去；
    3.对每个不是空的桶进行排序；
    4.从不是空的桶里把排好序的数据拼接起来。 
*/
const bucketSort = (arr, bucketSize) => {
  if (!arr.length) return;
  let length = arr.length,
    min = (max = arr[0]);
  for (let i = 0; i < length; i++) {
    min = min <= arr[i] ? min : arr[i]; // 获取最小值
    max = max >= arr[i] ? max : arr[i]; // 获取最大值
  }

  // 初始化桶
  const DEFAULT_BUCKET_SIZE = 5; // 设置每个桶的默认数量为5
  bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
  const bucketCount = Math.floor((max - min) / bucketSize) + 1; // 设置桶的数量
  // 初始化每个桶
  const buckets = new Array(bucketCount);
  for (let i = 0; i < buckets.length; i++) {
    buckets[i] = [];
  }

  // 利用映射函数将数据分配到各个桶中
  for (let i = 0; i < length; i++) {
    const index = Math.floor((arr[i] - min) / bucketSize);
    buckets[index].push(arr[i]);
  }

  arr.length = 0;
  for (let i = 0; i < buckets.length; i++) {
    insertSort(buckets[i]); // 对每个桶进行排序
    for (let j = 0; j < buckets[i].length; j++) {
      arr.push(buckets[i][j]);
    }
  }
  return arr;
};

4. 算法分析

桶排序最好情况下使用线性时间 O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为 O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。

(十) 基数排序 Radix Sort

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

1. 算法执行过程描述

• 取得数组中的最大数，并取得位数；
• arr 为原始数组，从最低位开始取每个位组成 radix 数组；
• 对 radix 进行计数排序（利用计数排序适用于小范围数的特点）；

2. 动图演示

3. 代码实现

/* 
    ---------- 基数排序 ---------- 
    基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。
    由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
    使用条件：
      要求数据可以分割独立的位来比较；
      位之间由递进关系，如果 a 数据的高位比 b 数据大，那么剩下的地位就不用比较了；
      每一位的数据范围不能太大，要可以用线性排序，否则基数排序的时间复杂度无法做到 O(n)。
    方案:
      按照优先从高位或低位来排序有两种实现方案:
      MSD：由高位为基底，先按 k1 排序分组，同一组中记录, 关键码 k1 相等，再对各组按 k2 排序分成子组, 之后，对后面的关键码继续这样的排序分组，直到按最次位关键码 kd 对各子组排序后，再将各组连接起来，便得到一个有序序列。MSD 方式适用于位数多的序列。
      LSD：由低位为基底，先从 kd 开始排序，再对 kd - 1 进行排序，依次重复，直到对 k1 排序后便得到一个有序序列。LSD 方式适用于位数少的序列。
*/
// 获取最大值的位数
const getMaxDigits = (arr) => arr?.length && String(arr.reduce((pre, cur) => (cur > pre ? cur : pre), 0)).length;
/* 
  name: 基数排序
  @param: arr 待排序数组
  @param: max 最大位数(String(v).length)
*/
const radixSort = (arr, max) => {
  const buckets = [];
  let unit = 10,
    base = 1;
  for (let i = 0; i < max; i++, base *= 10, unit *= 10) {
    for (let j = 0; j < arr.length; j++) {
      let index = ~~((arr[j] % unit) / base); // 依次过滤出个位，十位等等
      // 往不同桶里添加数据
      if (buckets[index] == null) {
        buckets[index] = [];
      }
      buckets[index].push(arr[j]);
    }
    let pos = 0,
      value;
    for (let j = 0, length = buckets.length; j < length; j++) {
      if (buckets[j] != null) {
        while ((value = buckets[j].shift()) != null) {
          // 将不同桶里的数据挨个捞出来，为下一轮高位做准备，由于靠近桶底的元素排名靠前，因此先从桶底开始捞
          arr[pos++] = value;
        }
      }
    }
  }
  return arr;
};

4. 算法分析

基数排序基于分别排序，分别收集，所以是稳定的。但基数排序的性能比桶排序要略差，每一次关键字的桶分配都需要 O(n)的时间复杂度，而且分配之后得到新的关键字序列又需要 O(n)的时间复杂度。假如待排数据可以分为 d 个关键字，则基数排序的时间复杂度将是 O(d*2n) ，当然 d 要远远小于 n，因此基本上还是线性级别的。基数排序的空间复杂度为 O(n+k)，其中 k 为桶的数量。一般来说 n>>k，因此额外空间需要大概 n 个左右。