负整数的基数排序

Question

负整数的基数排序

25

我正在尝试实现整数的基数排序，其中包括负整数。对于非负整数，我计划创建一个由10个队列组成的队列，分别对应数字0-9，并实现LSD算法。但是我对负整数有点困惑。现在我考虑的是，继续为它们创建另一个由10个队列组成的队列，并单独对它们进行排序，最后我会得到两个列表，一个包含已排序的负整数，另一个包含非负整数。最后我会将它们合并。

你对此有何看法？是否有更有效的处理负整数的方法？

- gtkesh

11个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- onurbilginnn · Answer 1

您可以在下面看到JS中用于正整数和负整数的基数排序实现。

const getDigit = (num, place) => {
  return  Math.floor(Math.abs(num) / Math.pow(10, place)) % 10;
}


const maxDigitNumber = arr => {

    const digitCount = (num) =>  {
        return Math.abs(num).toString().length;
    }

    let maxDigit = digitCount(arr[0]);
    for(let num of arr) {
        const digits = digitCount(num);
        if(maxDigit < digits) maxDigit = digits;
    }
    return maxDigit;
}

const radixSort = arr => {
    const maxDigit = maxDigitNumber(arr);
    digitIteration:
    for(let d = 0; d < maxDigit; d++) {
        const bucket = {};
        arrIteration:
        for(let i = 0; i < arr.length; i++) {
            const number = arr[i];
            const digitValue = getDigit(number, d);
            if(!bucket[digitValue]) bucket[digitValue] = [];
            if(number > 0) bucket[digitValue].push(number);            
            else bucket[digitValue].unshift(number);            
        };
        const newArr = [];
        for(let obj in bucket) {
            bucket[obj].map(el => {
                if(el < 0) newArr.unshift(el);
                else newArr.push(el);
            });
        }
        arr = newArr;        
    }
    return arr;
}