我想知道 JavaScript 中這種快速排序實作的時間和空間復雜度是多少。它是否具有超過快速排序的理想時間和空間復雜性，還是相同？（理想的快速排序在最壞的情況下具有 TC O(n^2) 和 SC O(log n)）
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)];
}
我假設它比理想的快速排序實作具有更多的時間和空間復雜性。
uj5u.com熱心網友回復：
最壞情況的時間復雜度也是 O(n2)，例如當輸入已經排序時。
輔助空間復雜度為 O(nlogn)。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/522071.html
上一篇：將陣列的元素聚合為不大于定義的值