编辑代码

function countSort1(arr: number[]): void {
    let n: number = arr.length;
    let maxValue: number = Math.max(...arr);
    let countArr: number[] = new Array(maxValue + 1).fill(0);
    
    for (let i: number = 0; i < n; i++) {
        countArr[arr[i]]++;
    }
    
    let sortedIndex: number = 0;
    for (let i: number = 0; i <= maxValue; ++i) {
        while (countArr[i]) {
            arr[sortedIndex++] = i;
            countArr[i]--;
        }
    }
    console.log(arr);
}

function countSort2(arr: number[]): void {
    let n: number = arr.length;
    let maxValue: number = Math.max(...arr);
    let minValue: number = Math.min(...arr);
    let d: number = maxValue - minValue + 1;
    let countArr: number[] = new Array(d).fill(0);
    let sortArr: number[] = new Array(n).fill(0);
    
    for (let i: number = 0; i < n; ++i) {
        countArr[arr[i] - minValue]++;
    }

    for (let i: number = 1; i < d; ++i) {
        countArr[i] += countArr[i - 1];
    }
    
    for (let i: number = n - 1; i >= 0; --i) {
        sortArr[countArr[arr[i] - minValue] - 1] = arr[i];
        countArr[arr[i] - minValue]--;
    }

    arr = sortArr.copyWithin(0, n);

    console.log(arr);
}

const arr: number[] = [9, 4, 3, 2, 5, 7, 6, 1, 8, 10];
// countSort1(arr);
countSort2(arr);