快速排序导致栈溢出的问题

javascript 中使用快速排序时，有时会出现调用栈溢出的问题，即超出最大调用栈大小。本文将分析这个问题的常见原因和解决方法。

问题描述

给定数组 arr = [33,77,88,44,55,11,66,99,22,44]，使用以下快速排序函数对其排序：

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

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))
}

当使用方式 1 时，调用 quicksort() 后会产生栈溢出错误，而使用方式 2 则不会。

问题分析

栈溢出是由于函数调用过多导致堆栈空间不足造成的。对于快速排序，当数组长度较大时，以下情况会导致栈溢出：

• 方式 1 中，获取中间键值未同时从数组中移除，导致 subsequent 比较一直成立，造成无限递归调用。
• 方式 2 中，获取中间键值时同时从数组中移除，将 midkey 独立出来，后续比较不会将它作为比较元素，从而避免无限递归调用。

解决方法

根据以上分析，解决栈溢出问题的方法是：

• 采用方式 2，在获取中间键值时同时从数组中移除。

建议实现

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