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

Question

当我尝试在 JS 中实现快速排序时出了什么问题？我收到调用堆栈大小超出错误。

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 数组时，该过程包括主元值。因此这两个子数组的总长度与原始数组的总长度相同。

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

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]));

正如我在上面的评论中指出的那样，与其他优秀的排序算法相比，快速排序的一个关键特性是它可以通过恒定的 space 开销来完成。实际实现不会创建新的子数组。相反，他们重新排列原始数组中的元素。递归步骤包括开始和结束索引而不是完整的新数组。

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

Why is my call stack size exceeded during this quicksort?

javascript

sorting

algorithm

quicksort