JavaScript:重新排序数组

Question

我读了一些关于处理拼接时问题的答案(包括 Move an array element from one array position to another )，但我无法解决我的问题。

我正在尝试以特定模式重新排序数组。我们假设模式是所有负数都应该位于数组的左侧，所有正数字都应该位于数组的左侧>数组的右侧。负数和正数应该用零分隔(如果有)。 维持秩序很重要

Sample Input   = [3,0,2,-1,0,-3]
Desired Output = [-1,-3,0,0,3,2]

这是我写的代码

function reorderArray(inputArray) {
origLength = inputArray.length
var indexZero = -1;
  for (var i = 0; i < origLength; i++) {
    if (inputArray[i] > 0) {
        inputArray.push(inputArray[i]);
        inputArray.splice(i, 1);
    } else if (indexZero == -1 && inputArray[i] == 0) {
        indexZero = i;
    } else if (indexZero != -1 && inputArray[i] < 0) {
        inputArray.splice(indexZero, 0, inputArray.splice(i, 1))
        indexZero++;
    }
  }
alert(inputArray);
}

我在第一步本身遇到了一个问题，由于重新索引，我尝试将所有正数移到数组后面。我无法从最后一个索引开始，因为这意味着丢失顺序，而且我无法使用 i-- 因为它会无限运行。

任何有关如何使我的代码工作的帮助将不胜感激。此外，如果有一种比拼接更有效的替代方案，也将受到欢迎。

谢谢。

Answer 1

var input = [3,0,2,-1,0,-3];

var copy = input.slice(0); // you need an original array copy since you need to
                           // refer to it to maintain the original order

input.sort(function(a, b) {
    var sign_a = Math.sign(a),
        sign_b = Math.sign(b);

    if (sign_a != sign_b) {
        return sign_a - sign_b;
    }

    return copy.indexOf(a) - copy.indexOf(b);
});

console.log(input);

JSFiddle:http://jsfiddle.net/w2g195fy/2/

因此，您首先按符号比较数字，然后通过比较原始数组中的位置来保证排序稳定性。后者重要，因为 Array.prototype.sort() 不保证稳定。

另一个重要说明:此特定实现的复杂性(从比较次数的 Angular 来看)是O(N^2 * logN)，这可能是 Not Acceptable 如果你有很大的原始数组。

另一个重要注意事项:如果您的输入数组有重复值，它将不起作用。

这是一个简单的实现，可以处理重复项:

var input = [1, -1, 2, 0, -2, 3, 0, -3, -4, 4, 0];

var groups = input.reduce(function(result, item) {
    result[Math.sign(item)].push(item);
    return result;
}, {'-1': [], 0: [], 1: []});

var result = groups['-1'].concat(groups[0]).concat(groups[1]);

console.log(result)

这是我能想到的最有效的解决方案(从内存和比较次数的 Angular 来看 - 它是 O(N)):

var input = [1, -4, 2, 0, -2, 3, 0, -3, -4, 4, 0];

var result = [];

for (var sign = -1, len = input.length; sign <= 1; ++sign) {
    for (var i = 0; i < len; ++i) {
        if (Math.sign(input[i]) == sign) {
            result.push(input[i]);
        }
    }
}

console.log(result);

http://jsfiddle.net/pbmw4dtt/