Sorting 排序 Bubble Sort O(n2) Insert Sort Selection Sort Quick Sort

Presentation on theme: "Sorting 排序 Bubble Sort O(n2) Insert Sort Selection Sort Quick Sort"— Presentation transcript:

1 Sorting 排序 Bubble Sort O(n2) Insert Sort Selection Sort Quick Sort
O(n log n) Merge Sort Heap Sort Radix Sort EE.KUAS

2 Bubble Sort EE.KUAS

3 Insert Sort EE.KUAS

4 Selection Sort EE.KUAS

5 Quick Sort 假設有 n 筆資料，其值為Q1、 Q2 … Qn 1. 如果n=1，則return 2. 令分隔點K為第一筆資料的值。
3. 由左至右找出一筆資料Qi ，使得Qi>K 4. 由右至左找出一筆資料Qj ，使得 Qj<K 5. 若 i<j 則將 Qi< Qi 交換，並跳到步驟(2) 6. 若 i>=j。則將K與Qj 交換，並以 j 為基點將資料 分割成左右兩半，然後分別針對左右兩半進行步 驟(1)～步驟(5)。 EE.KUAS

6 Quick Sort EE.KUAS

7 Merge Sort 將N個長度為1的數列，合併為N/2個長度為2的數列 將N/2個長度為2的數列，合併為N/4個長度為4的數列 ………..
EE.KUAS

8 Merge Sort EE.KUAS

9 Heap Sort 最大（小）堆積樹 一個完整二元樹 每一個節點的值都大（小）於子節點的值 堆積樹中最大（小）的元素位於樹根 EE.KUAS

10 Heap Sort 10, 66, 30, 52, 61, 21, 3, 27, 55, 10 10 66 52 61 27 55 30 21 3 EE.KUAS

11 Heap Sort 10, 66, 30, 52, 61, 21, 3, 27, 55, 10 3 10 10 27 61 21 30 52 55 66

12 Heap Sort 10, 66, 30, 52, 61, 21, 3, 27, 55, 10 10 27 10 52 61 21 30 66 55

13 Heap Sort 10, 66, 30, 52, 61, 21, 3, 27, 55, 10 10 27 21 52 61 55 30 66

14 Heap Sort 10, 66, 30, 52, 61, 21, 3, 27, 55, 10 21 27 30 52 61 55 66

15 Radix Sort KEY花色 : >>>
KEY點數 : A>K>Q>J>10>9>8>7>6>5>4>3>2 MSD 優先 : 從最左邊位數開始比較 LSD 優先 : 從最右邊位數開始比較 EE.KUAS

16 Radix Sort 80, 44, 324, 44, 3, 94, 221, 8, 25, 210 MSD 1 2 3 324 4 5 6 7 8 9 1 2 3 324 4 5 6 7 8 9

17 Radix Sort 80, 44, 324, 44, 3, 94, 221, 8, 25, 210 LSD 1 221 2 3 4 5 25 6 7 8 9 3 8 1 210 2 3 4 5 25 6 7 8 80 9 94

18 Radix Sort 80, 44, 324, 44, 3, 94, 221, 8, 25, 210 LSD 1 2 3 324 4 5 6 7 8 9