为什么在此快速排序过程中超出了我的调用堆栈大小？

Question

当我尝试在JS中实现quicksort时出了什么问题？我收到呼叫堆栈大小超出错误。

function quicksort(arr) {
  if (arr.length <= 1)
    return arr;
  let pivot = Math.floor(arr.length / 2);
  const left = [], right = [];
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    }
    else {
      right.push(arr[i]);
    }
  }
  return quicksort(left).concat(pivot, quicksort(right));
}

console.log(quicksort([2, 5, 9, 5, 67, 1, 23, 9]));

Answer 1

可能是因为您的arr.length小于一。

Answer 2

当您的代码构建left和right数组时，该处理includes枢轴值。因此，这两个子阵列的总长度与原始阵列的总长度相同。

如果跳过数据透视元素，则排序有效（至少对于您的测试用例而言：]

function quicksort(arr) {
  if (arr.length <= 1)
    return arr;
  let pp = Math.floor(arr.length / 2), pivot = arr[pp];
  const left = [], right = [];
  for (var i = 0; i < arr.length; i++) {
    if (i == pp) continue;
    if (arr[i] < pivot) {
      left.push(arr[i]);
    }
    else {
      right.push(arr[i]);
    }
  }
  return quicksort(left).concat(pivot, quicksort(right));
}

console.log(quicksort([2, 5, 9, 5, 67, 1, 23, 9]));