排序算法

简单来说，排序算法用于将一组乱序的元素按照升序或降序的顺序重新排列。排序算法的性能通常通过其时间复杂度、空间复杂度、稳定性等指标来衡量。

JavaScript 语言中的自带的排序：数组的 sort 方法。

冒泡排序

冒泡排序（Bubble Sort）是一种简单的比较排序算法。它重复地遍历待排序数组，每次比较相邻的两个元素，如果顺序相反则进行交换。这样，每一轮遍历都会将最大（或最小）的元素“冒泡”到顶端，直到整个数组都排序完成，最终达到完全有序。

步骤：

1. 遍历数组：从头到尾遍历数组，比较相邻的两个元素。
2. 比较相邻元素：每次比较相邻的两个元素，如果它们的顺序不正确（比如，前一个元素大于后一个元素），则交换它们。
3. 重复遍历：重复上述步骤，直到没有任何一对元素需要交换，即数组已经完全排序。

代码实现：

function bubbleSort(array) {
    // 检查输入是否为数组且长度大于 1，若不满足条件，则直接返回原数组
    if (!Array.isArray(array) || array.length <= 1) return array

    // 初始化最后一个未排序元素的索引
    let lastIndex = array.length - 1

    // 当还有未排序的元素时，执行排序过程
    while (lastIndex > 0) {
        // 初始化交换标志为 true，若本轮未发生交换，则排序完成
        let flag = true
        // 记录最后一次交换元素的位置，初始设置为未排序部分的末尾
        const k = lastIndex

        // 遍历未排序部分的元素
        for (let j = 0; j < k; j++) {
            // 若当前元素大于其后面的元素，则交换它们的位置
            if (array[j] > array[j + 1]) {
                flag = false // 发生了交换，将标志设置为 false
                lastIndex = j // 记录最后一次交换的位置
                ;[array[j], array[j + 1]] = [array[j + 1], array[j]] // 交换元素
            }
        }

        // 若本轮未发生交换，则数组已经有序，直接退出循环
        if (flag) break
    }

    // 返回排序后的数组
    return array
}

// 测试
console.log(bubbleSort([6,1,5,4,2,3])) // [1, 2, 3, 4, 5, 6]

冒泡排序有几种可以优化的空间：

• 优化遍历范围：在每一轮排序中，可以观察到最后一次交换发生的位置之后的元素已经是有序的，因此可以将下一轮排序的范围限定在上一轮最后一次交换的位置之前。这样可以减少不必要的比较和交换操作。

• 添加标志位：如果在一轮排序过程中没有发生任何元素的交换，说明数组已经是有序的，可以提前结束排序过程。

• 针对部分有序数组的优化：如果数组在初始状态下已经接近有序，可以记录下每轮排序中最后一次交换的位置，然后下一轮排序时只需要遍历到该位置即可，这样可以大大减少排序的比较次数。

• 鸡尾酒排序（双向冒泡排序）：在一次排序过程中，既从左到右比较交换，又从右到左比较交换，可以在某些特定情况下提升效率。

时间复杂度：

• 最优时间复杂度：O(n)
  当输入数据已经是有序时，冒泡排序可以通过设置一个标志变量来检测是否发生了交换操作，如果在某一趟排序中没有交换操作发生，说明数组已经有序，因此可以提前结束排序过程。此时，最优时间复杂度为 O(n)。

• 最坏时间复杂度：O(n^2)
  在最坏情况下，输入数据是逆序的，此时需要进行 n-1 趟排序，每一趟排序中需要进行的比较次数逐渐减少，总比较次数为 n(n-1)/2，因此最坏时间复杂度为 O(n^2)。

• 平均时间复杂度：O(n^2)
  在一般情况下，冒泡排序的比较和交换操作的次数与输入数据的初始排列状态有关，但总体而言其时间复杂度仍为 O(n^2)。

空间复杂度：

