跳转至

11.9   计数排序

计数排序(counting sort)通过统计元素数量来实现排序,通常应用于整数数组。

11.9.1   简单实现

先来看一个简单的例子。给定一个长度为 \(n\) 的数组 nums ,其中的元素都是“非负整数”,计数排序的整体流程如图 11-16 所示。

  1. 遍历数组,找出其中的最大数字,记为 \(m\) ,然后创建一个长度为 \(m + 1\) 的辅助数组 counter 。
  2. 借助 counter 统计 nums 中各数字的出现次数,其中 counter[num] 对应数字 num 的出现次数。统计方法很简单,只需遍历 nums(设当前数字为 num),每轮将 counter[num] 增加 \(1\) 即可。
  3. 由于 counter 的各个索引天然有序,因此相当于所有数字已经排序好了。接下来,我们遍历 counter ,根据各数字出现次数从小到大的顺序填入 nums 即可。

图 11-16   计数排序流程

图解 11-16:统计每个整数的次数,再按次数写回

用数字本身作索引统计频数,再按数值递增顺序写回。

待排序数组为 nums = [1, 0, 1, 2, 0, 4, 0, 2, 2, 4],元素均为非负整数且最大值为 4,因此创建包含索引 0 至 4 共五个位置的计数数组 counter。counter[num] 记录数字 num 的出现次数,其索引直接对应数值本身,而非原数组下标。

counter[3] = 0 表示输入没有数字 3。按索引 0 至 4 读取频数,依次写出三个 0、两个 1、三个 2 和两个 4;下方三张表分别列出原始输入、数字频数与写回结果。

原始输入
索引值
01
10
21
32
40
54
60
72
82
94
数字频数
数字出现次数
03
12
23
30
42
写回结果
索引值
00
10
20
31
41
52
62
72
84
94

这种简单实现按频数重建整数序列,不保留相等数值各自的原输入身份;若需对携带附加属性的对象稳定排序,须进一步保留对象身份并安排写入位置。

代码如下所示:

counting_sort.py
def counting_sort_naive(nums: list[int]):
    """计数排序"""
    # 简单实现,无法用于排序对象
    # 1. 统计数组最大元素 m
    m = max(nums)
    # 2. 统计各数字的出现次数
    # counter[num] 代表 num 的出现次数
    counter = [0] * (m + 1)
    for num in nums:
        counter[num] += 1
    # 3. 遍历 counter ,将各元素填入原数组 nums
    i = 0
    for num in range(m + 1):
        for _ in range(counter[num]):
            nums[i] = num
            i += 1
