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)。