冒泡排序是一种原地排序算法，它在排序过程中只需要常数级的额外空间，即只使用了少量的辅助变量，因此其空间复杂度为 O(1)。

稳定性：

冒泡排序是一种稳定排序算法。在排序过程中，如果两个相等的元素相互比较，它们不会交换位置，因此相等元素的相对位置不会改变。

冒泡排序由于其简单易懂的特性，常用于教学和小规模数据集的排序，但由于其较低的效率，通常不适合大规模数据集的排序任务。

选择排序

选择排序（Selection Sort）是一种简单的比较排序算法。它的基本思想是在未排序数组中找到最小（或最大）的元素，然后将其放置到数组的起始位置，接着在剩余的未排序部分中继续寻找最小（或最大）的元素，依次类推，直到所有元素都排序完成。

步骤：

1. 初始状态： 将整个序列看作两部分，一部分是未排序的，一部分是已排序的（初始时已排序部分为空）。

2. 遍历未排序部分： 遍历未排序部分，找到最小（或最大）的元素。

3. 交换元素： 将找到的最小（或最大）元素与未排序部分的第一个元素交换位置，使得找到的最小元素成为已排序部分的最后一个元素。

4. 扩大已排序部分： 将已排序部分的长度增加 1，未排序部分的长度减少 1。

5. 重复： 重复以上步骤，直到所有元素都已经排序完毕。

这个过程类似于每次从一堆未排序的卡片中选出最小（或最大）的卡片，然后放到已排序的卡片堆中。选择排序的特点是每次遍历都只进行一次交换操作，因此相对于其他排序算法，它的交换次数较少。

代码实现：

function selectionSort(array) {
    // 获取数组长度
    const { length } = array

    // 如果不是数组或者数组长度小于等于 1，直接返回，不需要排序
    if (!Array.isArray(array) || length <= 1) return array

    // 外层循环，遍历整个数组，每次找到当前未排序部分的最小元素并放到已排序部分的末尾
    for (let i = 0; i < length - 1; i++) {
        let minIndex = i // 设置当前循环最小元素索引

        // 内层循环，从当前元素的下一个位置开始遍历，找到未排序部分的最小元素
        for (let j = i + 1; j < length; j++) {
            // 如果当前元素比最小元素索引小，则更新最小元素索引
            if (array[minIndex] > array[j]) {
                minIndex = j
            }
        }

        // 交换最小元素到当前位置
        swap(array, i, minIndex)
    }

    return array
}

// 交换数组中两个元素的位置
function swap(array, left, right) {
    const temp = array[left]
    array[left] = array[right]
    array[right] = temp
}

// 测试
console.log(selectionSort([6, 1, 5, 4, 2, 3]))  // [1, 2, 3, 4, 5, 6]

时间复杂度：

• 最优时间复杂度：O(n^2)
  无论输入数据的初始排列状态如何，选择排序总是需要进行 n(n-1)/2 次比较，因此最优时间复杂度为 O(n^2)。

• 最坏时间复杂度：O(n^2) 同样地，在最坏情况下，选择排序仍需要进行 n(n-1)/2 次比较，所以最坏时间复杂度为 O(n^2)。

• 平均时间复杂度：O(n^2)
  由于选择排序每一趟排序所需的比较次数固定，因此其平均时间复杂度也为 O(n^2)。

空间复杂度：

选择排序是一种原地排序算法，只需要常数级的辅助空间（通常是用于交换元素的临时变量），因此其空间复杂度为 O(1)。

稳定性：

选择排序通常不是稳定排序。在选择排序过程中，每次从未排序部分选择最小（或最大）元素并将其与未排序部分的第一个元素交换时，如果相等元素存在，原有的相对顺序可能会被打破。例如：

• 初始数组：[3, 2, 2, 1]
• 第一次选择：选择最小元素 1，与第一个元素 3 交换，结果：[1, 2, 2, 3]
• 第二次选择：选择最小元素 2，与第二个元素 2 交换，结果：[1, 2, 2, 3]

