シープの雑談メモ帳

Appearance

基數排序法 Radix Sort ​

本文同步發布於 2023 iThome 鐵人賽：那些前端不用會，但是可以會的資料結構與演算法 系列文中。

基數排序法（Radix Sort）是一種非比較性質的整數排序演算法。其基本原理是，將整數的每個位數上的值進行分組，在分組的過程中對於不足位的數值補零。

radix sort 按照對位數分組的順序的不同，可以分為 LSD（Least Significant Digit）和 MSD（Most Significant Digit）兩種。 LSD radix sort 是按照從低位數到高位數的順序進行分組，而 MSD radix sort 則是按照從高位數到低位數的順序進行分組。兩種方式不僅僅是對位數分組的順序不同，其實作原理也不同。

LSD Radix Sort ​

在 LSD radix sort 中，序列中每個整數的每一位數都可以看成一個桶子，而該位數上的數字就可以認為是這個桶子的鍵值。例如下面的陣列：

txt
[ 170, 45, 75, 90, 802, 2, 24, 66 ]

首先，我們要確認最大值，因為最大值的位數最多。 然後，建立 10 個桶子，亦即 10 個陣列。 接著遍歷所有元素，取其個位數，個位數是什麼就放進對應編號的陣列，例如 1 放進 1 號桶，將上面的陣列進行遍歷後的結果為：

txt
0 號 bucket: [ 170, 90 ]
1 號 bucket: []
2 號 bucket: [ 802, 2 ]
3 號 bucket: []
4 號 bucket: [ 24 ]
5 號 bucket: [ 45, 75 ]
6 號 bucket: [ 66 ]
7 號 bucket: []
8 號 bucket: []
9 號 bucket: []

然後依次將元素從桶子中取出，覆蓋原始陣列或是放到一個新陣列，我們把經過第一次排序的陣列叫 sorted：

txt
sorted = [ 170, 90, 802, 2, 24, 45, 75, 66 ]

再一次遍歷 sorted 陣列的元素，這次取十位數的值。這時要注意，2 不存在十位數，所以預設為 0：

txt
0 號 bucket: [ 2, 802 ]
1 號 bucket: []
2 號 bucket: [ 24 ]
3 號 bucket: []
4 號 bucket: [ 45 ]
5 號 bucket: []
6 號 bucket: [ 66 ]
7 號 bucket: [ 170, 75 ]
8 號 bucket: []
9 號 bucket: [ 90 ]

再全部取出：

txt
sorted = [ 2, 802, 24, 45, 66, 170, 75, 90 ]

開始百位數的入桶操作，沒有百位就預設為 0：

txt
0 號 bucket: [ 2, 24, 45, 66, 75, 90 ]
1 號 bucket: [ 170 ]
2 - 7 號 bucket: []
8 號 bucket: [ 802 ]
9 號 bucket: []

全部取出：

txt
sorted = [ 2, 24, 45, 66, 75, 90, 170, 802 ]

沒有千位數，排序完成，回傳 sorted。具體執行過程如下圖所示：

LSD Radix Sort

程式碼實作：

js
function radixSort(array) {
  const max = Math.max(...array);
  const times = getLoopTimes(max);
  const len = array.length;
  const buckets = [...Array(10)].map(() => []);

  for (let radix = 0; radix < times; radix++) {
    // 個位數、十位數、百位數...
    lsdRadixSort(array, buckets, len, radix);
  }

  return array;
}
/** 根據某個位數上的值得到桶子的編號 */
function getBucketNumber(num, i) {
  return Math.floor((num / Math.pow(10, i - 1)) % 10);
}
/** 獲取數字的位數 */
function getLoopTimes(num) {
  let digits = 0;
  while (num) {
    digits++;
    num = Math.floor(num / 10);
  }
  return digits;
}
function lsdRadixSort(array, buckets, len, radix) {
  // 將數字放入桶子中
  for (let i = 0; i < len; i++) {
    const el = array[i];
    const bucketNum = getBucketNumber(el, radix);
    buckets[bucketNum].push(el);
  }
  let index = 0;
  // 將桶子中的數字取出來，重寫原陣列
  for (let i = 0; i < 10; i++) {
    const bucket = buckets[i];
    for (let j = 0; j < bucket.length; j++) {
      array[index++] = bucket[j];
    }
    bucket.length = 0;
  }
}

MSD Radix Sort ​

接下來我們來看看 MSD radix sort。最開始也是遍歷所有元素，取最大值，得到最大的位數，建立 10 個桶子。這次從百位數取起，不足三位的數字補 0：

txt
0 號 bucket: [ 45, 75, 90, 2, 24, 66 ]
1 號 bucket: [ 107 ]
2 - 7 號 bucket: []
8 號 bucket: [ 802 ]
9 號 bucket: []

