排序(Sort)(三)¶
Da-Wei Chiang¶
- 合併排序法(
Merge Sort)
- 堆積樹排序法(
Heap Sort)
- 快速排序法(
Quick Sort)
合併排序法(Merge Sort)¶
- 使用
Devide and Conquer進行排序
- 先將預排序數怎進行分割, 直到分割至最小單位後再逐一合併
圖例 - 合併排序法(Merge Sort)¶
圖例 - 合併排序法(Merge Sort)¶
圖例 - 合併排序法(Merge Sort)¶
圖例 - 合併排序法(Merge Sort)¶
圖例 - 合併排序法(Merge Sort)¶
圖例 - 合併排序法(Merge Sort)¶
圖例 - 合併排序法(Merge Sort)¶
圖例 - 合併排序法(Merge Sort)¶
圖例 - 合併排序法(Merge Sort)¶
圖例 - 合併排序法(Merge Sort)¶
圖例 - 合併排序法(Merge Sort)¶
圖例 - 合併排序法(Merge Sort)¶
圖例 - 合併排序法(Merge Sort)¶
圖例 - 合併排序法(Merge Sort)¶
圖例 - 合併排序法(Merge Sort)¶
圖例 - 合併排序法(Merge Sort)¶
圖例 - 合併排序法(Merge Sort)¶
圖例 - 合併排序法(Merge Sort)¶
- 請使用數組
[15, 8, 20, 18, 17]撰寫合併排序法, 由小到大排序
堆積樹排序法(Heap Sort)¶
- 按照堆積樹的原理
- 對於最小/最大堆積樹逐一取出root則可獲取經排序的數組
- 請使用數組
[15, 8, 20, 18, 17]撰寫堆積排序法, 由小到大排序
快速排序法(Quick Sort)¶
Step1:對於數組取一個基準值(pivot)Step2:將比基準值小的數放基準值左邊、比基準值大的放基準值右邊。當基準值左邊或右邊為1個或0個數時，則該邊完成排序。Step3:遞迴對基準值左邊/右邊的數組執行Step1&Step2即完成快速排序
圖例 - 快速排序法(Quick Sort)¶
圖例 - 快速排序法(Quick Sort)¶
圖例 - 快速排序法(Quick Sort)¶
圖例 - 快速排序法(Quick Sort)¶
圖例 - 快速排序法(Quick Sort)¶
圖例 - 快速排序法(Quick Sort)¶
圖例 - 快速排序法(Quick Sort)¶
- 請使用數組
[15, 8, 20, 18, 17]撰寫快速排序法, 由小到大排序
總整理¶
- 泡沫排序：$O(n^2)$
- 選擇排序：$O(n^2)$
- 雞尾酒排序：$O(n^2)$
- 插入排序：$O(n^2)$
- 合併排序：$(n-1) + log_2 n = O(nlog_2 n)$
- 分割：長度為
n的陣列切為每個子陣列長度為1需要n−1個步驟
- 合併：假設一開始有4個子陣列合併成2個，最後合併為一個。故為$nlog_2 n$
- 堆積樹排序：$O(nlog n)$
- 快速排序：$O(nlog n)$