快速排序导致栈溢出的问题
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];
