杂项

基数排序（Radix Sort）

• 原理：基数排序按照数字的位数来排序，从最低位（个位）开始，逐位排序直到最高位。
• 例子：假设我们要对一组整数 [170, 45, 75, 90, 802, 24, 2, 66] 进行排序。
  • 步骤1：首先按照个位数排序：
    • [170, 90, 802, 2, 24, 45, 75, 66]
  • 步骤2：然后按照十位数排序：
    • [802, 2, 24, 45, 66, 170, 75, 90]
  • 步骤3：最后按照百位数排序：
    • [2, 24, 45, 66, 75, 90, 170, 802]
  • 最终得到有序数组 [2, 24, 45, 66, 75, 90, 170, 802]。

计数排序（Counting Sort）

• 原理：计数排序通过统计每个元素出现的次数，然后按次数将元素排列。它适合排序值范围较小的整数。
• 例子：对数组 [4, 2, 2, 8, 3, 3, 1] 进行排序。
  • 步骤1：找出数组中的最大值和最小值，假设最小值是 1，最大值是 8。
  • 步骤2：创建一个计数数组 count，其大小为最大值与最小值的差加一，即 count[1..8]，并初始化为 0。
  • 步骤3：遍历原数组，每个元素对应的 count 数组位置加一：
    • count 变为 [0, 1, 2, 2, 1, 0, 0, 1]
  • 步骤4：累加计数数组，将计数数组转换为位置数组：
    • count 变为 [0, 1, 3, 5, 6, 6, 6, 7]
  • 步骤5：根据 count 数组的位置，将元素放入结果数组，最终得到 [1, 2, 2, 3, 3, 4, 8]。

桶排序（Bucket Sort）

• 原理：桶排序将数据分到多个桶中，每个桶内的数据分别进行排序，最后将各个桶内的数据依次合并得到最终的有序数组。
• 例子：对 [0.42, 0.32, 0.53, 0.25, 0.47, 0.51] 进行排序。
  • 步骤1：假设数据是均匀分布在 [0, 1) 之间，创建若干个空桶（假设 10 个）。
  • 步骤2：将每个元素按照其值放入相应的桶中：
    • 0.42 放入第 4 号桶，0.32 放入第 3 号桶，0.53 放入第 5 号桶……
  • 步骤3：对每个桶内的元素进行排序（可以使用插入排序或其他排序算法）。
    • 第 3 号桶：[0.32, 0.25] -> 排序后：[0.25, 0.32]
    • 第 4 号桶：[0.42, 0.47] -> 排序后：[0.42, 0.47]
    • 第 5 号桶：[0.53, 0.51] -> 排序后：[0.51, 0.53]
  • 步骤4：将所有桶中的元素按顺序合并，得到最终排序结果：
    • [0.25, 0.32, 0.42, 0.47, 0.51, 0.53]。

这三个算法分别通过不同的方式实现排序，适用于不同的数据类型和应用场景。