快速排序栈溢出问题分析

在尝试使用 javascript 实现快速排序算法时，遇到了一个栈溢出问题，即 "uncaught rangeerror: maximum call stack size exceeded"。问题代码如下：

var quickSort = function(arrTemp) {
    if(arrTemp.length < 2) {
        return arrTemp;
    }
    
    // 方式 1: 使用 arrTemp[middle]
    var midKey = arrTemp[middle];
    
    // 方式 2: 使用 arrTemp.splice(middle, 1)[0]
    // var midKey = arrTemp.splice(middle, 1)[0];
    
    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 时，代码会出现栈溢出问题，但使用方式 2 却不会。这背后的原因是什么？

错误分析

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

在方式 1 中，使用 arrtemp[middle] 获得中间关键字后，没有对 arrtemp 数组进行任何修改。这导致在 subsequent 递归调用中，arrtemp 数组的长度始终为最初长度。

而对于 arrtemp[i] < midkey 判断，只有 midkey 位于 arrtemp 数组首位时才会满足。因此，在方式 1 中，left 数组始终为空，从而导致无限递归调用。

正确做法

在方式 2 中，使用 arrtemp.splice(middle, 1)[0] 获得中间关键字的同时，也会将 midkey 从 arrtemp 数组中移除。这保证了 arrtemp 数组的长度在每次递归调用中都会缩减，从而避免了栈溢出问题。