Crctvyvyvyvyvyvyvyvyvyb7h.C語言-排序法(二).pptx

Bh

1. C 語言 排序法 Sorting ( 二 ) Feng Chia University EE Computer System Lab

2. Divide and Conquer 分治法 分而治之 把大問題切成小問題 小到可以直接求解 最後將小問題的組合成大問題的解 2

3. Merge Sort 合併排序法 拆分 把大陣列切一半成為兩個小陣列 切好的小陣列再各自切一半 重複切半直到每個小陣列都只剩一個元素 合併 排序兩個只剩一個元素的小陣列並合併 把兩邊排序好的小陣列合併並排序成一個陣列 重複排序合併直到所有小陣列都合併成一個大陣列 3

4. 4

5. 5

6. 合併 6

7. Merge Sort 時間複雜度 拆分 有 N 個元素需拆 N -1 次 ( 切 N -1 刀 ) 。 合併 共有 N 個元素的兩個小陣列相合併就需 n 步驟 共有 N 個元素做合併就需 log 2 N 個輪 N x log 2 N = N log 2 N 時間複雜度 (N -1) + nlog 2 n = O( NlogN ) 7

8. Merge Sort 虛擬碼 MergeSort ( arr , left, right){ if left < right mid = ( left+right )/2; MergeSort ( arr , left, mid); MergeSort ( arr , mid+1, right); Merge( arr , left, mid, right); } 8

9. Merge 副程式 9

10. Quick Sort 快速排序法 選出一個基準 從陣列兩端往內掃描，逐一和基準比較 把比基小的都放左邊準，比較大的都放右邊 再重覆處理左邊小陣列，和右邊大陣列 10

11. 11

12. 12

13. 13

14. 14 左右指標都找到位置不正確的數，兩數直接交換

15. 15 左右指標相遇，該數和基準交換 第一輪結束

16. 16 拆分，開始第二輪

17. 17

18. 18 分到只剩一項，解決 ! 開始組合回原本的解

19. 19

20. 20

21. Visualization of Quick sort https://www.youtube.com/watch?v=aXXWXz5rF64 Merge Sort vs Quick Sort https://www.youtube.com/watch?v=es2T6KY45cA 21

22. Quick Sort 時間複雜度 有 N 個元素約需掃描 N 次 。 N 個元素需做 log 2 N 輪 時間複雜度 N x log 2 N = O( NlogN ) 22

23. Quick Sort 虛擬碼 /* low --> Starting index, high --> Ending index */ quickSort ( arr [], low, high){ if (low < high){ /* pi is partitioning index, arr [pi] is now at left place */ pi = partition( arr , low, high); quickSort ( arr , low, pi - 1); // Before pi quickSort ( arr , pi + 1, high); // After pi } } 23

24. 24

25. 25 作業 將 Quick Sort ( 遞迴版本 ) 寫出來 須加註解，可參考網路，但要了解程式碼 C 語言