基数排序

Harshit Jindal 2023年1月30日 2021年2月7日
  1. 基数排序算法
  2. 基数排序示例
  3. 基数排序算法的实现
  4. 基数排序算法的复杂度
基数排序
注意
如果你不知道什么是计数排序,那么请先去看计数排序一文。

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

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

相关文章 - Sort Algorithm