counting_sort.cpp
/* 计数排序 */
// 简单实现,无法用于排序对象
void countingSortNaive(vector<int> &nums) {
    // 1. 统计数组最大元素 m
    int m = 0;
    for (int num : nums) {
        m = max(m, num);
    }
    // 2. 统计各数字的出现次数
    // counter[num] 代表 num 的出现次数
    vector<int> counter(m + 1, 0);
    for (int num : nums) {
        counter[num]++;
    }
    // 3. 遍历 counter ,将各元素填入原数组 nums
    int i = 0;
    for (int num = 0; num < m + 1; num++) {
        for (int j = 0; j < counter[num]; j++, i++) {
            nums[i] = num;
        }
    }
}
counting_sort.java
/* 计数排序 */
// 简单实现,无法用于排序对象
void countingSortNaive(int[] nums) {
    // 1. 统计数组最大元素 m
    int m = 0;
    for (int num : nums) {
        m = Math.max(m, num);
    }
    // 2. 统计各数字的出现次数
    // counter[num] 代表 num 的出现次数
    int[] counter = new int[m + 1];
    for (int num : nums) {
        counter[num]++;
    }
    // 3. 遍历 counter ,将各元素填入原数组 nums
    int i = 0;
    for (int num = 0; num < m + 1; num++) {
        for (int j = 0; j < counter[num]; j++, i++) {
            nums[i] = num;
        }
    }
}
counting_sort.cs
/* 计数排序 */
// 简单实现,无法用于排序对象
void CountingSortNaive(int[] nums) {
    // 1. 统计数组最大元素 m
    int m = 0;
    foreach (int num in nums) {
        m = Math.Max(m, num);
    }
    // 2. 统计各数字的出现次数
    // counter[num] 代表 num 的出现次数
    int[] counter = new int[m + 1];
    foreach (int num in nums) {
        counter[num]++;
    }
    // 3. 遍历 counter ,将各元素填入原数组 nums
    int i = 0;
    for (int num = 0; num < m + 1; num++) {
        for (int j = 0; j < counter[num]; j++, i++) {
            nums[i] = num;
        }
    }
}
counting_sort.go
/* 计数排序 */
// 简单实现,无法用于排序对象
func countingSortNaive(nums []int) {
    // 1. 统计数组最大元素 m
    m := 0
    for _, num := range nums {
        if num > m {
            m = num
        }
    }
    // 2. 统计各数字的出现次数
    // counter[num] 代表 num 的出现次数
    counter := make([]int, m+1)
    for _, num := range nums {
        counter[num]++
    }
    // 3. 遍历 counter ,将各元素填入原数组 nums
    for i, num := 0, 0; num < m+1; num++ {
        for j := 0; j < counter[num]; j++ {
            nums[i] = num
            i++
        }
    }
}
counting_sort.swift
/* 计数排序 */
// 简单实现,无法用于排序对象
func countingSortNaive(nums: inout [Int]) {
    // 1. 统计数组最大元素 m
    let m = nums.max()!
    // 2. 统计各数字的出现次数
    // counter[num] 代表 num 的出现次数
    var counter = Array(repeating: 0, count: m + 1)
    for num in nums {
        counter[num] += 1
    }
    // 3. 遍历 counter ,将各元素填入原数组 nums
    var i = 0
    for num in 0 ..< m + 1 {
        for _ in 0 ..< counter[num] {
            nums[i] = num
            i += 1
        }
    }
}
counting_sort.js
/* 计数排序 */
// 简单实现,无法用于排序对象
function countingSortNaive(nums) {
    // 1. 统计数组最大元素 m
    let m = Math.max(...nums);
    // 2. 统计各数字的出现次数
    // counter[num] 代表 num 的出现次数
    const counter = new Array(m + 1).fill(0);
    for (const num of nums) {
        counter[num]++;
    }
    // 3. 遍历 counter ,将各元素填入原数组 nums
    let i = 0;
    for (let num = 0; num < m + 1; num++) {
        for (let j = 0; j < counter[num]; j++, i++) {
            nums[i] = num;
        }
    }
}
counting_sort.ts
/* 计数排序 */
// 简单实现,无法用于排序对象
function countingSortNaive(nums: number[]): void {
    // 1. 统计数组最大元素 m
    let m: number = Math.max(...nums);
    // 2. 统计各数字的出现次数
    // counter[num] 代表 num 的出现次数
    const counter: number[] = new Array<number>(m + 1).fill(0);
    for (const num of nums) {
        counter[num]++;
    }
    // 3. 遍历 counter ,将各元素填入原数组 nums
    let i = 0;
    for (let num = 0; num < m + 1; num++) {
        for (let j = 0; j < counter[num]; j++, i++) {
            nums[i] = num;
        }
    }
}
counting_sort.dart
/* 计数排序 */
// 简单实现,无法用于排序对象
void countingSortNaive(List<int> nums) {
  // 1. 统计数组最大元素 m
  int m = 0;
  for (int _num in nums) {
    m = max(m, _num);
  }
  // 2. 统计各数字的出现次数
  // counter[_num] 代表 _num 的出现次数
  List<int> counter = List.filled(m + 1, 0);
  for (int _num in nums) {
    counter[_num]++;
  }
  // 3. 遍历 counter ,将各元素填入原数组 nums
  int i = 0;
  for (int _num = 0; _num < m + 1; _num++) {
    for (int j = 0; j < counter[_num]; j++, i++) {
      nums[i] = _num;
    }
  }
}
counting_sort.rs
/* 计数排序 */
// 简单实现,无法用于排序对象
fn counting_sort_naive(nums: &mut [i32]) {
    // 1. 统计数组最大元素 m
    let m = *nums.iter().max().unwrap();
    // 2. 统计各数字的出现次数
    // counter[num] 代表 num 的出现次数
    let mut counter = vec![0; m as usize + 1];
    for &num in nums.iter() {
        counter[num as usize] += 1;
    }
    // 3. 遍历 counter ,将各元素填入原数组 nums
    let mut i = 0;
    for num in 0..m + 1 {
        for _ in 0..counter[num as usize] {
            nums[i] = num;
            i += 1;
        }
    }
}
counting_sort.c
/* 计数排序 */
// 简单实现,无法用于排序对象
void countingSortNaive(int nums[], int size) {
    // 1. 统计数组最大元素 m
    int m = 0;
    for (int i = 0; i < size; i++) {
        if (nums[i] > m) {
            m = nums[i];
        }
    }
    // 2. 统计各数字的出现次数
    // counter[num] 代表 num 的出现次数
    int *counter = calloc(m + 1, sizeof(int));
    for (int i = 0; i < size; i++) {
        counter[nums[i]]++;
    }
    // 3. 遍历 counter ,将各元素填入原数组 nums
    int i = 0;
    for (int num = 0; num < m + 1; num++) {
        for (int j = 0; j < counter[num]; j++, i++) {
            nums[i] = num;
        }
    }
    // 4. 释放内存
    free(counter);
}
counting_sort.kt
/* 计数排序 */
// 简单实现,无法用于排序对象
fun countingSortNaive(nums: IntArray) {
    // 1. 统计数组最大元素 m
    var m = 0
    for (num in nums) {
        m = max(m, num)
    }
    // 2. 统计各数字的出现次数
    // counter[num] 代表 num 的出现次数
    val counter = IntArray(m + 1)
    for (num in nums) {
        counter[num]++
    }
    // 3. 遍历 counter ,将各元素填入原数组 nums
    var i = 0
    for (num in 0..<m + 1) {
        var j = 0
        while (j < counter[num]) {
            nums[i] = num
            j++
            i++
        }
    }
}
counting_sort.rb
### 计数排序 ###
def counting_sort_naive(nums)
  # 简单实现,无法用于排序对象
  # 1. 统计数组最大元素 m
  m = 0
  nums.each { |num| m = [m, num].max }
  # 2. 统计各数字的出现次数
  # counter[num] 代表 num 的出现次数
  counter = Array.new(m + 1, 0)
  nums.each { |num| counter[num] += 1 }
  # 3. 遍历 counter ,将各元素填入原数组 nums
  i = 0
  for num in 0...(m + 1)
    (0...counter[num]).each do
      nums[i] = num
      i += 1
    end
  end
