Radix Sort trong JavaScript

Thuật toán Radix Sort phân phối số nguyên vào bucket dựa trên chữ số đáng kể (radix). Radix dựa trên hệ số của giá trị mảng. Cách triển khai:

Ví dụ

function radixSort(arr) {
  const maxNum = Math.max(...arr) * 10;
  let divisor = 10;
  while (divisor < maxNum) {
    let buckets = [...Array(10)].map(() => []);
    for (let num of arr) {
      buckets[Math.floor((num % divisor) / (divisor / 10))].push(num);
    }
    arr = [].concat.apply([], buckets);
    divisor *= 10;
  }
  return arr;
}
console.log(radixSort([5,3,88,235,65,23,4632,234]))

Kết quả

[ 3, 5, 23, 65, 88, 234, 235, 4632 ]

Đặc điểm:

• Non-comparison sort (không so sánh cặp)
• Time complexity: O(d * (n + k)) - d: số chữ số, k: base (10)
• Stable sort (giữ thứ tự tương đối)
• Chỉ dành cho số nguyên (integer)
• Space complexity: O(n + k)