CS61B 课程笔记（Lecture 36 Radix Sorts)

1. 背景介绍

  • 排序问题的下界：基于比较的排序算法在最坏情况下需要进行 \(Ω(N \log N)\) 次比较操作，这也是归并排序的最坏运行时间。
  • 问题引入：但如果我们不做任何比较呢？可以使用 非比较排序算法 实现更快的排序。

2. 计数排序（Counting Sort）

  • 计数排序思想：
    1. 创建一个新数组，用来记录每个元素出现的次数。
    2. 根据出现次数将原数组中的元素放入正确的位置。
  • 时间复杂度：计数排序可以在 \(Θ(N)\) 时间内完成排序，适用于整数范围较小、值唯一且连续的情况。

3. 最低有效位基数排序（LSD Radix Sort）

  • 基本思想：从最低位（右侧）开始，逐位对数字进行排序，每次排序使用计数排序作为子过程。
  • 过程：
    1. 首先对所有数的最低位进行排序。
    2. 然后对第二低位进行排序，保持前一位排序的稳定性。
    3. 依次向左处理，直到所有位都排序完成。
  • 运行时间：LSD基数排序的运行时间为 \(Θ(WN + WR)\)，其中：
    • \(N\) 为元素的数量，
    • \(W\) 为数字的位数或字符长度，
    • \(R\) 为基数（例如，十进制数的基数为 \(10\)）。
  • 适用场景：适用于所有键长度相同的情况，尤其在极大数据量下表现出色。

4. 最高有效位基数排序（MSD Radix Sort）

  • 基本思想：与LSD相反，从最高位（左侧）开始逐位排序，每次将数据分组，然后在每个分组内部递归进行排序。
  • 过程：
    1. 对数据的最高位进行排序，将数据分组。
    2. 然后对每个分组按照下一位递归进行排序。
    3. 直到所有位都排序完成。
  • 最佳情况：在最理想的情况下，只需查看最高位即可完成排序，时间复杂度为 \(Θ(N + R)\)。
  • 最坏情况：最坏情况下，MSD基数排序会退化为LSD排序，运行时间仍为 \(Θ(WN + WR)\)。

5. 适用场景与对比

  • LSD vs. MSD：
    • LSD排序：适合长度相同、字符差异较小的字符串。
    • MSD排序：适合长度不相等的字符串。
  • LSD vs. 比较排序：
    • 对于非常大的数据集，LSD排序更优，尤其是当 N 极大时。
    • 对于很短且字符差异大的字符串，比较排序（如快速排序）通常更高效，因为 $ N$ 通常较小。

6. 术语总结

  • 基数（Radix）：指数字系统的基数，例如十进制数的基数为$ 10\(，字母表的基数为\) 26$。
  • 基数排序（Radix Sort）：逐位对数据进行排序的一种排序方法。
  • 计数排序（Counting Sort）：通过计数并直接放置元素的位置来完成排序的算法，通常用于基数排序的子过程。
  • LSD排序：从最低有效位开始逐位排序。
  • MSD排序：从最高有效位开始逐位排序。

7. 总结

  • 基数排序是一种非比较排序算法，能够打破基于比较排序的时间下界 \(Ω(N \log N)\)。
  • 计数排序是基数排序的核心子过程，它能够在线性时间 \(Θ(N + R)\) 内完成排序，适用于键值较小的整数集合。
  • LSD和MSD基数排序各有优势，适用于不同类型的数据。