13.1 氣泡排序 13.2 選擇排序 13.3 插入排序 13.4 合併排序 13.5 快速排序

Presentation on theme: "13.1 氣泡排序 13.2 選擇排序 13.3 插入排序 13.4 合併排序 13.5 快速排序"— Presentation transcript:

1 13.1 氣泡排序 13.2 選擇排序 13.3 插入排序 13.4 合併排序 13.5 快速排序
Chapter 13 排序 13.1 氣泡排序 13.2 選擇排序 13.3 插入排序 13.4 合併排序 13.5 快速排序 13.6 堆積排序 13.7 二元樹排序 13.8 謝耳排序 13.9 基數排序

2 Chapter 13 排序 排序的方式可以分成兩種： 內部排序（internal sort）
如果記錄是在主記憶體（main memory）中進行分類，則稱之。 外部排序（external sort） 假若記錄太多，以致無法全部存於主記憶體，需借助輔助記憶體，如磁碟或磁帶來進行分類，則稱之。

3 Chapter 13 排序 除了上述內部排序和外部排序之區別外，也可以分成下列兩類： 比較排序（comparative sort）
如果排序方式是比較整個鍵值（key value）的話，則稱之。 分配排序（distributive sort） 假使是一次只比較鍵值的某一位數，此類稱之。

4 Chapter 13 排序 存於檔案（file）中的記錄（record），可能含有相同的鍵值。對於兩個鍵值 k(i) = k(j)的記錄 r(i) 和 r(j)，如果在原始檔案中，r(i) 排在 r(j) 之前；而在排序後，檔案中的 r(i) 仍在 r(j) 之前，則稱此排序具有穩定性（stable）。反之，如果 r(j) 在 r(i) 之前，則稱此排序為不穩定（unstable）。亦即表示當兩個鍵值一樣時並不需要互換，此稱為穩定排序，反之，即使鍵值相同仍需互換者，則稱為不穩定排序。

5 13.1 氣泡排序 氣泡排序（bubble sort）又稱為交換排序（interchange sort）。
13.1 氣泡排序 氣泡排序（bubble sort）又稱為交換排序（interchange sort）。 相鄰兩個相比，假使前一個比後一個大時，則互相對調。 通常有n個資料時需要做n-1次掃瞄，一次掃瞄完後，資料量減少1，當沒有對調時，就表示已排序好了。

6 13.1 氣泡排序 例如有5個資料，分別是18, 2, 20, 34, 12以氣泡排序的步驟如下：

7 13.1 氣泡排序 假設鍵值是12, 18, 2, 20, 34，則需要幾次掃瞄呢?

8 13.1 氣泡排序 由於在第三次掃瞄，沒有做互換的動作，因此可知資料已排序好，不用再比較了。我們可利用一變數加以判斷是否要繼續下一次的掃描與比較。 氣泡排序是stable，最壞時間與平均時間為O(n2)，所需要額外空間也很少。

9 13.2 選擇排序 選擇排序（selection sort）首先在所有的資料中挑選一個最小的放置在第一個位置（因為由小到大排序），再從第二個開始挑選一個最小的放置於第二個位置.....，一直下去。

10 13.2 選擇排序 例如有5個記錄，其鍵值為18, 2, 20, 34, 12。利用選擇排序，其做法如下：
13.2 選擇排序 例如有5個記錄，其鍵值為18, 2, 20, 34, 12。利用選擇排序，其做法如下： 選擇排序跟氣泡排序一樣是stable，最壞時間與平均時間都是O(n2)，所需要額外空間亦很少。

11 13.3 插入排序 插入排序（insertion sort）乃將加入的資料置於適當的位置，如下圖所示：

12 13.3 插入排序 在j的每個步驟將加入的資料，找出其適當的位置如j=4時，加入25，則需將39和45往後移，再將25放在12的後面。餘此類推。 插入排序是stable的性質，最壞時間和平均時間均為O(n2)，所需額外空間很少。

13 13.4 合併排序 合併排序(merge sort)乃是將兩個或兩個以上已排序好的檔案，合併成一個大的已排序好的檔案。

