有趣的算法之计数排序

基于比较的算法，其平均时间复杂度不会好过 $O(n \log n)$，而计数排序是一种非比较排序算法，可以在特定条件下实现线性时间复杂度 $O(k + n)$，其中 $n$ 是输入数组的大小，$k$ 是输入数据的范围。

先来看下，为什么基于比较的算法时间复杂度不能好过 $O(n \log n)$？

1
2
A > B ?
A < B ?

比较排序算法的核心是通过比较元素之间的大小关系来确定它们的顺序，核心永远都是在比大小。

假设我们有n个不同的元素，能有多少种排序方式：$n!$，每次比较只能将元素分成两部分，所以需要至少 $\log_2(n!)$ 次比较才能确定排序结果。根据斯特林公式，$\log_2(n!)$ 的时间复杂度为 $O(n \log n)$，因此基于比较的排序算法的平均时间复杂度不能好过 $O(n \log n)$。

计数排序的核心思想是统计每个元素出现的次数，然后根据这些统计信息来构建排序结果。它适用于输入数据范围较小且为整数的情况。

计数排序的步骤如下：

  1. 找到输入数据中的最大值和最小值，以确定计数数组的大小。
  2. 创建一个计数数组，大小为最大值和最小值之间的范围加1，并初始化为0。
  3. 遍历输入数组，统计每个元素出现的次数，并将其存储在计数数组中。
  4. 对计数数组进行累加，以便在构建输出数组时能够直接使用计数数组中的值来确定每个元素在输出数组中的位置。
  5. 创建一个输出数组，大小与输入数组相同。
  6. 从输入数组的末尾开始遍历，根据计数数组中的值来将元素放置在输出数组的正确位置，并更新计数数组中的值。
  7. 将输出数组复制回输入数组，以完成排序。

举个例子：

对数组 input[4, 2, 2, 8, 3, 3, 1] 进行计数排序：

  1. 最大值为 8，最小值为 1，所以计数数组大小为 8 - 1 + 1 = 8。
  2. 创建计数数组 count，初始化为 [0, 0, 0, 0, 0, 0, 0, 0]。
  3. 遍历输入数组，统计每个元素的出现次数：
    • 4 出现 1 次，count[4] = 1
    • 2 出现 2 次，count[2] = 2
    • 8 出现 1 次，count[8] = 1
    • 3 出现 2 次，count[3] = 2
    • 1 出现 1 次，count[1] = 1
      计数数组 count 变为 [0, 1, 2, 2, 1, 0, 0, 0, 1]。
  4. 对计数数组进行累加：
    • count[1] = 1
    • count[2] = 1 + 2 = 3
    • count[3] = 3 + 2 = 5
    • count[4] = 5 + 1 = 6
    • count[5] = 6 + 0 = 6
    • count[6] = 6 + 0 = 6
    • count[7] = 6 + 0 = 6
    • count[8] = 6 + 1 = 7
      计数数组 count 变为 [0, 1, 3, 5, 6, 6, 6, 6, 7]。
  5. 创建输出数组 output，大小为 7。
  6. 从输入数组input的末尾开始遍历，根据计数数组中的值来将元素放置在输出数组的正确位置：
    • 1 放在 output[count[1] - 1] = output[0] 的位置，output 变为 [1, _, _, _, _, _, _]，count[1] 更新为 0。
    • 3 放在 output[count[3] - 1] = output[4] 的位置，output 变为 [1, _, _, _, 3, _, _], count[3] 更新为 4。
    • 3 放在 output[count[3] - 1] = output[3] 的位置，output 变为 [1, _, _, 3, 3, _, _]，count[3] 更新为 3。
    • 8 放在 output[count[8] - 1] = output[6] 的位置，output 变为 [1, _, _, 3, 3, _, 8]，count[8] 更新为 6。
    • 2 放在 output[count[2] - 1] = output[2] 的位置，output 变为 [1, _, 2, 3, 3, _, 8]，count[2] 更新为 2。
    • 2 放在 output[count[2] - 1] = output[1] 的位置，output 变为 [1, 2, 2, 3, 3, _, 8]，count[2] 更新为 1。
    • 4 放在 output[count[4] - 1] = output[5] 的位置，output 变为 [1, 2, 2, 3, 3, 4, 8]，count[4] 更新为 5。
      输出数组 output 最终为 [1, 2, 2, 3, 3, 4, 8]。
  7. 将输出数组复制回输入数组，完成排序。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void countingSort(vector<int>& arr) {
    if (arr.empty()) return;

    int maxVal = *max_element(arr.begin(), arr.end());
    int minVal = *min_element(arr.begin(), arr.end());
    int range = maxVal - minVal + 1;

    vector<int> count(range, 0);
    vector<int> output(arr.size());

    // 统计每个元素的出现次数
    for (int num : arr) {
        count[num - minVal]++;
    }

    // 累加计数数组
    for (int i = 1; i < count.size(); i++) {
        count[i] += count[i - 1];
    }

    // 构建输出数组
    for (int i = arr.size() - 1; i >= 0; i--) {
        output[count[arr[i] - minVal] - 1] = arr[i];
        count[arr[i] - minVal]--;
    }

    // 将输出数组复制回输入数组
    for (int i = 0; i < arr.size(); i++) {
        arr[i] = output[i];
    }
}

时间复杂度和空间复杂度：

  • 时间复杂度：$O(n + k)$，其中 $n$ 是输入数组的大小，$k$ 是输入数据的范围。
  • 空间复杂度：$O(n + k)$，其中 $n$ 是输出数组的大小，$k$ 是计数数组的大小。

适用场景：

计数排序适用于输入数据范围较小且为整数的情况，例如对年龄、考试成绩等进行排序。对于范围较大的数据，计数排序可能会占用过多的空间，因此不适合使用。

基数排序

基数排序是一种非比较排序算法，它通过将整数分解成不同的数字位来进行排序。基数排序通常使用计数排序作为子程序来对每个位进行排序。基数排序的时间复杂度为 $O(d \cdot (n + k))$，其中 $d$ 是数字的位数，$n$ 是输入数组的大小，

其核心思想是：对每个位做计数排序。

比如，对数组 input[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]。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void radixSort(vector<int>& arr) {
    if (arr.empty()) return;

    int maxVal = *max_element(arr.begin(), arr.end());

    // 对每个位进行计数排序
    for (int exp = 1; maxVal / exp > 0; exp *= 10) {
        countingSortForRadix(arr, exp);
    }
}

void countingSortForRadix(vector<int>& arr, int exp) {
    vector<int> output(arr.size());
    vector<int> count(10, 0);

    // 统计每个数字出现的次数
    for (int num : arr) {
        count[(num / exp) % 10]++;
    }

    // 累加计数数组
    for (int i = 1; i < count.size(); i++) {
        count[i] += count[i - 1];
    }

    // 构建输出数组
    for (int i = arr.size() - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }

    // 将输出数组复制回输入数组
    for (int i = 0; i < arr.size(); i++) {
        arr[i] = output[i];
    }
}

时间复杂度和空间复杂度：

  • 时间复杂度：$O(d \cdot (n + k))$，其中 $d$ 是数字的位数，$n$ 是输入数组的大小，$k$ 是计数数组的大小（对于十进制数字，$k$ 通常为 10）。
  • 空间复杂度：$O(n + k)$，其中 $n$ 是输出数组的大小，$k$ 是计数数组的大小。

适用场景：

基数排序适用于输入数据范围较大且为整数的情况，例如对电话号码、身份证号码等进行排序。对于范围较小的数据，基数排序可能会占用过多的空间，因此不适合使用。

计数排序解决“小值域问题”

基数排序把“大数问题”拆成多个“小值域问题”

为什么基数排序必须稳定，否则一定排错？

基数排序的核心是对每个位进行排序，如果排序算法不稳定，那么在对某个位进行排序时，可能会改变之前位的相对顺序，从而导致最终排序结果错误。

高位排序时，必须要保留低位排序的结果，否则就乱了。