虽然这个例子没有改变相同元素的相对顺序，但在某些情况下，如处理：[2, 3, 1, 2]，第二个“2”会被提前，与第一个“2”交换，导致顺序改变。

选择排序由于其简单性和恒定的空间复杂度，适用于对内存空间要求较高但对时间效率要求不高的场景。然而，由于其 O(n^2) 的时间复杂度，选择排序在处理大规模数据集时效率较低，通常不作为首选的排序算法。

插入排序

插入排序（Insertion Sort）是一种简单的比较排序算法。它的基本思想是将待排序数组分成已排序和未排序两部分，初始时已排序部分只有一个元素（即数组的第一个元素），然后从未排序部分依次取出元素，将其插入到已排序部分的正确位置，直到所有元素都被插入完成。

插入排序类似扑克牌思想，想象在打扑克牌，拿起来第一张，放哪里无所谓，再拿起来一张，比第一张小，放左边，继续拿，可能是中间数，就插在中间，依次把牌拿完。

步骤：

1. 初始已排序部分：初始时，将待排序数组的第一个元素视为已排序部分，其余元素视为未排序部分。
2. 遍历未排序部分：从第二个元素开始，依次遍历未排序部分的元素。
3. 插入到已排序部分：对于每个未排序部分的元素，将其与已排序部分的元素逐个比较，找到正确的插入位置。
4. 重复插入：将元素插入到已排序部分的正确位置后，已排序部分的长度增加 1，未排序部分的长度减少 1，继续重复上述步骤，直到所有元素都被插入完成。

代码实现：

function insertSort(array) {
    const { length } = array

    // 如果不是数组或者数组长度小于等于 1，直接返回，不需要排序
    if (!Array.isArray(array) || length <= 1) return array

    // 循环从 1 开始，0 位置为默认的已排序的序列
    for (let i = 1; i < length; i++) {
        const temp = array[i] // 保存当前需要排序的元素
        let j = i

        // 在当前已排序序列中比较，如果比需要排序的元素大，就依次往后移动位置
        while (j - 1 >= 0 && array[j - 1] > temp) {
            array[j] = array[j - 1]
            j--
        }

        // 将找到的位置插入元素
        array[j] = temp
    }

    return array
}

insertSort([6,1,5,4,2,3]) // [1, 2, 3, 4, 5, 6]

时间复杂度：

• 最优时间复杂度：O(n)
  当输入数据已经有序时，插入排序每次只需要比较一次即可确定元素的位置，无需进行交换操作。此时，最优时间复杂度为 O(n)。

• 最坏时间复杂度：O(n^2)
  在最坏情况下，输入数据是逆序的。此时，插入排序需要进行大量的比较和移动操作，每次插入元素时都需要将其与已经排序的部分进行比较并移动其他元素。因此最坏时间复杂度为 O(n^2)。

• 平均时间复杂度：O(n^2)
  在一般情况下，插入排序的比较和移动操作次数与输入数据的初始排列状态有关，但总体而言，其平均时间复杂度为 O(n^2)。

空间复杂度：

插入排序是一种原地排序算法，它在排序过程中只需要常数级的额外空间（用于存储待插入的元素的临时变量），因此其空间复杂度为 O(1)。

稳定性：

插入排序是一种稳定排序算法。在插入过程中，如果待插入的元素与已排序部分的某个元素相等，插入排序会将待插入的元素放在相等元素的后面，从而保持相等元素的相对顺序不变。

插入排序由于其简单性和对小规模数据集的高效性，常用于对小型数组进行排序或在其他更复杂的排序算法（如快速排序、归并排序）的过程中处理小数据块。然而，由于其 O(n^2) 的时间复杂度，插入排序在处理大规模数据集时效率较低。

希尔排序

