js实现基数算法

function radixSort(arr) {
    const max = Math.max(...arr);
    let exp = 1; // 指数，表示当前位数（个位、十位、百位等）

    while (Math.floor(max / exp) > 0) {
        arr = countingSortByDigit(arr, exp);
        exp *= 10;
    }

    return arr;
}

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

    // 统计每个桶中的元素个数
    for (let i = 0; i < n; i++) {
        const digit = Math.floor(arr[i] / exp) % 10;
        count[digit]++;
    }

    // 将count[i]更新为前i个桶中元素的总数
    for (let i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    // 构建输出数组（从后向前遍历以保证稳定性）
    for (let i = n - 1; i >= 0; i--) {
        const digit = Math.floor(arr[i] / exp) % 10;
        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }

    return output;
}

// 示例用法
const arr = [170, 45, 75, 90, 802, 24, 2, 66];
console.log(radixSort(arr)); // 输出: [2, 24, 45, 66, 75, 90, 170, 802]