爲什麼QuickSort的這個功能版本會中斷？我該如何解決它？

Question

此實現吹堆棧中的任何大小的陣列上：

function quickSort(arr){ 

    let pivot = arr[arr.length-1] 

    return quickSort(arr.filter((num) => (num < pivot))) 
    .concat(quickSort(arr.filter((num) => (num >= pivot)))) 
} 

爲什麼不這項工作？如果可以修復，我該怎麼做？

Answer 1

想象一下，數組已被排序，例如。 [3]。關鍵將是3和兩個遞歸將是[]和[3]。 []的關鍵是undefined，但是這不會阻止它在大於或小於undefined的情況下進行過濾，這完全沒問題，因爲謂詞永遠不會使用零元素數組進行測試。兩個過濾器都會變成[]，並且您可以從一個[]獲得兩個遞歸。

quickSort([])   // ==> 

quickSort([]) 
.concat(quickSort([])) // ==> 

quickSort([]) 
.concat(quickSort([])) 
.concat(quickSort([])) // ==> 

quickSort([]) 
.concat(quickSort([])) 
.concat(quickSort([])) 
.concat(quickSort([])) // ==> 

... (expands forever on an infinite space machine) 

注意：我只是擴大到左手，因爲右手永遠不會伸手。

所以快排並不排序具有一個或更少元素的數組。在這種情況下，你有一個基本情況，它只是返回數組。

你的實現仍然有問題。想象一下排序[3 3 3]你最終每次都會得到[]和[3 3 3]。傳統上，數據透視表位於兩個排序數組之間，不包含在最後。這樣你就可以快速排除最糟糕的情況，但卻是可行的解決方案。

關於Quicksort is required to be in-place

快速排序，由霍爾在他開創性的論文中定義，是就地 算法。霍爾的就地分區是他的論文的主要貢獻 和quicksort的典型部分。