计数排序

【注】参考自教材「算法导论」。

1. 简介

计数排序属于非比较排序算法类,故其时间复杂度不受比较排序算法时间复杂度下界的限制,可以达到 O(n+k)O(n+k) 。其中,kk 为待排序序列的排序关键字的最大范围。
计数排序是稳定的非原址的

2. 思想

计数排序假设 nn 个输入元素中的每一个的排序关键字都是在 0 到 kk 区间(左闭右开)内的一个整数。对每一个输入元素 xx ,确定小于 xx 的元素个数,然后利用元素个数直接将序列按顺序排好放到输出序列中。

3. 实现

3.1 伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
CountingSort(A, Key, k) {
// 定义新数组 B & C
define B[0..A.length]
define C[0..k]
// 初始化数组 C
for i = 0 to k
C[i] = 0
// 统计每个关键字的元素数量
for j = 1 to A.length
C[Key[j]] = C[Key[j]] + 1
// 统计关键字小于等于 i 的元素数量
for i = 1 to k
C[i] = C[i] + C[i-1]
for j = A.length downto 1
B[C[Key[j]]] = A[j]
C[Key[j]] = C[Key[j]] - 1
// 将已排好序的 B 数组拷贝给 A 数组
A = B
}

3.2 模板

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
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;

#ifndef _COUNTING_
#define _COUNTING_
#define ll int
#define MAXN 100005

// 计数排序
template < typename T >
struct Counting {

ll C[MAXN];
T B[MAXN];
Counting() {}
// 计数排序(关键字的值属于区间 [0,n))
//(关键字数组不会改变,待排序数组变为有序)
void countingSort(T *bA, T *eA, ll *bK, ll *eK, ll n) {
ll len_A = eA - bA;
ll len_K = eK - bK;
T *A = bA;
ll *K = bK;
// 判断关键字数组大小与元素数组大小是否吻合
assert(len_A == len_K);
// 初始化计数数组
for(ll i = 0; i < n; ++i) {
C[i] = 0;
}
// 统计关键字次数
for(ll i = 0; i < len_K; ++i) {
C[K[i]]++;
}
// 计算 <= i 的关键字次数
for(ll i = 1; i < n; ++i) {
C[i] = C[i] + C[i-1];
}
// 初始化排序数组
for(ll i = len_A-1; ~i; --i) {
B[C[K[i]]-1] = A[i];
C[K[i]]--;
}
// 将排好序的数组赋值给原数组
memcpy(A, B, sizeof(T)*len_A);
}
};
#endif

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!