end
可视化运行

计数排序与桶排序的联系

从桶排序的角度看,我们可以将计数排序中的计数数组 counter 的每个索引视为一个桶,将统计数量的过程看作将各个元素分配到对应的桶中。本质上,计数排序是桶排序在整型数据下的一个特例。

11.9.2   完整实现

细心的读者可能发现了,如果输入数据是对象,上述步骤 3. 就失效了。假设输入数据是商品对象,我们想按照商品价格(类的成员变量)对商品进行排序,而上述算法只能给出价格的排序结果。

那么如何才能得到原数据的排序结果呢?我们首先计算 counter 的“前缀和”。顾名思义,索引 i 处的前缀和 prefix[i] 等于数组前 i 个元素之和:

\[ \text{prefix}[i] = \sum_{j=0}^i \text{counter[j]} \]

前缀和具有明确的意义,prefix[num] - 1 代表元素 num 在结果数组 res 中最后一次出现的索引。这个信息非常关键,因为它告诉我们各个元素应该出现在结果数组的哪个位置。接下来,我们倒序遍历原数组 nums 的每个元素 num ,在每轮迭代中执行以下两步。

  1. 将 num 填入数组 res 的索引 prefix[num] - 1 处。
  2. 令前缀和 prefix[num] 减小 \(1\) ,从而得到下次放置 num 的索引。

遍历完成后,数组 res 中就是排序好的结果,最后使用 res 覆盖原数组 nums 即可。图 11-17 展示了完整的计数排序流程。

图 11-17   计数排序步骤

图解 11-17:前缀和计数排序的稳定写入

将频数累加为前缀和以定位写入下标,倒序遍历原数组填入 res 并递减计数,最后覆盖 nums。

原数组为 nums = [1, 0, 1, 2, 0, 4, 0, 2, 2, 4](索引 0 至 9),数值范围为 0 至 4,频数数组为 counter = [3, 2, 3, 0, 2]。

对 counter 计算前缀和得到初始 prefix = [3, 5, 8, 8, 10]。初始 prefix[num] 表示小于或等于 num 的元素总数,对于确实出现的数值 num,prefix[num] - 1 正好是它在结果数组 res 中最后一次出现的目标索引。图将这组数称为 prefix;正文代码直接在 counter 中累加并覆盖存放前缀和。

结果数组 res 共有十个槽位。图中尚未写入元素的槽位留白,用于区分“尚未放置元素”与“已写入数值 0”(尽管代码中用 0 初始化 res,画面仍以空白格表示未写入状态)。

从右向左遍历 nums:将当前值 num 写入 res[prefix[num] − 1],随后令 prefix[num] 减 1。若后续还有同值元素,递减后的 prefix[num] − 1 就是它的下一个写入索引;因此 prefix 会随写入改变,不再是最初的前缀和。