14 13.4 合併排序 假使在一堆無排序的資料，我們可以先將它們一對一合併，再來二對二合併，三對三合併，如下圖所示，假設有下列8個鍵值18, 2, 20,34, 12, 32, 6, 16。

15 13.4 合併排序 從上圖大致可以發現最後合併的動作，乃是和上述將兩個已排序好的資料加以合併而成。
13.4 合併排序 從上圖大致可以發現最後合併的動作，乃是和上述將兩個已排序好的資料加以合併而成。 合併分類是stable，最壞時間與平均時間均為O(nlog2n) 。所需的額外空間與檔案大小成正比。

16 13.5 快速排序 快速排序（quick sort）又稱為劃分交換排序（partition exchange sorting）。就平均時間而言，快速排序是所有排序中最佳的。假設有n個R1, R2, R3, ..., Rn，其鍵值為K1, K2, K3, ..., Kn。

17 13.5 快速排序 快速排序法其步驟如下： 以第一個記錄的鍵值k1做基準K。
13.5 快速排序 快速排序法其步驟如下： 以第一個記錄的鍵值k1做基準K。 由左至右 i = 2,3,...,n，一直找到ki > K。 由右至左 j = n, n-1, n-2, ..., 2，一直找到kj < K 。 當i<j 時Ri與Rj互換，否則R1與Rj互換。

18 13.5 快速排序 例如有十個記錄，其鍵值分別為39, 11, 48, 5, 77, 18, 70, 25, 55, 33，利用快速排序過程如下：

19 13.5 快速排序 此時在39的左半部之鍵值皆比39小，而右半部皆比39大。
13.5 快速排序 此時在39的左半部之鍵值皆比39小，而右半部皆比39大。 再利用上述方法將左半部與右半部排序，形成遞迴（recursive）。 快速排序是unstable，最壞時間是O(n2)，平均時間是O(n log2n) 。

20 13.5 快速排序 全部排序過程如下所示：

21 13.6 堆積排序 堆積（heap）是一棵二元樹，其特性是每一父節點的資料都比它的兩個子節點來得大或等於。
13.6 堆積排序 堆積（heap）是一棵二元樹，其特性是每一父節點的資料都比它的兩個子節點來得大或等於。 而利用heap來排序的方法稱為堆積排序(heap sort)。 圖13-1之(a)符合 heap的定義， 而(b)則否。

22 13.6 堆積排序 如何將圖13-2變成heap的型態呢？

23 13.6 堆積排序 茲以圖13-2之二元樹說明之。 從 開始， A[10] = 25 < A[5] = 67 故不必換。
13.6 堆積排序 茲以圖13-2之二元樹說明之。 從 開始， A[10] = 25 < A[5] = 67 故不必換。 A[4] = 5，其最大子節點 A[8] = 58，因58 > 5， 故將A[4]與A[8]對調。

24 13.6 堆積排序 A[3] = 80與最大子節點A[7] = 62相比，因80 > 62，故不必調換。
13.6 堆積排序 A[3] = 80與最大子節點A[7] = 62相比，因80 > 62，故不必調換。 A[2] = 7，由於其小於 A[5] = 67， 故A[2]與A[5]對調， 然後A[5]又比A[10] 小再調換。

25 13.6 堆積排序 A[1] = 27，小於A[3] = 80，故A[1]與A[3]對調，然後A[3]又比A[7]小再做調換，故二元樹變為

26 13.6 堆積排序 不難看出已經變成heap了，第1個資料80最大，此時80與第10個7對調，對調之後，最後一個資料就固定不動了，下面調整時資料量已減少1個。 完成了將二元樹變為一棵樹heap之後，也可以利用上述的方法繼續調整之。

27 13.6 堆積排序 可是這種方去會浪費很多不必要的比較，因為除了第1個資料外，其餘的資料皆相同，因此可以先令第一個節點為父節點，然後比較左、右子節點，視那一個大，若右子節點大，則只要調整右半部即可；反之，調整左半部（因為不須調整的那半部已符合heap的規則了）。

28 13.6 堆積排序 此時a[1] = 80, A[2] = 67, a[3] = 62, A[4] = 58, A[5] = 25, A[6] = 18, A[7] = 27, A[8] = 5, A[9] = 24, a[10] = 7，當i =1時，樹根節點A[1]與A[10]對調，然後輸出A[10]；i = 2，樹根節點與A[9]對調，然後輸出A[9]，餘此類推。因此[i = 1]時，輸出80，原先堆積變成

