11.9 计数排序¶
计数排序(counting sort)通过统计元素数量来实现排序,通常应用于整数数组。
11.9.1 简单实现¶
先来看一个简单的例子。给定一个长度为 \(n\) 的数组 nums ,其中的元素都是“非负整数”,计数排序的整体流程如图 11-16 所示。
- 遍历数组,找出其中的最大数字,记为 \(m\) ,然后创建一个长度为 \(m + 1\) 的辅助数组
counter。 - 借助
counter统计nums中各数字的出现次数,其中counter[num]对应数字num的出现次数。统计方法很简单,只需遍历nums(设当前数字为num),每轮将counter[num]增加 \(1\) 即可。 - 由于
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;下方三张表分别列出原始输入、数字频数与写回结果。
| 索引 | 值 |
|---|---|
| 0 | 1 |
| 1 | 0 |
| 2 | 1 |
| 3 | 2 |
| 4 | 0 |
| 5 | 4 |
| 6 | 0 |
| 7 | 2 |
| 8 | 2 |
| 9 | 4 |
| 数字 | 出现次数 |
|---|---|
| 0 | 3 |
| 1 | 2 |
| 2 | 3 |
| 3 | 0 |
| 4 | 2 |
| 索引 | 值 |
|---|---|
| 0 | 0 |
| 1 | 0 |
| 2 | 0 |
| 3 | 1 |
| 4 | 1 |
| 5 | 2 |
| 6 | 2 |
| 7 | 2 |
| 8 | 4 |
| 9 | 4 |
这种简单实现按频数重建整数序列,不保留相等数值各自的原输入身份;若需对携带附加属性的对象稳定排序,须进一步保留对象身份并安排写入位置。
代码如下所示:
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
/* 计数排序 */
// 简单实现,无法用于排序对象
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;
}
}
}
/* 计数排序 */
// 简单实现,无法用于排序对象
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;
}
}
}
/* 计数排序 */
// 简单实现,无法用于排序对象
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;
}
}
}
/* 计数排序 */
// 简单实现,无法用于排序对象
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++
}
}
}
/* 计数排序 */
// 简单实现,无法用于排序对象
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
}
}
}
/* 计数排序 */
// 简单实现,无法用于排序对象
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;
}
}
}
/* 计数排序 */
// 简单实现,无法用于排序对象
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;
}
}
}
/* 计数排序 */
// 简单实现,无法用于排序对象
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;
}
}
}
/* 计数排序 */
// 简单实现,无法用于排序对象
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;
}
}
}
/* 计数排序 */
// 简单实现,无法用于排序对象
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);
}
/* 计数排序 */
// 简单实现,无法用于排序对象
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++
}
}
}
### 计数排序 ###
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 个元素之和:
前缀和具有明确的意义,prefix[num] - 1 代表元素 num 在结果数组 res 中最后一次出现的索引。这个信息非常关键,因为它告诉我们各个元素应该出现在结果数组的哪个位置。接下来,我们倒序遍历原数组 nums 的每个元素 num ,在每轮迭代中执行以下两步。
- 将
num填入数组res的索引prefix[num] - 1处。 - 令前缀和
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。
统计频数
遍历原数组 nums,统计数字 0、1、2、3、4 各自出现的次数,生成长度为 5 的计数数组 counter = [3, 2, 3, 0, 2]。尚未求前缀和,也未写入结果。
计数排序第 1 步:nums 索引 nums 值 0 1 1 0 2 1 3 2 4 0 5 4 6 0 7 2 8 2 9 4 计数排序第 1 步:频数 counter 数字 num 出现次数 0 3 1 2 2 3 3 0 4 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 元素的原始索引 0 1 未写入 无 1 0 未写入 无 2 1 未写入 无 3 2 未写入 无 4 0 未写入 无 5 4 未写入 无 6 0 未写入 无 7 2 未写入 无 8 2 未写入 无 9 4 未写入 无 计数排序第 2 步:初始 prefix 数字 num prefix[num] 0 3 1 5 2 8 3 8 4 10 将末尾的 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 元素的原始索引 0 1 未写入 无 1 0 未写入 无 2 1 未写入 无 3 2 未写入 无 4 0 未写入 无 5 4 未写入 无 6 0 未写入 无 7 2 未写入 无 8 2 未写入 无 9 4 4 9 计数排序第 3 步:递减后的 prefix 数字 num prefix[num] 0 3 1 5 2 8 3 8 4 9 将原索引 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 元素的原始索引 0 1 未写入 无 1 0 未写入 无 2 1 未写入 无 3 2 未写入 无 4 0 未写入 无 5 4 未写入 无 6 0 未写入 无 7 2 2 8 8 2 未写入 无 9 4 4 9 计数排序第 4 步:递减后的 prefix 数字 num prefix[num] 0 3 1 5 2 7 3 8 4 9 将原索引 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 元素的原始索引 0 1 未写入 无 1 0 未写入 无 2 1 未写入 无 3 2 未写入 无 4 0 未写入 无 5 4 未写入 无 6 0 2 7 7 2 2 8 8 2 未写入 无 9 4 4 9 计数排序第 5 步:递减后的 prefix 数字 num prefix[num] 0 3 1 5 2 6 3 8 4 9 将原索引 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 元素的原始索引 0 1 未写入 无 1 0 未写入 无 2 1 0 6 3 2 未写入 无 4 0 未写入 无 5 4 未写入 无 6 0 2 7 7 2 2 8 8 2 未写入 无 9 4 4 9 计数排序第 6 步:递减后的 prefix 数字 num prefix[num] 0 2 1 5 2 6 3 8 4 9 完成其余六次写入
继续倒序处理原数组索引 5 至 0 的其余六个元素(依次为 4、0、2、1、0、1),分别填入 res 的索引 8、1、5、4、0、3。图中省略了这六步中间画面,直接跳到遍历结束状态:此时 res 已全部填满为有序序列,而上方原数组 nums 尚未被覆盖。
计数排序第 7 步:nums 与 res 索引 nums 值 res 值或写入状态 res 元素的原始索引 0 1 0 1 1 0 0 4 2 1 0 6 3 2 1 0 4 0 1 2 5 4 2 3 6 0 2 7 7 2 2 8 8 2 4 5 9 4 4 9 计数排序第 7 步:递减后的 prefix 数字 num prefix[num] 0 0 1 3 2 5 3 8 4 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 元素的原始索引 0 0 0 1 1 0 0 4 2 0 0 6 3 1 1 0 4 1 1 2 5 2 2 3 6 2 2 7 7 2 2 8 8 4 4 5 9 4 4 9 计数排序第 8 步:最终 prefix(同第 7 步) 数字 num prefix[num] 0 0 1 3 2 5 3 8 4 8
计数排序的实现代码如下所示:
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]
/* 计数排序 */
// 完整实现,可排序对象,并且是稳定排序
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;
}
/* 计数排序 */
// 完整实现,可排序对象,并且是稳定排序
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];
}
}
/* 计数排序 */
// 完整实现,可排序对象,并且是稳定排序
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];
}
}
/* 计数排序 */
// 完整实现,可排序对象,并且是稳定排序
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)
}
/* 计数排序 */
// 完整实现,可排序对象,并且是稳定排序
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]
}
}
/* 计数排序 */
// 完整实现,可排序对象,并且是稳定排序
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];
}
}
/* 计数排序 */
// 完整实现,可排序对象,并且是稳定排序
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];
}
}
/* 计数排序 */
// 完整实现,可排序对象,并且是稳定排序
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);
}
/* 计数排序 */
// 完整实现,可排序对象,并且是稳定排序
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)
}
/* 计数排序 */
// 完整实现,可排序对象,并且是稳定排序
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);
}
/* 计数排序 */
// 完整实现,可排序对象,并且是稳定排序
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]
}
}
### 计数排序 ###
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)\) 的排序算法还要慢。