倒序遍历与从右向左填充相配合,使得原数组中靠右的相等元素先填入结果区段的靠右位置、靠左的相等元素后填入靠左位置,从而保证排序的稳定性。本图前四次分别展示原索引 9、8、7、6 的写入过程,随后省略中间六次写入直接展示遍历完成状态,最后用 res 覆盖 nums。

  1. 统计频数

    遍历原数组 nums,统计数字 0、1、2、3、4 各自出现的次数,生成长度为 5 的计数数组 counter = [3, 2, 3, 0, 2]。尚未求前缀和,也未写入结果。

    计数排序第 1 步:nums
    索引nums 值
    01
    10
    21
    32
    40
    54
    60
    72
    82
    94
    计数排序第 1 步:频数 counter
    数字 num出现次数
    03
    12
    23
    30
    42
  2. 累加频数,准备结果数组

    对 counter 依次累加计算前缀和,得到 prefix = [3, 5, 8, 8, 10],同时准备好十格空白的结果数组 res。根据 prefix[num] - 1 可知:数字 0 的最后一个目标位置是 3 - 1 = 2,数字 2 的最后位置是 8 - 1 = 7,数字 4 的最后位置是 10 - 1 = 9;数字 3 未出现,不会触发写入。

    计数排序第 2 步:nums 与 res
    索引nums 值res 值或写入状态res 元素的原始索引
    01未写入无
    10未写入无
    21未写入无
    32未写入无
    40未写入无
    54未写入无
    60未写入无
    72未写入无
    82未写入无
    94未写入无
    计数排序第 2 步:初始 prefix
    数字 numprefix[num]
    03
    15
    28
    38
    410
  3. 将末尾的 4 写入索引 9

    指针 num 指向原数组最右端索引 9,元素值为 4。先根据递减前的 prefix[4] = 10 计算出目标索引 10 - 1 = 9,将 4 填入 res[9];再将 prefix[4] 自减 1 变为 9。画面中展示的是已完成自减后的 prefix。目前仅处理了原索引 9,其余九格未写入。

    计数排序第 3 步:nums 与 res
    索引nums 值res 值或写入状态res 元素的原始索引
    01未写入无
    10未写入无
    21未写入无
    32未写入无
    40未写入无
    54未写入无
    60未写入无
    72未写入无
    82未写入无
    9449
    计数排序第 3 步:递减后的 prefix
    数字 numprefix[num]
    03
    15
    28
    38
    49
  4. 将原索引 8 的 2 写入索引 7

    指针 num 左移至原数组索引 8,元素值为 2。先根据递减前的 prefix[2] = 8 计算出目标索引 8 - 1 = 7,将 2 填入 res[7];再将 prefix[2] 自减 1 变为 7。画面中展示的是已完成自减后的 prefix。已处理原索引 9 至 8。

    计数排序第 4 步:nums 与 res
    索引nums 值res 值或写入状态res 元素的原始索引
    01未写入无
    10未写入无
    21未写入无
    32未写入无
    40未写入无
    54未写入无
    60未写入无
    7228
    82未写入无
    9449
    计数排序第 4 步:递减后的 prefix
    数字 numprefix[num]
    03
    15
    27
    38
    49
  5. 将原索引 7 的 2 写入索引 6

    指针 num 左移至原数组索引 7,遇到第二个值为 2 的元素。根据上一轮递减后的 prefix[2] = 7 计算出目标索引 7 - 1 = 6,将该 2 填入 res[6](排在刚才那个 2 的左侧,保持原有相对次序);随后将 prefix[2] 自减 1 变为 6。已处理原索引 9 至 7。

    计数排序第 5 步:nums 与 res
    索引nums 值res 值或写入状态res 元素的原始索引
    01未写入无
    10未写入无
    21未写入无
    32未写入无
    40未写入无
    54未写入无
    6027
    7228
    82未写入无
    9449
    计数排序第 5 步:递减后的 prefix
    数字 numprefix[num]
    03
    15
    26
    38
    49
  6. 将原索引 6 的 0 写入索引 2

    指针 num 左移至原数组索引 6,元素值为 0。先根据递减前的 prefix[0] = 3 计算出目标索引 3 - 1 = 2,将 0 填入 res[2];再将 prefix[0] 自减 1 变为 2。画面中展示的是已完成自减后的 prefix。已处理原索引 9 至 6。res[2] 是实际写入的 0,表中“未写入”表示尚未放置元素。

    计数排序第 6 步:nums 与 res
    索引nums 值res 值或写入状态res 元素的原始索引
    01未写入无
    10未写入无
    2106
    32未写入无
    40未写入无
    54未写入无
    6027
    7228
    82未写入无
    9449
    计数排序第 6 步:递减后的 prefix
    数字 numprefix[num]
    02
    15
    26
    38
    49
  7. 完成其余六次写入

    继续倒序处理原数组索引 5 至 0 的其余六个元素(依次为 4、0、2、1、0、1),分别填入 res 的索引 8、1、5、4、0、3。图中省略了这六步中间画面,直接跳到遍历结束状态:此时 res 已全部填满为有序序列,而上方原数组 nums 尚未被覆盖。

    计数排序第 7 步:nums 与 res
    索引nums 值res 值或写入状态res 元素的原始索引
    0101
    1004
    2106
    3210
    4012
    5423
    6027
    7228
    8245
    9449
    计数排序第 7 步:递减后的 prefix
    数字 numprefix[num]
    00
    13
    25
    38
    48
  8. 把结果复制回 nums

    最后将有序结果数组 res 中的十个元素按索引复制回原数组 nums,上方 nums 随即更新为 [0, 0, 0, 1, 1, 2, 2, 2, 4, 4],计数排序全部完成。此时 prefix = [0, 3, 5, 8, 8]:对出现过的 0、1、2、4,分别等于它们在 res 中首次出现的索引 0、3、5、8。数字 3 未出现,prefix[3] = 8 没有对应的 3;它与 4 的起始索引相同。最终 prefix[num] 等于小于 num 的输入元素个数;例如小于 3 的共有 8 项,因此未出现的 3 也对应 8。

    计数排序第 8 步:nums 与 res
    索引nums 值res 值或写入状态res 元素的原始索引
    0001
    1004
    2006
    3110
    4112
    5223
    6227
    7228
    8445
    9449
    计数排序第 8 步:最终 prefix(同第 7 步)
    数字 numprefix[num]
    00
    13
    25
    38
    48