29 13.6 堆積排序

30 13.6 堆積排序 此時左、右節點各為67和62，因此將67與父節點7對調，以同樣的方法調整左半部即可（因為67在 父節點的左邊）， 而右半部不必做調整 （因右半段沒更動）。 調整後為

31 13.6 堆積排序 [i = 2]，承i = 1

32 13.6 堆積排序 [i = 3]：承i = 2

33 13.6 堆積排序 [i = 4]：承i = 3

34 13.6 堆積排序 [i = 5]：承i = 4

35 13.6 堆積排序 [i = 6]：承i =5

36 13.6 堆積排序 [i = 7]：承i = 6

37 13.6 堆積排序 [i = 8]：承i = 7

38 13.6 堆積排序 [i = 9]：承i = 8 只剩下節點5，再將其輸出。
13.6 堆積排序 [i = 9]：承i = 8 只剩下節點5，再將其輸出。 此時已全部排序完成，順序為輸出80, 67, 62, 58, 27, 25, 24, 18, 7, 5

39 13.7 二元樹排序 二元樹排序(binary tree sort)乃是先將所有的資料建立成二元搜尋樹，再利用中序法來追蹤，步驟如下：
13.7 二元樹排序 二元樹排序(binary tree sort)乃是先將所有的資料建立成二元搜尋樹，再利用中序法來追蹤，步驟如下： 將第一個資料放在樹根。 進來的資料皆與樹根相比較，若比樹根大，則置於右子樹；反之，置於左子樹。 二元搜尋樹建立完後，利用中序法追蹤，即可得到由小至大的排序資料。

40 13.7 二元樹排序

41 13.7 二元樹排序

42 13.7 二元樹排序 最後利用中序法來追蹤就可排序（由小至大）完成。

43 13.8 謝耳排序 假設有9個資料，分別是18, 2, 20, 34, 12, 32, 6, 16, 25, 10。謝耳排序（shell sort）方法如下： 先將所有的資料分成Y = (9/2)部份，則Y = 4，Y為劃分數，其中1, 5, 9 是第一部份；2, 6屬於第二部份；3, 7是第三部份；4, 8是第四部份。 每一循環的劃分數是Y，皆是上一循環二分數除2，即Yi+1 = Yi/2，最後一個循環的劃分數為1。

44 13.8 謝耳排序 先比較每一部份的前兩個，如[1:5]，[2:6]，[3:7]，[4:8] 。
13.8 謝耳排序 先比較每一部份的前兩個，如[1:5]，[2:6]，[3:7]，[4:8] 。 前兩個比較完成後，再比較每一部份的第二個和第三個，將較小的放入第二個，放入後還要和第一個相比較，若比第一個小，則需要調換。

45 13.8 謝耳排序

46 13.9 基數排序 基數排序（radix sort）又稱為bucket sort或bin sort。
13.9 基數排序 基數排序（radix sort）又稱為bucket sort或bin sort。 它是屬於distribution sort。基數排序是依據每個記錄的鍵值劃分為若干單元，把相同的單元放置在同一箱子。 基數排序是stable，所需的平均時間是O(n logr m) 。

47 13.9 基數排序 然後利用LSD的基數排序，此處所採取的基數為10，第1 次依每個鍵值最右邊的數字，放在對應的箱子，其情形如下所示：

48 13.9 基數排序

49 13.9 基數排序 然後將每一箱的記錄，由F(i)開始，0 < i < r，連接成一鏈結串列，如下所示：
13.9 基數排序 然後將每一箱的記錄，由F(i)開始，0 < i < r，連接成一鏈結串列，如下所示： 同樣的做法，再以每一鍵值由最右邊起的第二位數字為準，將之放置於對應的箱子。

50 13.9 基數排序

51 13.9 基數排序 上圖所形成的鏈結串列如下： 最後再以每一鍵值由最右邊起第三位數字為準，將之放入其所對應的箱子。

52 13.9 基數排序

53 13.9 基數排序 最後所形成的鏈結串列為 此時排序已告完成。