javascript - 正确的合并排序

所以...如果我输入：

4 1 5 3

代替1,3,4,5

我得到[4，1，5，3]

以下是用于合并排序的代码，但对于最后一次比较，该程序未获取更新的（1,4）（3,5）值，而是获取了（4,1）（5,3）的值，从而得出错误的结果。

 var a = [4, 1, 5, 3];
    q(a);
    function q(a) {
      var start = 0;
      var n = a.length;
      var length = parseInt(n / 2);
      if (n < 2) {
        return n;
      }
      var l = [], r = [];
      for (i = 0; i < length; i++) {
        l[i] = a[i];  //left array
      }
      for (i = 0, j = length; j < n; i++ , j++) {
        r[i] = a[j];   //right array
      }
      q(l);           //merge sort left array
      q(r);           //merge sort right array
      comp(l, r);
    }

    function comp(l, r) {
      var k = [], m = 0, i = 0, j = 0;
      while (i < ((l.length)) && j < ((r.length))) {
        if (l[i] < r[j]) {
          k[m] = l[i];
          i++;
          m++
        }
        else {
          k[m] = r[j];
          j++;
          m++
        }
      }
      while (i != (l.length)) {
        k[m] = l[i];
        m++;
        i++;
      }
      while (j != (r.length)) {
        k[m] = r[j];
        m++;
        j++;
      }
      console.log(k); //for final output it is [ 4, 1, 5, 3 ] instead of [1,3,4,5]

    }

最佳答案

您有几个小问题。最主要的是您要从边缘条件中返回错误的东西：

if (n < 2) {
    return n; // n is just a length; doesn't make sense to return it.
}

n是长度，您真的想在这里返回小数组：

  if (n < 2) {
    return a;  // return the array instead
  }

另外，您需要将递归调用的结果传递给comp函数。现在，您只返回原始列表：

 comp(l, r)

这样的事情会更好：

  let l_sort = q(l);           //merge sort left array
  let r_sort = q(r);           //merge sort right array
  return comp(l_sort, r_sort); // merge the arrays when recursion unwinds.

并且您需要return东西才能递归工作。

放在一起：

function q(a) {
  var start = 0;
  var n = a.length;
  var length = parseInt(n / 2);
  if (n < 2) {
    return a;
  }
  var l = [],
    r = [];
  for (i = 0; i < length; i++) {
    l[i] = a[i]; //left array
  }
  for (i = 0, j = length; j < n; i++, j++) {
    r[i] = a[j]; //right array
  }
  let l_sort = q(l); //merge sort left array
  let r_sort = q(r); //merge sort right array
  return comp(l_sort, r_sort);
}

function comp(l, r) {
  var k = [],
    m = 0,
    i = 0,
    j = 0;
  while (i < ((l.length)) && j < ((r.length))) {
    if (l[i] < r[j]) {
      k[m] = l[i];
      i++;
      m++
    } else {
      k[m] = r[j];
      j++;
      m++
    }
  }
  while (i != (l.length)) {
    k[m] = l[i];
    m++;
    i++;
  }
  while (j != (r.length)) {
    k[m] = r[j];
    m++;
    j++;
  }
  return k
}

console.log(q([4, 1, 5, 3]).join(','));
console.log(q([5, 4, 3, 2, 1]).join(','));
console.log(q([2, 3]).join(','));
console.log(q([3, 2]).join(','));
console.log(q([1]).join(','));

关于javascript - 正确的合并排序，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/55710541/