为什么 JavaScript 快速排序中使用 `splice` 方法可以避免栈溢出？-js教程-PHP中文网

为什么 JavaScript 快速排序中使用 `splice` 方法可以避免栈溢出？

花韻仙語

发布： 2024-11-10 20:03:21

原创

1015人浏览过

为什么 javascript 快速排序中使用 `splice` 方法可以避免栈溢出？

解决 javascript 快速排序中的栈溢出错误

在实现快速排序算法时，有时可能会遇到调用栈溢出错误（uncaught rangeerror: maximum call stack size exceeded）。这通常是由于递归调用过多导致的。

问题示例

考虑以下代码：

立即学习“Java免费学习笔记（深入）”；

arr = [33, 77, 88, 44, 55, 11, 66, 99, 22, 44];

var quickSort = function(arrTemp) {
  if (arrTemp.length < 2) {
    return arrTemp;
  }

  var middle = Math.floor(arrTemp.length / 2);
  var midKey = arrTemp[middle]; // 方式 1
  // var midKey = arrTemp.splice(middle, 1)[0]; // 方式 2

  var left = [];
  var right = [];

  for (var i = 0; i < arrTemp.length; i++) {
    if (arrTemp[i] < midKey) {
      left.push(arrTemp[i]);
    } else {
      right.push(arrTemp[i]);
    }
  }

  return quickSort(left).concat([midKey], quickSort(right));
};

console.log(quickSort(arr));

登录后复制

使用方式 1 时会发生栈溢出，但使用方式 2 不会。