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]

    }

标签： javascript

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.

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