基數排序

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