Lec7 Sorting(3)

接下来登场的是$Linear-Time$的$Sort$。😎

线性时间排序（Linear-Time Sorts）

基本原理

线性时间排序算法（如桶排序、计数排序、基数排序等）在某些特定条件下可以达到 $ O(N) $ 的时间复杂度。以下是桶排序（Bucket Sort）的一些基本概念和分析。

桶排序（Bucket Sort）

基本思想：桶排序通过将输入数据分配到若干个桶（或子数组）中，每个桶包含一段特定范围的元素。然后，对每个桶内的元素进行排序，最后将所有桶中的元素合并在一起。
工作原理：
1. 给定一个包含 $ N $ 个元素的数组 $ A $，首先根据元素的键值将这些元素分配到 $ MaxKeyValue $ 个桶中。
2. 如果元素的键值在范围 $[0, MaxKeyValue-1]$ 内，那么元素就被放入对应索引位置的桶中。
3. 每个桶内的元素可以使用其他排序算法（例如快速排序或插入排序）来排序。
4. 最后，按顺序合并各个桶中的元素，得到排序后的结果。

桶排序的实现：

template <typename E, class getKey>
void bucketsort(E A[], int n) {
  List<E> B[MaxKeyValue]; // 一个链表数组
  E item;
  // 将记录分配到各个桶中
  for (int i = 0; i < n; i++) {
    // 根据键值将记录放入桶 B[i]
    B[getKey::key(A[i])].append(A[i]);
  }
  // 扫描 MaxKeyValue 个桶输出排序后的记录
  for (int i = 0; i < MaxKeyValue; i++) {
    for (B[i].setStart(); B[i].getValue(item); B[i].next()) {
      output(item);
    }
  }
}

时间复杂度分析：
- 分配记录到桶：
  - 将 $ N $ 个记录分配到 $ MaxKeyValue $ 个桶中的时间复杂度是 $ (N) $，因为每个记录只需要 O(1) 时间进行分配。
- 扫描并输出记录：
  - 扫描所有桶并输出记录的时间复杂度取决于桶的数量和每个桶中的记录数。
  - 如果桶的数量是 $ (N) $，则总的时间复杂度是 $ (N) $。
  - 如果桶的数量是 $ (N^2) $，则时间复杂度会变成 $ (N + N^2) = (N^2) $。

桶排序的优缺点

优点：
- 适用于键值范围较小的情况（Useful only for a limited key range）：如果键值的范围相对较小，桶排序非常高效。特别是在键值分布均匀的情况下，可以在 $ O(N) $ 的时间内完成排序。
- 空间复杂度低：桶排序的空间复杂度主要依赖于桶的数量。如果桶数量适中，它的空间消耗是可以接受的。
缺点：
- 适用范围有限：桶排序对于键值范围较大的情况表现较差，因为需要为每个可能的键值创建一个桶。这样会导致大量的空间浪费，特别是当键值范围非常大的时候。
- 不能处理任意类型的数据：桶排序通常要求数据是可分割的，并且键值必须具有明确的顺序或范围（例如，整数或浮点数）。

桶排序的应用场景

当数据分布比较均匀，并且键值的范围较小时，桶排序表现非常高效。
桶排序适用于浮动数值排序，如排序分数、价格、时间等。

结论

桶排序可以在合适的条件下达到线性时间排序 $ O(N) $，但是对于大范围的键值数据，它的性能会急剧下降，并且对于大范围的键值会占用过多的空间。

桶排序的进一步推广

一般化桶排序

在经典的桶排序中，每个桶只对应一个键值。然而，可以进一步推广这种方法，使得每个桶对应一组键值范围，而不是单一的键值。这种方法可以更灵活地适应不同类型的数据，并提高桶排序的效率。

基本思想

分配记录到桶：每个桶对应一组键值范围，而不是单一键值。例如，对于键值范围为 $ 0 $ 到 $ 99 $ 的记录，可以通过取键值对 10 取余的方式将记录分配到 10 个桶中。具体而言，可以通过键值的不同位数来决定记录分配到哪个桶中。
桶内排序：每个桶内部可能仍然有多个记录，因此需要对每个桶内的记录进行排序。通常会使用更高效的排序算法（例如插入排序、快速排序等）来排序每个桶内的记录。
合并结果：最后，将各个桶中的排序结果按顺序合并，得到完整的排序列表。

示例

考虑以下包含 12 个记录的数组，键值范围是 $ 0 $ 到 $ 99 $：

1	27, 91, 1, 97, 17, 23, 84, 28, 72, 5, 67, 25

