Thực Hiện Sắp Xếp Phân Phối (Radix Sort) Trong JavaScript

function getMax(arr) {
    let max = arr[0];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

function countingSort(arr, exp) {
    let n = arr.length;
    let output = new Array(n);
    let count = new Array(10).fill(0);

    // Đếm số lần xuất hiện của các chữ số
    for (let i = 0; i < n; i++) {
        let index = Math.floor(arr[i] / exp) % 10;
        count[index]++;
    }

    // Thay đổi count[i] để chứa vị trí của chữ số trong output[]
    for (let i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    // Xây dựng mảng output[]
    for (let i = n - 1; i >= 0; i--) {
        let index = Math.floor(arr[i] / exp) % 10;
        output[count[index] - 1] = arr[i];
        count[index]--;
    }

    // Sao chép mảng output[] vào arr[], để arr[] chứa các số đã sắp xếp theo chữ số hiện tại
    for (let i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

function radixSort(arr) {
    // Tìm giá trị lớn nhất để biết số chữ số tối đa
    let max = getMax(arr);

    // Thực hiện sắp xếp đếm cho từng chữ số
    for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
        countingSort(arr, exp);
    }
}

// Ví dụ kiểm tra
let arr = [170, 45, 75, 90, 802, 24, 2, 66];
radixSort(arr);
console.log(arr); // [2, 24, 45, 66, 75, 90, 170, 802]

let arr = [170, 45, 75, 90, 802, 24, 2, 66];
radixSort(arr);
console.log(arr); // [2, 24, 45, 66, 75, 90, 170, 802]