資料結構 老師：李崇明 助教：楊斯竣.

Presentation on theme: "資料結構 老師：李崇明 助教：楊斯竣."— Presentation transcript:

1 資料結構 老師：李崇明 助教：楊斯竣

2 課程內容 排序的基本特性 排序種類 排序方法 程式撰寫 依排序後的順序來看 依儲存媒體來看 插入排序法(Insertion Sort)
氣泡排序法(Bubble Sort) 選擇排序法(Selection Sort) 程式撰寫

3 排序的基本特性 依照某種條件將資料項目按順序排列 鍵值 廠商估計，電腦的運算約有25%的執行時間是耗費在排序上。 按照數字的大小由小至大排列
按照筆畫順序排列姓名 鍵值 比如號碼數字、身高，或筆畫數等某種特定的值。 透過鍵值大小的比較來排序。 廠商估計，電腦的運算約有25%的執行時間是耗費在排序上。

4 排序種類-依排序後的順序來看 穩定性(Stable)排序 不穩定性(Unstable)排序
排序過後能使相同數值的資料，保持原順序中之相對位置。 不穩定性(Unstable)排序

5 排序種類-依儲存媒體來看 內部排序(internal sort) 外部排序(external sort)
資料可以全部同時載入主記憶體(main memory)中完成排序。 外部排序(external sort) 資料太多以致無法同時於主記憶體中來完成排序，而需借用輔助記憶體，且必須不斷的做資料抽換的動作。相當的耗時。

6 插入排序法(Insertion Sort)
從第2個資料開始，每次考慮一資料，並依序插入其前面適當的位置。 每到新位置 i，即能找到該數值的適當位置，並保證前 i 個數值皆排序完成。 Input 45 39 12 25 30 第1回合 第2回合 第3回合 第4回合

7 插入排序法(Insertion Sort)
穩定性排序 練習寫出以下數列，使用插入排序法的過程。 Input：21, 76, 85, 7, 32, 64, 101

8

9 氣泡排序法(Bubble Sort) 又稱為交換排序(interchange sort)。
如果是由小排到大，每次都只將相鄰的兩個資料做比較，假使前一個比後一個大時，則互相對調。 每一回合結束，最大值都會被放在對的位置上。 時間複雜度： O(n2) 穩定性排序 Input 18 2 20 34 12 第1回合 第2回合 第3回合 第4回合

10 練習 練習寫出以下數列，使用氣泡排序法的過程。 Input：95, 27, 90, 49, 80, 58, 6, 9, 18, 50

11 95 27 90 49 80 58 6 9 18 50 第1回合 第2回合 第3回合 第4回合 第5回合 第6回合

12 選擇排序法(Selection Sort)
每回合到新位置 i 並與後方最小的值交換，保證前 i 個數值皆排序完成。 時間複雜度： O(n2) 穩定性排序 Input 18 2 20 34 12 第1回合 第2回合 第3回合 第4回合

13 練習 練習寫出以下數列，使用選擇排序法的過程。 Input：95, 27, 90, 49, 80, 58, 6, 9, 18, 50

14 95 27 90 49 80 58 6 9 18 50 第1回合 第2回合 第3回合 第4回合 第5回合 第6回合 第7回合

15 程式碼 Java的陣列提供內建的排序方法 撰寫一程式碼，讓使用者輸入個數及數值資料，將其數列排序並印出。
必須import java.util.*的類別庫 由小到大的內建排序方法：Arrays.sort(陣列名); 撰寫一程式碼，讓使用者輸入個數及數值資料，將其數列排序並印出。

16 合併排序(Merge Sort) 典型的「分而治之」排序法 把陣列分解成後， 再兩兩合併進行排序。

17 快速排序法(Quick Sort) 「分而治之」 (divide and conquer)排序法 從數值中挑一個「基準」(pivot)
比基準小的元素放在基準前方，形成左串列 大的放在後方形成右串列 遞迴將左右串列進行Quick Sort。

18 快速排序法(Quick Sort)

19 練習 練習寫出以下數列，使用快速排序法的過程。 Input：95, 27, 90, 49, 80, 58, 6, 9, 18, 50

20 95 27 90 49 80 58 6 9 18 50 第1回合 第2回合 第3回合 第4回合