TUTORIAL · Algorithm
计数排序
本教程介绍了计数排序算法。
本页内容
计数排序是一种非比较排序算法。它通过计算每个唯一元素的出现次数对数组进行排序。它对唯一元素的计数进行部分哈希处理，然后执行计算以找到最终排序数组中每个元素的索引。它是一个相当快的算法，但不适合大型数据集。它作为基数排序中的一个子程序使用。
计数排序算法
假设我们有一个无序数组 A[]，包含 n 个元素。
-
求出数组内的最大元素
max和最小元素min。 -
初始化一个长度为
max-min+1的数组count，所有元素都设置为0。 -
初始化一个数组
output，大小与输入数组A相同。 -
将
count数组中所有元素的数量减去min，并将其差值作为索引。 -
累计
count数组内元素的总和。现在，count数组拥有排序数组中每个元素的位置。 -
从尾部开始，从
A中抽取元素，并进行以下操作。 -
计算元素索引为
count[A[i]-min]-1，并将A[i]存储在output中。 -
将
count[A[i]-min]减少1。 -
将
output元素存储回原数组A中。
计数排序实例
假设我们有数组。(6, 3, 2, 7, 4, 5, 4, 2). 我们将使用计数排序算法对其进行排序。
maxm=7minm=2range=6count和output初始化为 0。
| 索引 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 值 | 0 | 0 | 0 | 0 | 0 | 0 |
count数组在计算了所有元素的数量后。
| 索引 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 值 | 2 | 1 | 2 | 1 | 1 | 1 |
- 累积元素之和后的
count数组。
| 索引 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 值 | 2 | 3 | 5 | 6 | 7 | 8 |
- 第一次迭代：
A[7]=2。
count |
1 3 5 6 7 8 |
output |
0 2 0 0 0 0 0 0 |
- 第二次迭代：
A[6]=4。
count |
1 3 4 6 7 8 |
output |
0 2 0 0 4 0 0 0 |
- 第三次迭代：
A[5]=5。
count |
1 3 4 5 7 8 |
output |
0 2 0 0 4 5 0 0 |
- 第四次迭代：
A[4]=4。
count |
1 3 3 5 7 8 |
output |
0 2 0 4 4 5 0 0 |
- 第五次迭代：
A[3]=7。
count |
1 3 3 5 7 7 |
output |
0 2 0 4 4 5 0 7 |
- 第六次迭代：
A[2]=2。
count |
0 3 3 5 7 7 |
output |
2 2 0 4 4 5 0 7 |
- 第七次迭代：
A[1]=3。
count |
0 2 3 5 7 7 |
output |
2 2 3 4 4 5 0 7 |
- 第八次迭代：
A[0]=6。
count |
0 2 3 5 6 7 |
output |
2 2 3 4 4 5 6 7 |
最后，我们把 output 数组存储在 A 里面，得到排序数组-2，2，3，4，4，5，6，7。
计数排序算法的实现
#include <iostream>
using namespace std;
const int N = 10;
int maxm(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
int minm(int arr[], int n) {
int min = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] < min) {
min = arr[i];
}
}
return min;
}
void countingSort(int arr[], int n) {
int min = minm(arr, n);
int max = maxm(arr, n);
int range = max - min + 1;
int count[range] = {};
int output[n];
for (int i = 0; i < n; i++) count[arr[i] - min]++;
for (int i = 1; i < range; i++) count[i] += count[i - 1];
for (int i = n - 1; i >= 0; i--) {
output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
for (int i = 0; i < n; i++) arr[i] = output[i];
}
int main() {
int n = 7;
int arr[7] = {3, 5, 1, 1, 4, 2, 1};
cout << "Input arr: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
countingSort(arr, n); // Sort elements in ascending order
cout << "Output arr: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
}
此实现也适用于负数。
计数排序算法的复杂度
时间复杂度
- 平均情况
计数排序对所有 n 项进行两次迭代，对计数数组进行一次迭代。因此，它的时间复杂度为 O(n+b)，其中 b 是输入的范围。由于 b 通常较小，所以计数排序的时间复杂度可以说是 [Big Theta]：O(n)。
- 最坏情况
最坏情况下的时间复杂度为 [Big O]：O(n)。
- 最佳情况
最佳情况下的时间复杂度是 [Big Omega]：O(n)。它与最坏情况下的时间复杂度相同。
空间复杂度
计数排序算法的空间复杂度为 O(n+b)，其中 b 是输入的范围。它来自于 count&output 数组。有时 b 可以比 n 大，但如果 b 小，时间复杂度可以说是 O(n)。
