基數排序
基數排序是一種非比較排序演算法。這種演算法通過根據基數 radix（Radix/Base 是用來表示數字的唯一數字的數量）將元素插入到桶中，從而避免比較。例如，十進位制數有十個唯一的數字）。) 它根據各個元素的數字進行排序。它對從最小的有效數字到最有效數字的數字進行計數排序。它也被稱為桶排序或數字排序，在並行機器上非常有用。
基數排序演算法
假設我們有一個無序陣列 A[]，包含 n 個元素。
-
找到陣列中最大的元素
maxm。 -
使用穩定的排序演算法，對
maxm中的每個數字從最小意義開始排序。
基數排序示例
假設我們有陣列：(1851, 913, 1214, 312, 111, 23, 41, 9). 我們將使用基數排序演算法對其進行排序。
| 索引 | 輸入陣列 | 第一次迭代 | 第二次迭代 | 第三次迭代 | 第四次迭代 |
|---|---|---|---|---|---|
| 0 | 1851 | 1851 | 0009 | 0009 | 0009 |
| 1 | 0913 | 0111 | 0111 | 0023 | 0023 |
| 2 | 1214 | 0041 | 0312 | 0041 | 0041 |
| 3 | 0312 | 0312 | 0913 | 0111 | 0111 |
| 4 | 0111 | 0913 | 1214 | 1214 | 0312 |
| 5 | 0023 | 0023 | 0023 | 0312 | 0913 |
| 6 | 0041 | 1214 | 0041 | 1851 | 1214 |
| 7 | 0009 | 0009 | 1851 | 0913 | 1851 |
在第一次迭代中，我們按照單位位進行排序，然後向十位、百位、千位移動，得到最終的排序陣列為 9，23，41，111，312，913，1214，1851。
基數排序演算法的實現
#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;
}
void countingSort(int arr[], int n, int place) {
int output[n];
int count[N];
for (int i = 0; i < N; ++i) count[i] = 0;
for (int i = 0; i < n; i++) count[(arr[i] / place) % 10]++;
for (int i = 1; i < N; i++) count[i] += count[i - 1];
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / place) % 10] - 1] = arr[i];
count[(arr[i] / place) % 10]--;
}
for (int i = 0; i < n; i++) arr[i] = output[i];
}
void radixsort(int arr[], int n) {
int max = maxm(arr, n);
for (int place = 1; max / place > 0; place *= 10) countingSort(arr, n, place);
}
int main() {
int n = 5;
int arr[5] = {1851, 913, 1214, 312, 111};
cout << "Input arr: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
radixsort(arr, n); // Sort elements in ascending order
cout << "Output arr: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
}
基數排序演算法的複雜度
時間複雜度
- 平均情況
基數排序的時間複雜度為 O(n+b)，其中 b 是輸入的範圍。如果最大元素 maxm 中有 d 位，那麼基數排序的時間複雜度就變成 O(d*(n+b))。由於 d 和 b 通常較小，所以時間複雜度為 [Big Theta]：O(n)。
- 最壞情況
最壞情況下的時間複雜度為 [Big O]：O(n)。
- 最佳情況
最佳情況下的時間複雜度是 [Big Omega]：O(n)。它與最壞情況下的時間複雜度相同。
空間複雜度
奇數排序演算法的空間複雜度為 O(n+b)，其中 b 是輸入的範圍。它來自於基數排序中的 count&output 陣列。有時 b 可以大於 n，使得複雜度為非線性。
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedIn