javascript - 正确的归并排序

Question

所以...如果我输入:

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]

    }

Answer 1

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

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.

并且您需要返回东西才能使递归工作。

放在一起:

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(','));