推 BroccolYee: 只有4,5 1,2算swap 剩下都是兩個串列擺前後直接合併 01/10 17:09
→ BroccolYee: 另外quick sort的空間複雜度是call遞迴stack的層數 01/10 17:10
→ BroccolYee: 它依然是in-place 01/10 17:10
推 FRAXIS: Quicksort 算不算 inplace 取決於你 inplace 的定義 01/10 22:55
→ FRAXIS: 如果你定義 inplace 是最多只能用 O(1) 額外空間，那 01/10 22:56
→ FRAXIS: quicksort 就不是 in-place 01/10 22:58
→ FRAXIS: 不過因為 quicksort 有一種版本可以最多只使用O(lg n) 01/10 22:58
→ FRAXIS: 空間 所以很多人也認為 quicksort 是 in-place 01/10 22:59
→ FRAXIS: 理論上 quicksort 可以只使用 O(1) 空間，只是方法很複雜 01/10 22:59
→ FRAXIS: 所以教科書上也不會提 01/10 23:00
推 kyrie77: 推F大 01/11 05:15