希尔排序（Shell Sort）是一种改进的插入排序算法，也被称为“缩小增量排序”。它的基本思想是通过定义一个间隔序列（称为增量序列），将待排序数组分成若干个子序列，对每个子序列进行插入排序。随着排序的进行，增量序列逐渐缩小，直到增量为 1，最后对整个数组进行插入排序。

步骤：

1. 选择增量序列：定义一个增量序列，确定每个增量值（间隔），通常以递减的方式选择。
2. 分组排序：将待排序数组根据当前增量值分成若干个子序列，对每个子序列进行插入排序。
3. 逐步缩小增量：重复上述步骤，逐步缩小增量值，直到增量为 1。
4. 最终排序：当增量为 1 时，对整个数组进行一次插入排序，完成排序过程。

代码实现：

function hillSort(array) {
  const { length } = array

  // 如果输入不是数组或者数组长度小于等于 1，直接返回原数组，不需要排序
  if (!Array.isArray(array) || length <= 1) return array

  // 第一层循环：确定增量的大小，每次增量的大小减半
  for (let gap = parseInt(length >> 1); gap >= 1; gap = parseInt(gap >> 1)) {
    // 对每个分组使用插入排序，相当于将插入排序的 1 换成了 gap
    for (let i = gap; i < length; i++) {
      const temp = array[i] // 保存当前元素
      let j = i

      // 第二层循环：对当前分组进行插入排序
      // 如果 j - gap >= 0 并且前一个元素大于当前元素，则进行交换
      while (j - gap >= 0 && array[j - gap] > temp) {
        array[j] = array[j - gap] // 将前一个元素后移
        j -= gap // 继续比较下一个分组内的元素
      }
      array[j] = temp // 插入元素到正确的位置
    }
  }

  return array // 返回排序后的数组
}

hillSort([6,1,5,4,2,3]) // [1, 2, 3, 4, 5, 6]

时间复杂度：

希尔排序的时间复杂度较为复杂，与所选的增量序列（gap sequence）有很大关系。常见的增量序列有希尔增量序列、Hibbard 增量序列、Sedgewick 增量序列等。以下是几种常见增量序列的时间复杂度分析：

• 希尔增量序列（gap = n/2, n/4, ..., 1）：最坏时间复杂度：O(n^2)

• Hibbard 增量序列（gap = 2^k - 1）：最坏时间复杂度：O(n^(3/2))

• Sedgewick 增量序列（一种较为复杂的序列）：最坏时间复杂度：O(n^(4/3))

• 更优的增量序列：有些优化过的增量序列可以达到 O(n log^2 n) 的最坏时间复杂度。

由于增量序列的选择对希尔排序的时间复杂度有很大的影响，所以具体的时间复杂度因实现而异，但通常在 O(n^2) 和 O(n log^2 n) 之间。

空间复杂度：

希尔排序是一种原地排序算法，其空间复杂度为 O(1)，只需要常数级的额外空间。

稳定性：

希尔排序不是稳定排序。在排序过程中，元素可能会跨越多个位置进行交换，因此相同元素的相对顺序可能会被打乱。

希尔排序由于其高效性和相对简单的实现，在实际应用中有一定的优势，特别是在数据规模较大时。它通过对插入排序的改进，大大减少了数据移动的次数，从而提高了排序的效率。

归并排序

归并排序（Merge Sort）是一种基于分治法（Divide and Conquer）的高效排序算法。其基本思想是将数组分成更小的子数组，分别对这些子数组进行排序，然后再将它们合并起来，以得到一个有序的数组。

步骤：

1. 分割（Divide）：将数组从中间分成两个子数组（递归地分割直到子数组的长度为 1）。
2. 排序（Conquer）：对每个子数组进行排序。因为子数组的长度为 1，所以它们是有序的。
3. 合并（Combine）：将两个有序的子数组合并成一个有序的数组。重复这个过程，直到所有的子数组被合并成一个完整的有序数组。

代码实现：