共有 10 个桶，键值范围为 $ 0 $ 到 $ 99 $，我们可以通过取键值的最后一位数字来决定每个记录所在的桶。例如，记录 $ 27 $ 会被分配到桶 $ 27 % 10 = 7 $，记录 $ 91 $ 会被分配到桶 $ 91 % 10 = 1 $，依此类推。

桶分配过程：

第一轮：通过取每个记录的最后一位数字（即 $ A[i] % 10 $）来分配桶：
- 记录 $ 27 $ 被分配到桶 7
- 记录 $ 91 $ 被分配到桶 1
- 记录 $ 1 $ 被分配到桶 1
- 记录 $ 97 $ 被分配到桶 7
- 记录 $ 17 $ 被分配到桶 7
- 记录 $ 23 $ 被分配到桶 3
- 记录 $ 84 $ 被分配到桶 4
- 记录 $ 28 $ 被分配到桶 8
- 记录 $ 72 $ 被分配到桶 2
- 记录 $ 5 $ 被分配到桶 5
- 记录 $ 67 $ 被分配到桶 7
- 记录 $ 25 $ 被分配到桶 5
第二轮：通过取每个记录的第二位数字（即 $ A[i] / 10 $）来决定桶的分配：
- 记录 $ 91 $ 被分配到桶 9
- 记录 $ 1 $ 被分配到桶 0
- 记录 $ 97 $ 被分配到桶 9
- 记录 $ 17 $ 被分配到桶 1
- 记录 $ 23 $ 被分配到桶 2
- 记录 $ 84 $ 被分配到桶 8
- 记录 $ 28 $ 被分配到桶 2
- 记录 $ 72 $ 被分配到桶 7
- 记录 $ 5 $ 被分配到桶 0
- 记录 $ 67 $ 被分配到桶 6
- 记录 $ 25 $ 被分配到桶 2
合并：将每个桶中的记录按顺序输出，得到排序后的结果：
1
1, 5, 17, 23, 25, 27, 28, 67, 72, 84, 91, 97

时间复杂度分析

分配记录到桶：分配记录到桶的过程只需要 $ O(N) $ 的时间，因为每个记录的键值都可以在常数时间内计算出应该放入的桶。
桶内排序：每个桶内部的排序过程通常使用比较排序算法，时间复杂度取决于桶内记录的数量。如果每个桶内有 $ O(N / b) $ 个记录（假设每个桶的记录数大致均匀），那么每个桶的排序时间是 $ O(N / b (N / b)) $，其中 $ b $ 是桶的数量。
合并结果：合并所有桶的过程也是 $ O(N) $ 的时间复杂度。

因此，如果桶内的记录分布均匀且每个桶内的记录数较少，整体的时间复杂度是 $ O(N) $。如果桶内的记录较多，桶排序的性能会接近于 $ O(N N) $。

适用场景

这种改进的桶排序适用于：

键值范围较小，并且数据分布均匀的情况。
对于键值范围较大的情况，可以使用多轮桶排序，并通过不同的位数来分配桶，从而使得排序过程变得更加高效。

结论

通过将每个桶分配给一个键值范围，并通过多轮桶排序来进一步细化排序过程，桶排序在某些情况下能够显著提高性能，尤其是在数据分布均匀、键值范围较小的情况下。

基数排序（Radix Sort）

概述：
基数排序是一种非比较型的排序算法，它通过将键值的每一位按顺序分配到不同的桶中来排序。这个过程基于键值的基数（即数值的进制），因此也被称为“进制排序”。

基数（Radix）：表示每一位的进制，常见的如十进制（10）、二进制（2）、八进制（8）、十六进制（16）等。
桶：每一位的值决定了记录应该被放置在哪个桶中。

基数排序的工作原理

分配记录到桶：基数排序从键值的最低位（右侧）开始，将记录按照每一位的值分配到不同的桶中。然后，再按顺序从桶中取出记录。
重复操作：依次从低位到高位处理，直到处理完所有的位。
排序稳定性：基数排序是稳定的，即相同的键值在排序前后的相对顺序不会改变。

示例：

假设有一组记录的键值为 999，并且桶的数量是 8（即以八进制进行分配），可以按照以下步骤进行排序：

第一轮：根据 999 % 8 = 7，键值 999 被放入桶 7。
第二轮：根据 (999 / 8) % 8 = 4，键值 999 被放入桶 4。
第三轮：根据 (999 / 8^2) % 8 = 7，键值 999 被放入桶 7。
第四轮：根据 (999 / 8^3) % 8 = 1，键值 999 被放入桶 1。