接下來就與 LSD 不一樣了。我們要對每個長度大於 1 的桶子進行內部排序，內部排序也是用 radix sort。因此我們需要建立另外 10 個桶子，對 0 號桶子進行入桶操作，這時比原來少一位，也就是十位數：

txt
0 號 bucket: [ 2 ]
1 號 bucket: []
2 號 bucket: [ 24 ]
3 號 bucket: []
4 號 bucket: [ 45 ]
5 號 bucket: []
6 號 bucket: [ 66 ]
7 號 bucket: [ 75 ]
8 號 bucket: []
9 號 bucket: [ 90 ]

然後繼續遞迴上一步，這裡因為每個桶子長度都沒有超過 1，所以可以開始取出收集的工作：

txt
0 號 bucket: [ 2, 24, 45, 66, 75, 90 ]
1 號 bucket: [ 107 ]
2 - 7 號 bucket: []
8 號 bucket: [ 802 ]
9 號 bucket: []

把這個步驟應用到後面的其他桶子就可以完成排序了。

實作程式碼如下：

js
function radixSort2(array) {
  const max = Math.max(...array);
  const times = getLoopTimes(max);
  const len = array.length;
  msdRadixSort(array, len, times);
  return array;
}

function msdRadixSort(array, len, radix) {
  const buckets = [[], [], [], [], [], [], [], [], [], []];
  // 入桶
  for (let i = 0; i < len; i++) {
    const el = array[i];
    const index = getBucketNumber(el, radix);
    buckets[index].push(el);
  }
  // 遞迴每個子桶
  for (let i = 0; i < 10; i++) {
    const bucket = buckets[i];
    if (bucket.length > 1 && radix > 1) {
      msdRadixSort(bucket, bucket.length, radix - 1);
    }
  }
  let k = 0;
  // 重寫原陣列
  for (let i = 0; i < 10; i++) {
    const bucket = buckets[i];
    bucket.forEach((el) => (array[k++] = el));
    bucket.length = 0;
  }
}

字串使用 Radix Sort 實作字典排序 ​

radix sort 只要稍作變換就可以應用於字串的字典排序（lexicographic order）中。例如對都是小寫字母的字串陣列進行排序。

小寫字母一共 26 個，考慮到長度不一樣的情況，我們需要對短的字串進行填充，這時可以補上空字串。然後根據字母與數字的對應關係，建立 27 個桶子，空字串對應 0，a 對應 1，b 對應 2，以此類推。而字典排序的規則是從左到右，所以會需要用到 MSD radix sort。

程式碼實作如下：

js
const character = {};
'abcdefghijklmnopqrstuvwxyz'.split('').forEach((char, index) => {
  character[char] = index + 1;
});
function toNum(c, length) {
  const obj = {};
  obj.c = c;
  obj.arr = [];
  for (let i = 0; i < length; i++) {
    obj.arr[i] = character[c[i]] || 0;
  }
  return obj;
}
function getBucketNumber(obj, i) {
  return obj.arr[i];
}

function lexSort(array) {
  const len = array.length;
  let loopTimes = 0;

  // 求出最長的字串，並得到它的長度，那也是最高位數
  for (let i = 0; i < len; i++) {
    const el = array[i];
    const charLength = el.length;
    if (charLength > loopTimes) {
      loopTimes = charLength;
    }
  }

  // 將字串轉成數字陣列
  const nums = array.map((el) => toNum(el, loopTimes));
  // 開始多關鍵字排序
  msdRadixSort(nums, len, 0, loopTimes);
  // 變回字串
  for (let i = 0; i < len; i++) {
    array[i] = nums[i].c;
  }
  return array;
}

function msdRadixSort(array, len, radix, radixs) {
  const buckets = [];
  for (let i = 0; i <= 26; i++) {
    buckets[i] = [];
  }
  // 入桶
  for (let i = 0; i < len; i++) {
    const el = array[i];
    const index = getBucketNumber(el, radix);
    buckets[index].push(el);
  }
  // 遞迴子桶
  for (let i = 0; i <= 26; i++) {
    const bucket = buckets[i];
    if (bucket.length > 1 && radix < radixs) {
      msdRadixSort(bucket, bucket.length, radix + 1, radixs);
    }
  }
  let k = 0;
  // 重寫原陣列
  for (let i = 0; i <= 26; i++) {
    const bucket = buckets[i];
    for (let j = 0; j < bucket.length; j++) {
      array[k++] = bucket[j];
    }
    bucket.length = 0;
  }
}

複雜度 Complexity ​

NameAverageBestWorstSpaceMethodStable
Radix sortO(n∗k)O(n∗k)O(n∗k)O(n+k)Out-placeYes

k 為桶子數量

參考資料 ​

Copyright © 2024 Sheep Yang