function mergeSort(array) {
  const { length } = array

  // 如果不是数组或者数组长度小于等于 0，直接返回，不需要排序
  if (!Array.isArray(array) || length <= 1) return array

  const mid = parseInt(length >> 1) // 找到中间索引值
  const left = array.slice(0, mid) // 截取左半部分
  const right = array.slice(mid, length) // 截取右半部分

  return merge(mergeSort(left), mergeSort(right)) // 递归分解后，进行排序合并
}

function merge(leftArray, rightArray) {
  const result = []
  const leftLength = leftArray.length
  const rightLength = rightArray.length
  let il = 0
  let ir = 0

  // 左右两个数组的元素依次比较，将较小的元素加入结果数组中，直到其中一个数组的元素全部加入完则停止
  while (il < leftLength && ir < rightLength) {
    if (leftArray[il] < rightArray[ir]) {
      result.push(leftArray[il++])
    } else {
      result.push(rightArray[ir++])
    }
  }

  // 如果是左边数组还有剩余，则把剩余的元素全部加入到结果数组中。
  while (il < leftLength) {
    result.push(leftArray[il++])
  }

  // 如果是右边数组还有剩余，则把剩余的元素全部加入到结果数组中。
  while (ir < rightLength) {
    result.push(rightArray[ir++])
  }

  return result
}

mergeSort([6,1,5,4,2,3]) // [1, 2, 3, 4, 5, 6]

基本过程：

1. 分割：将待排序数组分成两半。
2. 递归排序：对每一半分别进行递归排序。
3. 合并：合并两个有序子数组以形成一个有序的整体。

时间复杂度：

1. 最优时间复杂度：O(n log n)
2. 最坏时间复杂度：O(n log n)
3. 平均时间复杂度：O(n log n)

归并排序在最优、最坏和平均情况下的时间复杂度都是 O(n log n)，因为它始终将数组分成两半，然后对每一半进行排序，再合并结果。

空间复杂度：

归并排序的空间复杂度为 O(n)，这是因为归并排序在合并过程中需要一个额外的数组来暂存数据。对于递归实现，还需要考虑递归调用的栈空间，但总的额外空间仍然是 O(n)。

稳定性：

归并排序是一种稳定排序算法。在合并两个有序子数组的过程中，如果两个元素相等，先将前一个数组的元素放入结果数组中，从而保持相等元素的相对顺序不变。

归并排序由于其稳定性和 O(n log n) 的时间复杂度，常用于处理大规模数据集，尤其是在需要稳定排序的情况下。虽然归并排序的空间复杂度较高，但其分治策略使其在许多应用中表现出色。

快速排序

快速排序（Quick Sort）是一种高效的排序算法，基于分治法（Divide and Conquer）。它通过选择一个"基准"（pivot）元素，并将数组分成两部分，其中一部分的所有元素都小于基准，另一部分的所有元素都大于基准。然后递归地对这两部分进行排序。

步骤：

1. 选择基准：从数组中选择一个元素作为基准（pivot）。
2. 分区：重新排列数组，使得所有小于基准的元素在基准的左边，所有大于基准的元素在基准的右边（相等的元素可以放在任一侧）。此时基准元素处于其正确的位置。
3. 递归排序：递归地对基准左边的子数组和右边的子数组进行排序。

代码实现：

function quickSort(array) {
  // 如果不是数组或者数组长度小于等于 0，直接返回，不需要排序
  if (!Array.isArray(array) || array.length <= 1) return array

  // 选择基准
  const pivot = array[array.length - 1]
  // 使用两个数组 left 和 right 来存储小于和大于基准的元素
  const left = []
  const right = []

  // 分区过程
  for (let i = 0; i < array.length - 1; i++) {
    if (array[i] < pivot) {
      left.push(array[i])
    } else {
      right.push(array[i])
    }
  }

  // 递归地排序左右子数组并合并
  return [...quickSort(left), pivot, ...quickSort(right)]
}

quickSort([6, 1, 5, 4, 2, 3]) // [1, 2, 3, 4, 5, 6]

