具有生成器函数的递归合并排序无法按预期工作

Question

我试图观察我的递归归并排序每一步对数组进行切片。

function mergeSort(arr) {
  if(arr.length === 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const leftArray = arr.slice(0, mid);
  const rightArray = arr.slice(mid, arr.length);

  console.log(leftArray, rightArray)

  return merge(mergeSort(leftArray), mergeSort(rightArray));
}

function merge(leftArray, rightArray) {
  const sortedArray = [];

  while(leftArray.length > 0 && rightArray.length > 0) {
    if(leftArray[0] < rightArray[0]) {
      sortedArray.push(leftArray[0]);
      leftArray.shift();
    } else {
      sortedArray.push(rightArray[0]);
      rightArray.shift();
    }
  }

  return sortedArray.concat(leftArray).concat(rightArray);
}

如果您看到上面的代码，我正在记录 leftArray 和 rightArray。但是一旦我运行代码，它就会立即记录每一步。为了控制代码的执行，我将我的 mergeSort 函数变成了一个生成器函数，这样每当我运行 .next() 我就可以看到下一个切片。

function * mergeSort(arr) {
  if(arr.length === 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const leftArray = arr.slice(0, mid);
  const rightArray = arr.slice(mid, arr.length);

  yield console.log(leftArray, rightArray);

  return merge(mergeSort(leftArray), mergeSort(rightArray));
}

function merge(leftArray, rightArray) {
  const sortedArray = [];

  while(leftArray.length > 0 && rightArray.length > 0) {
    if(leftArray[0] < rightArray[0]) {
      sortedArray.push(leftArray[0]);
      leftArray.shift();
    } else {
      sortedArray.push(rightArray[0]);
      rightArray.shift();
    }
  }

  return sortedArray.concat(leftArray).concat(rightArray);
}

const list = [32, 12, 23, 52, 5, 16, 74, 21, 33, 55, 85];
const sort = mergeSort(list);

sort.next(); // I expected [32, 12], [23, 52, 5]
sort.next(); // [32, 12] and so on...

原来结果不是我想的那样。如果您对生成器函数的使用提出建议，我将不胜感激！

Answer 1

在合并排序中，数组被分成更小的数组，直到它的大小为1。之后，它合并更小的数组，这样新创建的数组也被排序。

要了解递归，您可以使用缩进来跟踪所有递归级别。例如：

const log = (level, data) => {
    var s = ""
    for (i = 0; i < level; i++) {
        s += "    ";
    }
    console.log(s + data);
}

const merge = (left, right) => {
  const result = [];

  while(left.length && right.length){
    if(left[0] <= right[0]){
      result.push(left.shift());
    }else{
      result.push(right.shift());
    }
  }

  while(left.length) result.push(left.shift());
  while(right.length) result.push(right.shift());
  return result;
}

const mergeSort = (array, level) => {
  log(level, "Start " + array);
  if(array.length < 2) {
    log(level, "Finish " + array);
    return array;
  }

  const middle = Math.floor(array.length / 2);
  log(level, "middle element " + array[middle])
  const leftArr = array.slice(0, middle);
  const rightArr = array.slice(middle, array.length);
  var result = merge(mergeSort(leftArr, level + 1), mergeSort(rightArr, level + 1));
  log(level, "Finish " + result);
  return result;
};

调用level值为1的函数

具有生成器函数的递归合并排序无法按预期工作

Recursive merge sort with a generator function does not work as expected

javascript

recursion

generator