Mergesort正在削减数组中的值。

Question

我似乎有一个基本的合并，用于小型数组，但在较大的n个值时，它似乎正在中断&去除值。我正在使用帮助函数(largetest)进行测试。

我已经为每件事添加了条件，验证了切片是正确的(据我理解)

helper函数可以帮助创建一个大型数组，发现差异点(取消对控制台日志的注释)，并验证长度。

我一直在vscode的quokka.js上运行这个程序。

var mergeSort = function(array) {
  if (array.length === 1) {
    return array;
  }

  const half = Math.floor(array.length / 2);
  let left = array.slice(0, half); 
  let right = array.slice(half); 

  var joined = joinArrays(mergeSort(left), mergeSort(right));
  return joined;
};

const joinArrays = (array1, array2) => {
  var pointer1 = 0;
  var pointer2 = 0;
  let results = [];
  while (array1[pointer1] && array2[pointer2]) {
    if (array1[pointer1] <= array2[pointer2]) {
      results.push(array1[pointer1]);
      pointer1++;
    } else if (array1[pointer1] > array2[pointer2]) {
      results.push(array2[pointer2]);
      pointer2++;
    }
  }
  if (array1[pointer1]) {
    results = results.concat(array1.slice(pointer1));
  } else if (array2[pointer2]) {
    results = results.concat(array2.slice(pointer2));
  }
  return results;
}

var a = mergeSort([4, 7, 4, 3, 9, 1, 2]);
console.log(a);

var a = mergeSort([48, 56, 2, 34, 98, 75, 42, 21, 3])
console.log(a);

var a = mergeSort([5, 6, 98324, 234, 34, 23, 42520, 234, 4323, 32])
console.log(a);

var a = mergeSort([4, 4, 4, 5, 7, 8, 9, 9, 1, 2, 3, ])
console.log(a);

function largeTest () {
  var input = [];
  var sorted;
  var n = 10;
  for (var i = 0; i < n; i++) {
    var number = Math.floor(Math.random() * n);
    input.push(number);
  }
  sorted = input.sort(function (a, b) {
    return a - b;
  }); 
  var result = mergeSort(input);

  console.log(result.length, sorted.length) //Why is it shaving numbers?
  for (var i = 0; i < n; i++) {
    if (result[i] !== sorted[i]) {
      //console.log(i, 'result:', result[i], 'sorted:', sorted[i])
    }
  }

  console.log('complete')
}

largeTest()

Answer 1

问题的核心在于这一行：

while (array1[pointer1] && array2[pointer2])

应该对这两个数组进行循环，只要数组值不是空的、未定义的或0，这个循环就能做到这一点。它的工作原理是在数组结束后读取数组元素，在javascript中返回undefined，因此测试false。测试中的小数组不包含空值，因此代码可以工作，但是填充伪随机数据的较大数组可能会这样做，每个数组都会导致相应切片的末尾被削掉。

可以通过测试数组长度而不是数组内容来解决这个问题：

const joinArrays = (array1, array2) => {
    var pointer1 = 0, len1 = array1.length;
    var pointer2 = 0, len2 = array2.length;
    let results = [];
    while (pointer1 < len1 && pointer2 < len2) {
        if (array1[pointer1] <= array2[pointer2]) {
            results.push(array1[pointer1]);
            pointer1++;
        } else {
            results.push(array2[pointer2]);
            pointer2++;
        }
    }
    if (pointer1 < len1) {
        results = results.concat(array1.slice(pointer1));
    } else if (pointer2 < len2) {
        results = results.concat(array2.slice(pointer2));
    }
    return results;
}

Answer 2

对于合并两个orders数组这样简单的事情，您的joinArrays()函数看起来非常复杂。尝试将这样的merge()函数替换为joinArrays()函数：

function merge( left, right, compare = defaultComparer ) {
  const merged = [];
  let   i      = 0;
  let   j      = 0;
  let   k      = 0;

  // ------------------------------------------------------
  // while we have both a left and right item, just compare
  // them and pick the lowest to put in the merged array
  // ------------------------------------------------------
  while ( i < left.length && j < right.length ) {
    const cc = compare( left[i], right[j] );
    merged[k++] = cc > 0 ? right[j++] : left[i++] ;
  }

  // ------------------------------------------------------
  // if we only have left items... it's easy
  // ------------------------------------------------------
  while ( i < left.length ) {
    merged[k++] = left[i++];
  }

  // ------------------------------------------------------
  // if we only have right items... it's easy
  // ------------------------------------------------------
  while ( j < right.length ) {
    merged[k++] = right[j++];
  }

  // ------------------------------------------------------
  // return the merged array
  // ------------------------------------------------------
  return merged;
}

function defaultComparer( a, b ) {
    return a < b ? -1
         : a > b ? +1
         :          0
         ;
}