时间复杂度：

• 最优时间复杂度：O(n log n)
  当每次划分的子数组都比较均匀时，递归树的高度为 log n，每层的操作复杂度为 O(n)，所以最优时间复杂度为 O(n log n)。

• 最坏时间复杂度：O(n^2)
  在最坏情况下，每次划分的子数组高度不均匀，例如每次选择的基准（pivot）是最大或最小元素，这会导致递归树退化为链表形式，时间复杂度为 O(n^2)。

• 平均时间复杂度：O(n log n)
  在实际应用中，快速排序的平均性能通常很好，期望时间复杂度为 O(n log n)，因为随机选择基准或使用“三数取中”等方法可以有效避免最坏情况。

空间复杂度：

快速排序的空间复杂度主要取决于递归调用栈的深度：

• 平均空间复杂度：O(log n)
  在理想情况下，递归调用栈的深度为 log n，因此空间复杂度为 O(log n)。

• 最坏空间复杂度：O(n)
  在最坏情况下，递归调用栈的深度为 n，因此空间复杂度为 O(n)。

稳定性：

快速排序不是稳定排序。在排序过程中，元素的相对顺序可能会被改变，因为基准元素的交换可能会使得相等的元素顺序颠倒。

快速排序因其高效性和较好的平均性能，广泛应用于各种排序任务。通过随机选择基准或“三数取中”等方法，可以有效地改善其性能，避免最坏情况的发生。

堆排序

堆排序（Heap Sort）是一种基于二叉堆数据结构的比较排序算法。堆排序可以分为两个阶段：构建初始堆和在堆上进行排序操作。

步骤：

1. 构建最大堆：将无序数组构建成一个最大堆（max heap），最大堆是一个完全二叉树，其中每个节点的值都大于或等于其子节点的值。
2. 排序：交换堆顶元素（最大值）和堆的最后一个元素，并将堆的大小减少 1。然后对堆的根节点进行调整，使其重新成为最大堆。 重复上述步骤，直到堆中剩余元素只剩一个，即完成排序。

function heapSort(array) {
  // 如果不是数组或者数组长度小于等于 1，直接返回，不需要排序
  if (!Array.isArray(array) || array.length <= 1) return array

  const n = array.length

  // 构建最大堆
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(array, n, i)
  }

  // 逐一从堆中取出元素，并对剩余元素重新堆化
  for (let i = n - 1; i > 0; i--) {
    // 将堆顶（最大值）和堆的最后一个元素交换
    ;[array[0], array[i]] = [array[i], array[0]]

    // 对堆的剩余部分重新堆化
    heapify(array, i, 0)
  }

  return array
}

// 堆化函数，维护堆的性质
function heapify(array, n, i) {
  let largest = i // 假设当前节点是最大值
  const left = 2 * i + 1 // 左子节点
  const right = 2 * i + 2 // 右子节点

  // 如果左子节点大于当前节点，则更新最大值
  if (left < n && array[left] > array[largest]) {
    largest = left
  }

  // 如果右子节点大于当前节点，则更新最大值
  if (right < n && array[right] > array[largest]) {
    largest = right
  }

  // 如果最大值不是当前节点，则交换并继续堆化
  if (largest !== i) {
    ;[array[i], array[largest]] = [array[largest], array[i]]
    heapify(array, n, largest)
  }
}

heapSort([6, 1, 5, 4, 2, 3]) // [1, 2, 3, 4, 5, 6]

堆排序（Heap Sort）是一种高效的排序算法，利用了堆数据结构的特性。以下是堆排序的时间复杂度、空间复杂度及其稳定性的详细分析：

时间复杂度：

• 最优时间复杂度：O(n log n)
  在最优情况下，堆排序的时间复杂度为 O(n log n)，因为构建最大堆和进行堆排序的时间复杂度都是 O(n log n)。

