js 快速排序优化 -- 如何防止溢出

Question

function quickSort(arr) {
    let len = arr.length
    if(len <= 1) {
        return arr
    }
    let middle = Math.floor(len / 2)
    let middleArr = [arr[middle]]
    let left = []
    let right = []
    for(let i = 0; i < len; i ++) {
        console.log(count ++, middle, arr[middle])
        if(i == middle) {
            continue
        }

        if(arr[i] > arr[middle]){
            left.push(arr[i])
        } else if(arr[i] < arr[middle]) {
            right.push(arr[i])
        } else {
            middleArr.push(arr[i])
        }
    }
    // 递归
    return [...quickSort(left), ...middleArr, ...quickSort(right)]
}

// 这是没有优化尾部迭代的算法，如果数组过大，会照成溢出，那么优化的思路是怎样的？百度的方式太模糊了

Answer 1

随机打乱数组后再进行快排，这个问题算法书里应该都有解答

Answer 2

讲道理不该溢出啊 你这个函数入栈深度是log(2)n，浏览器调用栈深度在10000以上，不可能有2^10000以上长度的数组啊。

---

不知道你的溢出是指哪里溢出？

Answer 3

提个问题都被踩，我真难。。