[演算法] 學習筆記 — 13. 基數排序法 Radix Sort

11 min readNov 30, 2022

跳脫比較的框架

目前為止，我們所有遇到的演算法，都屬於「比較演算法」（Comparison Sorts）。意思是，不論是氣泡排序（Bubble Sort）、或是進階的快速排序（Quick Sort），都需要在排序時針對某種基準做比較，我們基於比較，把一些東西移到左邊、一些移到右邊。

在前面這些演算法中，時間複雜度有些是 O(n²)，例如 Bubble Sort、Selection Sort、Insertion Sort；進階的 Merge Sort 及 Quick Sort 則是 O(nlogn)。從 O(n²）→ O(nlogn) 是很大的進步！但是，我們還能更好嗎？（貪心是進步的動力呀～ 😆

答案是，可以！不過這一次，我們不再透過比較去排序。（哇，我現在學的是人生的道理嗎？）

在比較演算法中，我們能期望最好的時間複雜度，就是 O(nlogn)，如果想瞭解為什麼，可以參考這篇維基。因此，要得到比 O(nlogn) 的時間複雜度更好的演算法，我們不能透過比較來排序，必須跳脫比較的思維，但很可惜，這樣的演算法有應用場景的限制。

有些演算法利用了資料的特定性質來做排序，得到了更好的時間複雜度。例如有一些演算法屬於「整數演算法」（Integer Algorithm），但如同它的名字，它只能用在整數列上。而這篇要認識的就是整數演算法中的基數演算法（Radix Sort）。

核心概念

基數演算法只適用在數字上，通常會被用在二進制中，或者如果將字串或圖片轉為二進制，也能使用 Radix Sort，重要的是當我們在排序的時候，資料的型別必須是數字。

基數演算法的核心概念很有趣，它利用的觀念是「數字的大小必定跟數字的長短（位數）有關」（好奇怪的一句話😅）。也就是說，一個由 4 個數字組成的數（當然前面不能是 0 ，例如最小的 1000）必定大於一個由 2 個數字組成的數（例如最大的 99）。我們不在乎它們實際是由什麼數字組成的，我們不將它們的組成數字拿來做比較，我們只需要知道：「更長的數字必定大於較短的數字」。

作法

所以實際上我們怎麼做呢？在做基數排序的時候，我們先創建十個籃子分別代表 0 ～ 9。

source: JavaScript Algorithms and Data Structures Masterclass，以下相同

接著，我們遍歷所有的元素，依據元素最右邊的數字（例如 1234 的 1、382 的 2 ）將它們放進對應的籃子裡。

902 在 2 的籃子裡，因為它第一個數字是 2，86、4386、3556、1556 都在 6 的籃子裡，因為它們第一個數字都是 6。

接著，我們維持籃子的順序將這些數字放回陣列中：

接著，我們重複一樣的步驟，只是這次我們看下一個數字，也就是右邊數來第二位數。我們會像這樣把它們放進對應的籃子：

408、7、4、902 的十位數都是 0，因此放在 0 的籃子裡，86、4386 的十位數都是 8，因此它們在 8 的籃子裡⋯⋯依此類推。

然後，我們再按籃子的順序將數字放進陣列中：

在這每一次的步驟中，陣列都會越來越接近最後的模樣。

接著，我們根據數字的百位數放進對應的籃子中：

再依序組回陣列：

再根據千位數放進籃子：

再組回陣列：

驚訝的發現，我們組好的陣列不知不覺中已經完成排序了！

這樣的「丟進籃子 → 組回陣列」的循環必須執行幾次，是根據我們排序的資料中「最長的數字有幾個位數」來決定的。也就是說最長的數字是 99，我們只需要重複 2 次，最長的數字是 12345，我們則需要重複 5 次。再這邊的例子中，最長的數字是 4 個位數，因此我們需要重複 4 次。

Radix Sort Helper Method

為了能完成 Radix Sort 的函式，我們必須先寫一些給它使用的輔助函式。

第一個輔助函式是 getDigit(num, place)，這個函式回傳的是「在某個特定位置的數字」，例如：

getDigit(12345, 0)  // 得到 5
getDigit(12345, 1)  // 得到 4
getDigit(12345, 2)  // 得到 3
getDigit(12345, 3)  // 得到 2
getDigit(12345, 4)  // 得到 1

然後，getDigit 的函式會是這樣（Colt 說他是從 StackOverflow 拿到的，所以我們不自己寫也不用良心不安對吧😆）

function getDigit(num, i) {
    return Math.floor(Math.abs(num) / Math.pow(10, i)) % 10
}

Math.abs 是為了得到 num 的絕對值，Math.pow 則是取得 10 的 n 次方。這段函式做的事情是這樣：

取得輸入值的絕對值，例如 -7238 得到 7238；
將絕對值除以 10 的 n 次方，n 取決於今天我們想拿的是第幾個位數。例如個位數就是 10 的 0 次方，百位數是 10 的 2 次方；
將絕對值除以 10 的 n 次方後，Math.floor 捨棄掉小數；
接著我們要的是最後一個數字也就是除以 10 取餘數（% 10）。

第二個我們會用到的輔助函式則是 digitCount，digitCount 告訴我們在所有要排序的數字中，最長的一筆資料有幾個數字（決定我們要重複丟進籃子 → 組回陣列這個步驟幾次）。

digitCount(1)     // 回傳 1
digitCount(25)    // 回傳 2
digitCount(391)   // 回傳 3

digitCount 的函式本人是這樣：

function digitCount(num) {
    if (num === 0) return 1
    return Math.floor(Math.log10(Math.abs(num))) + 1
}

將輸入的 num 取絕對值；
我們需要知道 10 的幾次方會得到 Math.abs(num)，因此我們以 Math.abs(num) 作為對數，做以 10 為底的 log10 的指對數計算（數學好難講🥹 複習高中數學啊⋯⋯；
這樣指對數計算出來的數字通常不會是整數，因此使用 Math.floor 無條件捨去；

Math.log10(423)              // 2.6263403673750423
Math.floor(Math.log10(423))  // 2

Math.log10(59)               // 1.7708520116421442
Math.floor(Math.log10(59))   // 1

最後，因為我們需要根據長度去做迭代，因此我們將得到的結果加一：

Math.floor(Math.log10(423))       // 2
Math.floor(Math.log10(423)) + 1   // 3

Math.floor(Math.log10(59))        // 1
Math.floor(Math.log10(59))  + 1   // 2

唯一的 edge case 是當 num 是 0 的時候，如果我們做 Math.log10(0) 我們會得到 -Infinity，負數的無窮大，因此我們以條件句讓它回傳 1。

最後一個輔助函式，叫做 mostDigits，mostDigits 回傳結果表示在輸入的陣列中，最長的數字有幾個位數。

mostDigits([1234, 56, 7])        // 4
mostDigits([1, 1, 11111, 1])     // 5
mostDigits([12, 34, 56, 78])     // 2

mostDigits 會利用到上面的 digitCount，函式本人是這樣：

function mostDigits(nums) {
    let maxDigits = 0
    for(let i = 0; i < nums.length; i++) {
        maxDigits = Math.max(maxDigits, digitCount(nums[i]))
    }
    return maxDigits
}

我覺得這個是最好理解的，縮短篇幅不細拆解了🤣

Radix Sort 虛擬碼

很多的 helper method 是 Radix Sort 比較複雜的部分，頭過身就過！！後面就比較簡單了（Colt 說的🤣），先來寫 pseudo code 的部分：

定義一個函式，接受一組數字陣列作為 input；
找出陣列中最長的數字有幾個位數（mostDigits）；
根據 mostDigits 回傳次數做迭代，重複上面「丟進籃子 → 組回陣列」的步驟：每一次迭代我們都會創建 0 ~ 9 十個籃子，然後根據對應的位數把元素放進籃子裡；

根據籃子由小到大，將籃子裡的數字依序放回陣列中；
最後得到的陣列就是我們期望的完成排序的結果！

Radix Sort

如果了解步驟，Radix Sort 實際的模樣並不複雜，我們只要把前面的輔助函式組合起來，再加上一點點過場就行了：

function getDigit(num, i) {
    return Math.floor(Math.abs(num) / Math.pow(10, i)) % 10
}

function digitCount(num) {
    if (num === 0) return 1
    return Math.floor(Math.log10(Math.abs(num))) + 1
}

function mostDigits(nums) {
    let maxDigits = 0
    for(let i = 0; i < nums.length; i++) {
        maxDigits = Math.max(maxDigits, digitCount(num[i]))
    }
    return maxDigits
}

function radixSort(nums) {

    // 找出陣列中最長的位數有幾個數字，來知道我們需要做幾次迭代
    let maxDigitsCount = mostDigits(nums)

    for (let k = 0; k < maxDigitCount; k++) {
        let digitBuckets = Array.from({length: 10}, () => [])

        for (let i = 0; i < nums.length; i++) {
            // 找出第 k 個位置的數字，並把它放進對應的籃子裡
            let bucketIdx = getDigit(nums[i], k)
            digitBuckets[bucketIdx].push(nums[i])
        }
        // 合併所有 array
        nums = [].concat(...digitBuckets)
    }
    return nums
}