计数排序的实现代码如下所示:

counting_sort.py
def counting_sort(nums: list[int]):
    """计数排序"""
    # 完整实现,可排序对象,并且是稳定排序
    # 1. 统计数组最大元素 m
    m = max(nums)
    # 2. 统计各数字的出现次数
    # counter[num] 代表 num 的出现次数
    counter = [0] * (m + 1)
    for num in nums:
        counter[num] += 1
    # 3. 求 counter 的前缀和,将“出现次数”转换为“尾索引”
    # 即 counter[num]-1 是 num 在 res 中最后一次出现的索引
    for i in range(m):
        counter[i + 1] += counter[i]
    # 4. 倒序遍历 nums ,将各元素填入结果数组 res
    # 初始化数组 res 用于记录结果
    n = len(nums)
    res = [0] * n
    for i in range(n - 1, -1, -1):
        num = nums[i]
        res[counter[num] - 1] = num  # 将 num 放置到对应索引处
        counter[num] -= 1  # 令前缀和自减 1 ,得到下次放置 num 的索引
    # 使用结果数组 res 覆盖原数组 nums
    for i in range(n):
        nums[i] = res[i]
counting_sort.cpp
/* 计数排序 */
// 完整实现,可排序对象,并且是稳定排序
void countingSort(vector<int> &nums) {
    // 1. 统计数组最大元素 m
    int m = 0;
    for (int num : nums) {
        m = max(m, num);
    }
    // 2. 统计各数字的出现次数
    // counter[num] 代表 num 的出现次数
    vector<int> counter(m + 1, 0);
    for (int num : nums) {
        counter[num]++;
    }
    // 3. 求 counter 的前缀和,将“出现次数”转换为“尾索引”
    // 即 counter[num]-1 是 num 在 res 中最后一次出现的索引
    for (int i = 0; i < m; i++) {
        counter[i + 1] += counter[i];
    }
    // 4. 倒序遍历 nums ,将各元素填入结果数组 res
    // 初始化数组 res 用于记录结果
    int n = nums.size();
    vector<int> res(n);
    for (int i = n - 1; i >= 0; i--) {
        int num = nums[i];
        res[counter[num] - 1] = num; // 将 num 放置到对应索引处
        counter[num]--;              // 令前缀和自减 1 ,得到下次放置 num 的索引
    }
    // 使用结果数组 res 覆盖原数组 nums
    nums = res;
}
counting_sort.java
/* 计数排序 */
// 完整实现,可排序对象,并且是稳定排序
void countingSort(int[] nums) {
    // 1. 统计数组最大元素 m
    int m = 0;
    for (int num : nums) {
        m = Math.max(m, num);
    }
    // 2. 统计各数字的出现次数
    // counter[num] 代表 num 的出现次数
    int[] counter = new int[m + 1];
    for (int num : nums) {
        counter[num]++;
    }
    // 3. 求 counter 的前缀和,将“出现次数”转换为“尾索引”
    // 即 counter[num]-1 是 num 在 res 中最后一次出现的索引
    for (int i = 0; i < m; i++) {
        counter[i + 1] += counter[i];
    }
    // 4. 倒序遍历 nums ,将各元素填入结果数组 res
    // 初始化数组 res 用于记录结果
    int n = nums.length;
    int[] res = new int[n];
    for (int i = n - 1; i >= 0; i--) {
        int num = nums[i];
        res[counter[num] - 1] = num; // 将 num 放置到对应索引处
        counter[num]--; // 令前缀和自减 1 ,得到下次放置 num 的索引
    }
    // 使用结果数组 res 覆盖原数组 nums
    for (int i = 0; i < n; i++) {
        nums[i] = res[i];
    }
}
counting_sort.cs
/* 计数排序 */
// 完整实现,可排序对象,并且是稳定排序
void CountingSort(int[] nums) {
    // 1. 统计数组最大元素 m
    int m = 0;
    foreach (int num in nums) {
        m = Math.Max(m, num);
    }
    // 2. 统计各数字的出现次数
    // counter[num] 代表 num 的出现次数
    int[] counter = new int[m + 1];
    foreach (int num in nums) {
        counter[num]++;
    }
    // 3. 求 counter 的前缀和,将“出现次数”转换为“尾索引”
    // 即 counter[num]-1 是 num 在 res 中最后一次出现的索引
    for (int i = 0; i < m; i++) {
        counter[i + 1] += counter[i];
    }
    // 4. 倒序遍历 nums ,将各元素填入结果数组 res
    // 初始化数组 res 用于记录结果
    int n = nums.Length;
    int[] res = new int[n];
    for (int i = n - 1; i >= 0; i--) {
        int num = nums[i];
        res[counter[num] - 1] = num; // 将 num 放置到对应索引处
        counter[num]--; // 令前缀和自减 1 ,得到下次放置 num 的索引
    }
    // 使用结果数组 res 覆盖原数组 nums
    for (int i = 0; i < n; i++) {
        nums[i] = res[i];
    }
}
counting_sort.go
/* 计数排序 */
// 完整实现,可排序对象,并且是稳定排序
func countingSort(nums []int) {
    // 1. 统计数组最大元素 m
    m := 0
    for _, num := range nums {
        if num > m {
            m = num
        }
    }
    // 2. 统计各数字的出现次数
    // counter[num] 代表 num 的出现次数
    counter := make([]int, m+1)
    for _, num := range nums {
        counter[num]++
    }
    // 3. 求 counter 的前缀和,将“出现次数”转换为“尾索引”
    // 即 counter[num]-1 是 num 在 res 中最后一次出现的索引
    for i := 0; i < m; i++ {
        counter[i+1] += counter[i]
    }
    // 4. 倒序遍历 nums ,将各元素填入结果数组 res
    // 初始化数组 res 用于记录结果
    n := len(nums)
    res := make([]int, n)
    for i := n - 1; i >= 0; i-- {
        num := nums[i]
        // 将 num 放置到对应索引处
        res[counter[num]-1] = num
        // 令前缀和自减 1 ,得到下次放置 num 的索引
        counter[num]--
    }
    // 使用结果数组 res 覆盖原数组 nums
    copy(nums, res)
}
counting_sort.swift
/* 计数排序 */
// 完整实现,可排序对象,并且是稳定排序
func countingSort(nums: inout [Int]) {
    // 1. 统计数组最大元素 m
    let m = nums.max()!
    // 2. 统计各数字的出现次数
    // counter[num] 代表 num 的出现次数
    var counter = Array(repeating: 0, count: m + 1)
    for num in nums {
        counter[num] += 1
    }
    // 3. 求 counter 的前缀和,将“出现次数”转换为“尾索引”
    // 即 counter[num]-1 是 num 在 res 中最后一次出现的索引
    for i in 0 ..< m {
        counter[i + 1] += counter[i]
    }
    // 4. 倒序遍历 nums ,将各元素填入结果数组 res
    // 初始化数组 res 用于记录结果
    var res = Array(repeating: 0, count: nums.count)
    for i in nums.indices.reversed() {
        let num = nums[i]
        res[counter[num] - 1] = num // 将 num 放置到对应索引处
        counter[num] -= 1 // 令前缀和自减 1 ,得到下次放置 num 的索引
    }
    // 使用结果数组 res 覆盖原数组 nums
    for i in nums.indices {
        nums[i] = res[i]
    }
}
counting_sort.js
/* 计数排序 */
// 完整实现,可排序对象,并且是稳定排序
function countingSort(nums) {
    // 1. 统计数组最大元素 m
    let m = Math.max(...nums);
    // 2. 统计各数字的出现次数
    // counter[num] 代表 num 的出现次数
    const counter = new Array(m + 1).fill(0);
    for (const num of nums) {
        counter[num]++;
    }
    // 3. 求 counter 的前缀和,将“出现次数”转换为“尾索引”
    // 即 counter[num]-1 是 num 在 res 中最后一次出现的索引
    for (let i = 0; i < m; i++) {
        counter[i + 1] += counter[i];
    }
    // 4. 倒序遍历 nums ,将各元素填入结果数组 res
    // 初始化数组 res 用于记录结果
    const n = nums.length;
    const res = new Array(n);
    for (let i = n - 1; i >= 0; i--) {
        const num = nums[i];
        res[counter[num] - 1] = num; // 将 num 放置到对应索引处
        counter[num]--; // 令前缀和自减 1 ,得到下次放置 num 的索引
    }
    // 使用结果数组 res 覆盖原数组 nums
    for (let i = 0; i < n; i++) {
        nums[i] = res[i];
    }
}
counting_sort.ts
/* 计数排序 */
// 完整实现,可排序对象,并且是稳定排序
function countingSort(nums: number[]): void {
    // 1. 统计数组最大元素 m
    let m: number = Math.max(...nums);
    // 2. 统计各数字的出现次数
    // counter[num] 代表 num 的出现次数
    const counter: number[] = new Array<number>(m + 1).fill(0);
    for (const num of nums) {
        counter[num]++;
    }
    // 3. 求 counter 的前缀和,将“出现次数”转换为“尾索引”
    // 即 counter[num]-1 是 num 在 res 中最后一次出现的索引
    for (let i = 0; i < m; i++) {
        counter[i + 1] += counter[i];
    }
    // 4. 倒序遍历 nums ,将各元素填入结果数组 res
    // 初始化数组 res 用于记录结果
    const n = nums.length;
    const res: number[] = new Array<number>(n);
    for (let i = n - 1; i >= 0; i--) {
        const num = nums[i];
        res[counter[num] - 1] = num; // 将 num 放置到对应索引处
        counter[num]--; // 令前缀和自减 1 ,得到下次放置 num 的索引
    }
    // 使用结果数组 res 覆盖原数组 nums
    for (let i = 0; i < n; i++) {
        nums[i] = res[i];
    }
}
counting_sort.dart
/* 计数排序 */
// 完整实现,可排序对象,并且是稳定排序
void countingSort(List<int> nums) {
  // 1. 统计数组最大元素 m
  int m = 0;
  for (int _num in nums) {
    m = max(m, _num);
  }
  // 2. 统计各数字的出现次数
  // counter[_num] 代表 _num 的出现次数
  List<int> counter = List.filled(m + 1, 0);
  for (int _num in nums) {
    counter[_num]++;
  }
  // 3. 求 counter 的前缀和,将“出现次数”转换为“尾索引”
  // 即 counter[_num]-1 是 _num 在 res 中最后一次出现的索引
  for (int i = 0; i < m; i++) {
    counter[i + 1] += counter[i];
  }
  // 4. 倒序遍历 nums ,将各元素填入结果数组 res
  // 初始化数组 res 用于记录结果
  int n = nums.length;
  List<int> res = List.filled(n, 0);
  for (int i = n - 1; i >= 0; i--) {
    int _num = nums[i];
    res[counter[_num] - 1] = _num; // 将 _num 放置到对应索引处
    counter[_num]--; // 令前缀和自减 1 ,得到下次放置 _num 的索引
  }
  // 使用结果数组 res 覆盖原数组 nums
  nums.setAll(0, res);
}
counting_sort.rs
/* 计数排序 */
// 完整实现,可排序对象,并且是稳定排序
fn counting_sort(nums: &mut [i32]) {
    // 1. 统计数组最大元素 m
    let m = *nums.iter().max().unwrap() as usize;
    // 2. 统计各数字的出现次数
    // counter[num] 代表 num 的出现次数
    let mut counter = vec![0; m + 1];
    for &num in nums.iter() {
        counter[num as usize] += 1;
    }
    // 3. 求 counter 的前缀和,将“出现次数”转换为“尾索引”
    // 即 counter[num]-1 是 num 在 res 中最后一次出现的索引
    for i in 0..m {
        counter[i + 1] += counter[i];
    }
    // 4. 倒序遍历 nums ,将各元素填入结果数组 res
    // 初始化数组 res 用于记录结果
    let n = nums.len();
    let mut res = vec![0; n];
    for i in (0..n).rev() {
        let num = nums[i];
        res[counter[num as usize] - 1] = num; // 将 num 放置到对应索引处
        counter[num as usize] -= 1; // 令前缀和自减 1 ,得到下次放置 num 的索引
    }
    // 使用结果数组 res 覆盖原数组 nums
    nums.copy_from_slice(&res)
}
counting_sort.c
/* 计数排序 */
// 完整实现,可排序对象,并且是稳定排序
void countingSort(int nums[], int size) {
    // 1. 统计数组最大元素 m
    int m = 0;
    for (int i = 0; i < size; i++) {
        if (nums[i] > m) {
            m = nums[i];
        }
    }
    // 2. 统计各数字的出现次数
    // counter[num] 代表 num 的出现次数
    int *counter = calloc(m, sizeof(int));
    for (int i = 0; i < size; i++) {
        counter[nums[i]]++;
    }
    // 3. 求 counter 的前缀和,将“出现次数”转换为“尾索引”
    // 即 counter[num]-1 是 num 在 res 中最后一次出现的索引
    for (int i = 0; i < m; i++) {
        counter[i + 1] += counter[i];
    }
    // 4. 倒序遍历 nums ,将各元素填入结果数组 res
    // 初始化数组 res 用于记录结果
    int *res = malloc(sizeof(int) * size);
    for (int i = size - 1; i >= 0; i--) {
        int num = nums[i];
        res[counter[num] - 1] = num; // 将 num 放置到对应索引处
        counter[num]--;              // 令前缀和自减 1 ,得到下次放置 num 的索引
    }
    // 使用结果数组 res 覆盖原数组 nums
    memcpy(nums, res, size * sizeof(int));
    // 5. 释放内存
    free(res);
    free(counter);
}
counting_sort.kt
/* 计数排序 */
// 完整实现,可排序对象,并且是稳定排序
fun countingSort(nums: IntArray) {
    // 1. 统计数组最大元素 m
    var m = 0
    for (num in nums) {
        m = max(m, num)
    }
    // 2. 统计各数字的出现次数
    // counter[num] 代表 num 的出现次数
    val counter = IntArray(m + 1)
    for (num in nums) {
        counter[num]++
    }
    // 3. 求 counter 的前缀和,将“出现次数”转换为“尾索引”
    // 即 counter[num]-1 是 num 在 res 中最后一次出现的索引
    for (i in 0..<m) {
        counter[i + 1] += counter[i]
    }
    // 4. 倒序遍历 nums ,将各元素填入结果数组 res
    // 初始化数组 res 用于记录结果
    val n = nums.size
    val res = IntArray(n)
    for (i in n - 1 downTo 0) {
        val num = nums[i]
        res[counter[num] - 1] = num // 将 num 放置到对应索引处
        counter[num]-- // 令前缀和自减 1 ,得到下次放置 num 的索引
    }
    // 使用结果数组 res 覆盖原数组 nums
    for (i in 0..<n) {
        nums[i] = res[i]
    }
}
counting_sort.rb
### 计数排序 ###
def counting_sort(nums)
  # 完整实现,可排序对象,并且是稳定排序
  # 1. 统计数组最大元素 m
  m = nums.max
  # 2. 统计各数字的出现次数
  # counter[num] 代表 num 的出现次数
  counter = Array.new(m + 1, 0)
  nums.each { |num| counter[num] += 1 }
  # 3. 求 counter 的前缀和,将“出现次数”转换为“尾索引”
  # 即 counter[num]-1 是 num 在 res 中最后一次出现的索引
  (0...m).each { |i| counter[i + 1] += counter[i] }
  # 4. 倒序遍历 nums, 将各元素填入结果数组 res
  # 初始化数组 res 用于记录结果
  n = nums.length
  res = Array.new(n, 0)
  (n - 1).downto(0).each do |i|
    num = nums[i]
    res[counter[num] - 1] = num # 将 num 放置到对应索引处
    counter[num] -= 1 # 令前缀和自减 1 ,得到下次放置 num 的索引
  end
  # 使用结果数组 res 覆盖原数组 nums
  (0...n).each { |i| nums[i] = res[i] }
