【算法】排序算法之基數排序

在前幾回我們已經對 、 、 、 、 、 、 、 、 做了說明分析。本回,將對基數排序

進行相關說明分析。


一、排序算法系列目錄說明

  • 冒泡排序(Bubble Sort)
  • 插入排序(Insertion Sort)
  • 希爾排序(Shell Sort)
  • 選擇排序(Selection Sort)
  • 快速排序(Quick Sort)
  • 歸併排序(Merge Sort)
  • 堆排序(Heap Sort)
  • 計數排序(Counting Sort)
  • 桶排序(Bucket Sort)
  • 基數排序(Radix Sort)

  • 二、基數排序(RadixSort)

    基數排序(Radix sort)是一種非比較型整數排序算法。

    1. 基本思想

    原理是將整數按位數切割成不同的數字,然後按每個位數分別比較。基數排序的方式可以採用LSD(Least significant digital)或MSD(Most significant digital),LSD的排序方式由鍵值的最右邊開始,而MSD則相反,由鍵值的最左邊開始。

    MSD:先從高位開始進行排序,在每個關鍵字上,可採用計數排序

    LSD:先從低位開始進行排序,在每個關鍵字上,可採用桶排序

    2. 實現邏輯

    ① 將所有待比較數值(正整數)統一為同樣的數位長度,數位較短的數前面補零。

    ② 從最低位開始,依次進行一次排序。

    ③ 這樣從最低位排序一直到最高位排序完成以後, 數列就變成一個有序序列。

    3. 動圖演示

    【算法】排序算法之基數排序

    基數排序演示

    分步圖示說明:設有數組 array = {53, 3, 542, 748, 14, 214, 154, 63, 616},對其進行基數排序:

    【算法】排序算法之基數排序

    在上圖中,首先將所有待比較數字統一為統一位數長度,接著從最低位開始,依次進行排序。

    按照個位數進行排序。

    按照十位數進行排序。

    按照百位數進行排序。

    排序後,數列就變成了一個有序序列。

    4. 複雜度分析

    時間複雜度:O(k*N)

    空間複雜度:O(k + N)

    穩定性:穩定

    設待排序的數組R[1…n],數組中最大的數是d位數,基數為r(如基數為10,即10進制,最大有10種可能,即最多需要10個桶來映射數組元素)。

    處理一位數,需要將數組元素映射到r個桶中,映射完成後還需要收集,相當於遍歷數組一遍,最多元素數為n,則時間複雜度為O(n+r)。所以,總的時間複雜度為O(d*(n+r))。

    基數排序過程中,用到一個計數器數組,長度為r,還用到一個rn的二位數組來做為桶,所以空間複雜度為O(rn)。

    基數排序基於分別排序,分別收集,所以是穩定的。

    5. 代碼實現

    <code>int maxbit(int data[], int n) //輔助函數,求數據的最大位數
    {
    int maxData = data[0];\t\t///< 最大數
    /// 先求出最大數,再求其位數,這樣有原先依次每個數判斷其位數,稍微優化點。
    for (int i = 1; i < n; ++i)
    {
    if (maxData < data[i])
    maxData = data[i];
    }
    int d = 1;
    int p = 10;
    while (maxData >= p)
    {
    //p *= 10; // Maybe overflow
    maxData /= 10;
    ++d;
    }
    return d;
    /* int d = 1; //保存最大的位數
    int p = 10;
    for(int i = 0; i < n; ++i)
    {
    while(data[i] >= p)
    {
    p *= 10;
    ++d;
    }
    }
    return d;*/
    }
    void radixsort(int data[], int n) //基數排序
    {
    int d = maxbit(data, n);
    int *tmp = new int[n];
    int *count = new int[10]; //計數器
    int i, j, k;

    int radix = 1;
    for(i = 1; i <= d; i++) //進行d次排序
    {
    for(j = 0; j < 10; j++)
    count[j] = 0; //每次分配前清空計數器
    for(j = 0; j < n; j++)
    {
    k = (data[j] / radix) % 10; //統計每個桶中的記錄數
    count[k]++;
    }
    for(j = 1; j < 10; j++)
    count[j] = count[j - 1] + count[j]; //將tmp中的位置依次分配給每個桶
    for(j = n - 1; j >= 0; j--) //將所有桶中記錄依次收集到tmp中
    {
    k = (data[j] / radix) % 10;
    tmp[count[k] - 1] = data[j];
    count[k]--;
    }
    for(j = 0; j < n; j++) //將臨時數組的內容複製到data中
    data[j] = tmp[j];
    radix = radix * 10;
    }
    delete []tmp;
    delete []count;
    }/<code>

    三、總結

    基數排序與計數排序、桶排序這三種排序算法都利用了桶的概念,但對桶的使用方法上有明顯差異:

    基數排序:根據鍵值的每位數字來分配桶;

    計數排序

    :每個桶只存儲單一鍵值;

    桶排序:每個桶存儲一定範圍的數值;

    基數排序不是直接根據元素整體的大小進行元素比較,而是將原始列表元素分成多個部分,對每一部分按一定的規則進行排序,進而形成最終的有序列表。


    PS: 更多精選內容資源分享,歡迎關注微信公眾號:『 developer1024 』


    分享到:


    相關文章: