Sắp xếp Radix (Radix Sort) trong JavaScript

Sắp xếp Radix (Radix Sort)

Sắp xếp Radix là một thuật toán sắp xếp dữ liệu với khóa nguyên bằng cách nhóm các khóa theo các chữ số riêng lẻ chia sẻ cùng vị trí và giá trị quan trọng.

Chúng ta cần viết một hàm JavaScript nhận vào một mảng các giá trị chữ nghĩa làm đối số duy nhất. Hàm nên sắp xếp mảng theo thứ tự tăng dần hoặc giảm dần bằng thuật toán radix sort.

Ví dụ

Dưới đây là mã nguồn:

const arr = [45, 2, 56, 2, 5, 6, 34, 1, 56, 89, 33]; const radixSort = (arr = []) => {    const base = 10;    let divider = 1;    let maxVal = Number.NEGATIVE_INFINITY;    while (divider === 1 || divider <= maxVal) {       const buckets = [...Array(10)].map(() => []);       for (let val of arr) {          buckets[Math.floor((val / divider) % base)].push(val);          maxVal = val > maxVal ? val : maxVal;       }       arr = [].concat(...buckets);       divider *= base;    };    return arr; }; console.log(radixSort(arr));

Kết quả

Đầu ra trên console:

[    1, 2, 2, 5, 6,    33, 34, 45, 56, 56,    89 ]

Lưu ý: Radix sort chỉ hoạt động với số nguyên không âm. Độ phức tạp O(d*(n+b)) với d là số chữ số, b là cơ số (base).