end
可视化运行

11.9.3   算法特性

  • 时间复杂度为 \(O(n + m)\)、非自适应排序 :涉及遍历 nums 和遍历 counter ,都使用线性时间。一般情况下 \(n \gg m\) ,时间复杂度趋于 \(O(n)\) 。
  • 空间复杂度为 \(O(n + m)\)、非原地排序:借助了长度分别为 \(n\) 和 \(m\) 的数组 res 和 counter 。
  • 稳定排序:由于向 res 中填充元素的顺序是“从右向左”的,因此倒序遍历 nums 可以避免改变相等元素之间的相对位置,从而实现稳定排序。实际上,正序遍历 nums 也可以得到正确的排序结果,但结果是非稳定的。

11.9.4   局限性

看到这里,你也许会觉得计数排序非常巧妙,仅通过统计数量就可以实现高效的排序。然而,使用计数排序的前置条件相对较为严格。

计数排序只适用于非负整数。若想将其用于其他类型的数据,需要确保这些数据可以转换为非负整数,并且在转换过程中不能改变各个元素之间的相对大小关系。例如,对于包含负数的整数数组,可以先给所有数字加上一个常数,将全部数字转化为正数,排序完成后再转换回去。

计数排序适用于数据量大但数据范围较小的情况。比如,在上述示例中 \(m\) 不能太大,否则会占用过多空间。而当 \(n \ll m\) 时,计数排序使用 \(O(m)\) 时间,可能比 \(O(n \log n)\) 的排序算法还要慢。

欢迎在评论区留下你的见解、问题或建议