基數排序
基數排序是一種非比較排序演算法。這種演算法通過根據基數 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