关于JavaScript实现的快速排序算法的时间与空间复杂度问询

先看你提供的JavaScript快速排序实现：

function quickSort(arr)
{
    if(arr.length == 1)
        return arr
    
    let pivot = arr[arr.length-1];
    let left = [], right= [];

    for(let i=0; i<arr.length-1; i++)
        arr[i] <= pivot ? left.push(arr[i]) : right.push(arr[i]);

    if(left.length && right.length)
        return [...quickSort(left), pivot, ...quickSort(right)]
    else if(left.length)
        return [...quickSort(left), pivot]
    else
        return [pivot, ...quickSort(right)];
}

时间复杂度（TC） #

• 平均情况：O(n log n)，和理想快速排序一致。每次递归会遍历当前数组的所有元素（O(n)），平均情况下数组会被分成两个规模相近的子数组，递归深度为O(log n)，总时间复杂度为n * log n。
• 最坏情况：O(n²)，同样和理想快速排序一致。当输入数组已经完全有序（或逆序）时，每次选择最后一个元素作为基准（pivot）会导致子数组规模极不均衡（一个子数组长度为n-1，另一个为空），递归深度变为O(n)，总时间复杂度为n * n。

空间复杂度（SC） #

这个实现的空间复杂度远高于理想快速排序：

• 平均情况：O(n log n)。不同于理想的原地快速排序仅使用递归栈空间，该实现每次递归都会创建left、right两个新数组存储分区元素，且返回结果时会通过扩展运算符...创建新的合并数组。每层递归的总存储空间为O(n)，平均递归深度为O(log n)，因此总空间复杂度为n * log n。
• 最坏情况：O(n²)。当数组有序时，每层递归创建的子数组长度依次为n-1、n-2...1，累加总存储空间为O(n²)，再加上递归栈的O(n)空间，主导项为O(n²)。

而理想快速排序的空间复杂度仅来自递归栈，平均为O(log n)，最坏为O(n)，相比之下该实现的空间开销大得多。

结论 #

时间复杂度和理想快速排序完全相同，但空间复杂度显著高于理想实现，你的假设中关于空间复杂度的部分是正确的。

内容的提问来源于stack exchange，提问作者Mohd Tazammul