基数排序
基数排序是一种非比较排序算法。这种算法通过根据基数 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