章節連結
重念一次早該補起來的「資料結構與演算法」。這篇筆記來初步簡介一下 Quick Sort。
課程相關資訊
[連結]：https://hiskio.com/courses/572/lectures/29820
本篇範圍：Chapter 6
請注意：本系列文章為個人對應課程的消化吸收後，所整理出來的內容。換言之，並不一定會包含全部的課程內容，也有可能會添加其他資源來說明。
內容
Quick Sort
1. Quick Sort 會呼叫一個 Partition 分群的函式，其目的是要將小於 pivot 的值和大於 pivot 的值 給分群
2. Pivot 所在的陣列，就是排列好的位置
3. Partition 分群回傳的值，就是「排列好的 index」
4. 接著進行 recursive，將 ( 0, 排列好的 index – 1) -> 代表左側；( 排列好的 index + 1, 尾端 index ) -> 代表右側
5. 初始值為 0, arr.length – 1，這兩個值代表一開始陣列的頭尾
6. Partition 內部的 i 代表有 n 個值小於 pivot
7. Worst Case 是 O(n^2)；最佳為 O(nlogN)；平均為 O(nlogN)