• 最坏时间复杂度：O(n log n)
  在最坏情况下，堆排序的时间复杂度也是 O(n log n)。无论输入数据的顺序如何，都需要将数据构建成最大堆，然后进行排序。

• 平均时间复杂度：O(n log n)

空间复杂度：

堆排序是一种原地排序算法，它只需要常数级别的额外空间来存储堆的数据结构，因此其空间复杂度为 O(1)。

稳定性：

堆排序不是稳定排序算法。在堆排序中，可能会破坏相同元素的相对顺序，因此它不是稳定的排序算法。

堆排序由于其高效性和原地排序的特性，常用于需要稳定且较高性能的排序任务。虽然堆排序的实现相对复杂，但它的时间复杂度稳定在 O(n log n)，在实践中具有较好的性能表现。

基数排序

基数排序（Radix Sort）是一种非比较性的排序算法，它根据关键字的每个位的值来排序。基数排序适用于元素都是整数的数组，其中每个元素都有相同的位数或范围。基本思想是将待排序的元素按照位数进行分组，然后按照每一位的顺序依次排序。

步骤：

1. 按照最低有效位进行排序：从最低位（个位）开始，将元素按照该位的值进行分组（例如 0 到 9），并按照顺序重新排列。

2. 依次对更高位进行排序：对每一位重复上述排序过程，直到按照最高位排序完成。

3. 合并分组：每次按照位数排序后，将所有分组合并为一个数组，形成新的待排序数组。

4. 重复步骤 1~3，直到所有位都被处理完毕。

示例：

假设我们有一个无序数组 [170, 45, 75, 90, 802, 24, 2, 66]，使用基数排序对其进行排序：

1. 按照个位进行排序：
   将数字按照个位的值进行分组：[170, 90, 802, 2], [24], [45, 75], [66]，并按照顺序重新排列：[170, 90, 802, 2, 24, 45, 75, 66]。

2. 按照十位进行排序：
   将数字按照十位的值进行分组：[802, 2], [24], [45, 66], [75], [170, 90]，并按照顺序重新排列：[802, 2, 24, 45, 66, 75, 170, 90]。

3. 按照百位进行排序（如果有的话，本例中没有）。

4. 排序完成，得到有序数组 [2, 24, 45, 66, 75, 90, 170, 802]。

代码实现：

// 获取数字的指定位数上的数字
function getDigit(num, place) {
  return Math.floor(Math.abs(num) / 10 ** place) % 10
}

// 获取数字的位数（最大位数）
function digitCount(num) {
  if (num === 0) return 1
  return Math.floor(Math.log10(Math.abs(num))) + 1
}

// 获取数组中最大数字的位数
function mostDigits(nums) {
  let maxDigits = 0
  for (let i = 0; i < nums.length; i++) {
    maxDigits = Math.max(maxDigits, digitCount(nums[i]))
  }
  return maxDigits
}

function radixSort(nums) {
  const maxDigitCount = mostDigits(nums)

  for (let k = 0; k < maxDigitCount; k++) {
    // 创建 10 个桶（0 到 9）
    const digitBuckets = Array.from({ length: 10 }, () => [])

    // 将数字放入相应的桶中
    for (let i = 0; i < nums.length; i++) {
      const digit = getDigit(nums[i], k)
      digitBuckets[digit].push(nums[i])
    }

    // 合并所有桶中的数字成为新的待排序数组
    nums = [].concat(...digitBuckets)
  }

  return nums
}

radixSort([6, 1, 5, 4, 2, 3]) // [1, 2, 3, 4, 5, 6]

时间复杂度：

• 最优时间复杂度：O(n * k)
  最优情况下，每个关键字的位数相同，基数排序的时间复杂度为 O(n * k)，其中 n 是元素个数，k 是关键字的位数。

• 最坏时间复杂度：O(n * k)
  最坏情况下，基数排序的时间复杂度仍然为 O(n * k)。

• 平均时间复杂度：O(n * k)
  基数排序的平均时间复杂度也为 O(n * k)，其中 k 通常为常数。

