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

Question

比如把616变成166，或者885740变成045788。我试过：

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

它确实有效，但是有没有更高效的方法？

Answer 1

避免与字符串之间的转换，您可能会获得更好的性能。为了排序，你可以使用计数排序：只有 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);