如何在线性时间内按绝对值对排序数组进行重新排序？

Question

您将获得一个包含负值和正值的排序数组.采用负数绝对值的阵列.你的复杂性应该是O(n)

样本输入

[-8, -5, -3, -1, 3, 6, 9]

预期产出

[ -1, -3, 3, -5, 6, -8, 9 ]

到目前为止我已经这样做了,但输出不正确.

function sortMe(input) {
   var newArr = [];
   for (var i = 0; i < input.length; i++) {
     var value = Math.abs(input[i]);
     newArr.push(value);
   }
   var c = newArr.sort()
}

它正在提供输出

[ 1, 3, 3, 5, 6, 8, 9 ]

Answer 1

1. 将阵列分成两半,一个带负数,另一个带正数.

2. 反转负数数组.

3. 然后,使用两个数组的绝对值运行合并算法.

整体运行时复杂性仍为O(n).

function sortMe(sortedArray) {

  var idx = -1, negs, pos, result = [], nIdx = 0, pIdx = 0;

  if (sortedArray.length === 0)
    return result;

  // Find the index where positive elements begin
  while (idx < sortedArray.length && sortedArray[++idx] < 0);

  // Get elements till the index and reverse the array
  negs = sortedArray.slice(0, idx).reverse();

  // Get elements from the index till the end
  pos = sortedArray.slice(idx);

  // Merging algorithm implementation which merges `negs` and `pos`
  while (nIdx < negs.length || pIdx < pos.length)
  {
    if (nIdx < negs.length && pIdx < pos.length)
    {
      if (Math.abs(negs[nIdx]) <= pos[pIdx])
        result.push(negs[nIdx++]);
      else
        result.push(pos[pIdx++]);
    }
    else if (nIdx < negs.length)
      result.push(negs[nIdx++]);
    else
      result.push(pos[pIdx++]);
  }

  return result;
}

console.log(sortMe([-8, -5, -3, -1, 3, 6, 9]));
// [ -1, -3, 3, -5, 6, -8, 9 ]

function sortMe(sortedArray) {

  var idx = -1, negs, pos, result = [], nIdx = 0, pIdx = 0;

  if (sortedArray.length === 0)
    return result;

  // Find the index where positive elements begin
  while (idx < sortedArray.length && sortedArray[++idx] < 0);

  // Get elements till the index and reverse the array
  negs = sortedArray.slice(0, idx).reverse();

  // Get elements from the index till the end
  pos = sortedArray.slice(idx);

  // Merging algorithm implementation which merges `negs` and `pos`
  while (nIdx < negs.length || pIdx < pos.length)
  {
    if (nIdx < negs.length && pIdx < pos.length)
    {
      if (Math.abs(negs[nIdx]) <= pos[pIdx])
        result.push(negs[nIdx++]);
      else
        result.push(pos[pIdx++]);
    }
    else if (nIdx < negs.length)
      result.push(negs[nIdx++]);
    else
      result.push(pos[pIdx++]);
  }

  return result;
}

function getElement(id) {
  return document.getElementById(id);
}

function sorter() {
  var data = getElement("numbers").value.split(" ").map(Number);
  getElement("result").innerHTML = "[" + sortMe(data).join(", ") + "]";
}

<input id="numbers" value="-8 -5 -3 -1 3 6 9" />
<input type="button" onclick="sorter()" value="Click here to Sort" />
<pre id="result" />