然后，将所有桶中的元素按顺序取出，最终得到排序结果。

算法实现：

基数排序的实现可以分为以下几个步骤：

1. 使用桶存储记录：

void radixSortA(vector<string> &arr, int stringLen) {
    const int BUCKETS = 256;  // 假设字符集为 ASCII 字符
    vector<vector<string>> buckets(BUCKETS);
    for (int pos = stringLen - 1; pos >= 0; --pos) {
        for (string &s : arr)
            // 将字符根据位置添加到相应的桶
            buckets[s[pos]].push_back(std::move(s));
        int idx = 0;
        // 将所有桶中的元素按顺序取出
        for (auto &thisBucket : buckets) {
            for (string &s : thisBucket)
                arr[idx++] = std::move(s);
            thisBucket.clear();
        }
    }
}

2. 计数基数排序：

template <typename E, typename getKey>
void radix(E A[], E B[], int n, int r, int b, int cnt[]) {
    int j;
    for (int i = 0, btoi = 1; i < r; i++, btoi *= b) {
        for (j = 0; j < b; j++) cnt[j] = 0;  // 初始化桶计数
        // 计算每个桶的记录数
        for (j = 0; j < n; j++) cnt[(getKey::key(A[j]) / btoi) % b]++;
        // 计算每个桶的累积计数
        for (j = 1; j < b; j++) cnt[j] += cnt[j - 1];
        // 将记录放入桶中，从桶底部开始
        for (j = n - 1; j >= 0; j--)
            B[--cnt[(getKey::key(A[j]) / btoi) % b]] = A[j];
        // 将桶中的记录复制回原数组
        for (j = 0; j < n; j++) A[j] = B[j];
    }
}

时间复杂度分析

时间复杂度：基数排序的时间复杂度是 $O(r(N + b))$，其中：
- $r$ 是排序的轮数，即排序所需的位数。
- $N$ 是待排序的记录数。
- $b$ 是桶的数量（即基数）。
通常，$b$ 是一个固定值（例如 10 或 256），因此时间复杂度主要取决于 $r$ 和 $N$。
r 与 N 的关系：
- 如果基数 $b$ 是一个常数，那么 $r$ 由 $N$ 的大小决定。通常 $r = O(\log_b N)$。
- 因此，基数排序的最坏情况下时间复杂度是 $O(N \log_b N)$，这使得它在大规模数据集时效率较高。

例子

基数排序的优缺点

优点：
- 非比较型排序，避免了传统比较排序的 $O(N \log N)$ 最优时间复杂度限制。
- 对于大量数据，尤其是键值较小的情况，基数排序可以表现得非常高效。
- 稳定排序。
缺点：
- 需要额外的存储空间（通常是桶的数组）。
- 不适用于所有类型的数据，通常需要在数据范围较小、键值分布均匀的情况下效果较好。
- 不是“原地”排序，意味着它不直接修改输入数组。

问题1：

使用基数排序算法对可变长度的字符串进行排序，演示输入字符串的排序过程：

输入：
"We, can, extend, either, version, of, radix, sort, to, work, with, variable, length, strings"

基数排序应该基于每个字符的ASCII值，从最右侧的字符（最低位字符）开始排序，然后向左侧的字符（最高位字符）进行排序。

解释：

我们使用基数排序对字符串列表进行排序，排序的依据是每个字符的ASCII值，从右侧的字符开始排序。

步骤：

第1步 - 按最后一个字符排序：
- 通过字符的ASCII值对字符串按最后一个字符进行排序。
第2步 - 按倒数第二个字符排序：
- 在按最后一个字符排序后，继续按倒数第二个字符排序。
继续按每个字符排序，直到排序到第一个字符为止。

输入：

"We, can, extend, either, version, of, radix, sort, to, work, with, variable, length, strings"

解答：

第1步：按最后一个字符排序：

每个字符串的最后一个字符是：
"We", "can", "extend", "either", "version", "of", "radix", "sort", "to", "work", "with", "variable", "length", "strings"
- We → "e" (ASCII 101)
- Can → "n" (ASCII 110)
- Extend → "d" (ASCII 100)
- Either → "r" (ASCII 114)
- Version → "n" (ASCII 110)
- Of → "f" (ASCII 102)
- Radix → "x" (ASCII 120)
- Sort → "t" (ASCII 116)
- To → "o" (ASCII 111)
- Work → "k" (ASCII 107)
- With → "h" (ASCII 104)
- Variable → "e" (ASCII 101)
- Length → "h" (ASCII 104)
- Strings → "s" (ASCII 115)