基数排序的时间复杂度主要取决于关键字的位数和元素个数，与元素的大小范围无关。

空间复杂度：

基数排序的空间复杂度取决于辅助存储空间的使用，通常需要一个额外的数组来存储中间结果。因此，其空间复杂度为 O(n + k)，其中 n 是元素个数，k 是关键字的范围（通常是 10）。

稳定性：

基数排序是一种稳定排序算法。在基数排序过程中，相同位数的元素根据其原始顺序进行排序，不会改变相等元素的相对位置，因此是稳定的。

基数排序适用于处理整数或字符串等具有固定位数的元素集合。它的时间复杂度相对较低，并且是稳定排序算法，因此在一些特定的排序场景中具有一定的优势。

计数排序

计数排序（Counting Sort）是一种非比较性的排序算法，适用于待排序元素都属于一个有限范围的整数。计数排序的基本思想是通过统计待排序数组中每个元素出现的次数，然后根据统计信息将元素放置到正确的位置上。

步骤：

1. 统计元素出现次数：遍历待排序数组，统计每个元素出现的次数，存储在一个辅助数组中。
2. 累加统计次数：对统计数组进行累加，使得每个位置存储的值表示小于等于该值的元素的个数。
3. 根据统计信息排序：遍历待排序数组，根据统计数组中的信息，将元素放置到正确的位置上。

示例：

假设我们有一个无序数组 [4, 2, 2, 8, 3, 3, 1]，使用计数排序对其进行排序：

1. 统计元素出现次数：统计数组中每个元素的出现次数：[1:1, 2:2, 3:2, 4:1, 8:1]。

2. 累加统计次数：将统计数组中的值进行累加：[1:1, 2:3, 3:5, 4:6, 8:7]，表示小于等于每个元素的个数。

3. 根据统计信息排序：根据累加统计次数，将待排序数组中的元素放置到正确的位置上，得到有序数组 [1, 2, 2, 3, 3, 4, 8]。

代码实现：

function countingSort(array) {
  // 找到待排序数组中的最大值和最小值
  let min = array[0]
  let max = array[0]
  for (let i = 1; i < array.length; i++) {
    if (array[i] < min) min = array[i]
    if (array[i] > max) max = array[i]
  }

  // 创建统计数组，长度为 max - min + 1
  const countArray = new Array(max - min + 1).fill(0)

  // 统计每个元素出现的次数
  for (let i = 0; i < array.length; i++) {
    countArray[array[i] - min]++
  }

  // 根据统计信息对元素进行排序
  let sortedIndex = 0
  for (let i = 0; i < countArray.length; i++) {
    while (countArray[i] > 0) {
      array[sortedIndex] = i + min
      sortedIndex++
      countArray[i]--
    }
  }

  return array
}

countingSort([6, 1, 5, 4, 2, 3]) // [1, 2, 3, 4, 5, 6]

时间复杂度：

• 最优时间复杂度：O(n + k) 最优情况下，计数排序的时间复杂度为 O(n + k)，其中 n 是元素个数，k 是元素的范围。

• 最坏时间复杂度：O(n + k) 最坏情况下，计数排序的时间复杂度仍然为 O(n + k)。

• 平均时间复杂度：O(n + k) 计数排序的平均时间复杂度也为 O(n + k)。

计数排序的时间复杂度主要取决于元素的范围，而与元素的个数无关。

空间复杂度：

计数排序的空间复杂度取决于额外的计数数组和输出数组。因此，其空间复杂度为 O(n + k)，其中 n 是元素个数，k 是元素的范围。

稳定性：

计数排序是一种稳定排序算法。在计数排序中，相同元素的相对顺序不会改变，因此是稳定的。

计数排序适用于对一定范围内的整数进行排序，并且适合于元素范围不是很大的情况下。由于其时间复杂度和空间复杂度均为线性，因此在一些特定的排序场景中具有较好的性能表现。