对整数中的数字进行排序的最有效方法是什么?

问题描述 投票:0回答:1

比如把616变成166,或者885740变成045788。我试过:

parseInt(n.toString().split("").sort().join(""))

它确实有效,但是有没有更高效的方法?

javascript
1个回答
0
投票

避免与字符串之间的转换,您可能会获得更好的性能。为了排序,你可以使用计数排序:只有 10 个不同的数字,在计算它们的出现次数后,你可以重建输出数字:

function countingSortDigits(n) {
    const count = Array(10).fill(0);
    for (; n; n = (n - n % 10) / 10) {
        count[n % 10]++;
    }
    for (let digit = 0; digit < 10; digit++) {
        for (let j = count[digit]; j; j--) {
            n = n*10 + digit;
        }
    }
    return n;
}

以下是执行时间的比较:

function toStringSort(n) { // Asker's implementation 
    return parseInt(n.toString().split("").sort().join(""));
}

function countingSort(n) {
    const count = Array(10).fill(0);
    for (; n; n = (n - n % 10) / 10) {
        count[n % 10]++;
    }
    for (let digit = 0; digit < 10; digit++) {
        for (let i = count[digit]; i; i--) {
            n = n*10 + digit;
        }
    }
    return n;
}

function timeIt(f, repeat) {
    const start = performance.now();
    while (repeat--) f();
    return performance.now() - start;
}

const timing = { toStringSort: 0, countingSort: 0 };
// Execute the functions for 1000 different random integers
for (let i = 0; i < 1000; i++) {
    let n = Math.floor(Math.random() * 1e15);
    timing.toStringSort += timeIt(toStringSort.bind(null, n), 1000);
    timing.countingSort += timeIt(countingSort.bind(null, n), 1000);
}
console.log(timing);

© www.soinside.com 2019 - 2024. All rights reserved.