时间戳

首页 > 解决方案 > 为什么在此快速排序期间超出了我的调用堆栈大小？

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

问题描述

当我尝试在 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]));

标签： javascriptalgorithmsortingquicksort

解决方案

当您的代码构建leftandright数组时，该过程包括枢轴值。因此，这两个子数组的总长度与原始数组的总长度相同。

如果您跳过枢轴元素，则排序有效（至少对于您的测试用例）：

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

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

推荐阅读