javascript - 合并排序正在削减数组中的值

Question

我似乎有一个适用于小数组的基本合并排序，但在较大的 n 值时，它似乎正在破坏和削减值。我正在使用辅助函数 (largetest) 进行测试。

我已经为所有内容添加了条件，验证了切片是否正确(根据我的理解)

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

我一直在 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])

您应该循环遍历两个数组，只要数组值不为 null、未定义或 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;
}