电脑的基本操作课件.ppt
Chapter 13 排序,13.1 氣泡排序13.2 選擇排序13.3 插入排序13.4 合併排序13.5 快速排序,13.6 堆積排序13.7 二元樹排序13.8 謝耳排序13.9 基數排序,資料結構-使用 C 語言 2,Chapter 13 排序,排序的方式可以分成兩種：內部排序（internal sort）如果記錄是在主記憶體（main memory）中進行分類，則稱之。外部排序（external sort）假若記錄太多，以致無法全部存於主記憶體，需借助輔助記憶體，如磁碟或磁帶來進行分類，則稱之。,資料結構-使用 C 語言 3,Chapter 13 排序,除了上述內部排序和外部排序之區別外，也可以分成下列兩類：比較排序（comparative sort）如果排序方式是比較整個鍵值（key value）的話，則稱之。分配排序（distributive sort）假使是一次只比較鍵值的某一位數，此類稱之。,資料結構-使用 C 語言 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）。亦即表示當兩個鍵值一樣時並不需要互換，此稱為穩定排序，反之，即使鍵值相同仍需互換者，則稱為不穩定排序。,資料結構-使用 C 語言 5,13.1 氣泡排序,氣泡排序（bubble sort）又稱為交換排序（interchange sort）。相鄰兩個相比，假使前一個比後一個大時，則互相對調。通常有n個資料時需要做n-1次掃瞄，一次掃瞄完後，資料量減少1，當沒有對調時，就表示已排序好了。,資料結構-使用 C 語言 6,13.1 氣泡排序,例如有5個資料，分別是18,2,20,34,12以氣泡排序的步驟如下：,資料結構-使用 C 語言 7,13.1 氣泡排序,假設鍵值是12,18,2,20,34，則需要幾次掃瞄呢?,資料結構-使用 C 語言 8,13.1 氣泡排序,由於在第三次掃瞄，沒有做互換的動作，因此可知資料已排序好，不用再比較了。我們可利用一變數加以判斷是否要繼續下一次的掃描與比較。氣泡排序是stable，最壞時間與平均時間為O(n2)，所需要額外空間也很少。,資料結構-使用 C 語言 9,13.2 選擇排序,選擇排序（selection sort）首先在所有的資料中挑選一個最小的放置在第一個位置（因為由小到大排序），再從第二個開始挑選一個最小的放置於第二個位置.，一直下去。,資料結構-使用 C 語言 10,13.2 選擇排序,例如有5個記錄，其鍵值為18,2,20,34,12。利用選擇排序，其做法如下：選擇排序跟氣泡排序一樣是stable，最壞時間與平均時間都是O(n2)，所需要額外空間亦很少。,資料結構-使用 C 語言 11,13.3 插入排序,插入排序（insertion sort）乃將加入的資料置於適當的位置，如下圖所示：,資料結構-使用 C 語言 12,13.3 插入排序,在j的每個步驟將加入的資料，找出其適當的位置如j=4時，加入25，則需將39和45往後移，再將25放在12的後面。餘此類推。插入排序是stable的性質，最壞時間和平均時間均為O(n2)，所需額外空間很少。,資料結構-使用 C 語言 13,13.4 合併排序,合併排序(merge sort)乃是將兩個或兩個以上已排序好的檔案，合併成一個大的已排序好的檔案。,資料結構-使用 C 語言 14,13.4 合併排序,假使在一堆無排序的資料，我們可以先將它們一對一合併，再來二對二合併，三對三合併，如下圖所示，假設有下列8個鍵值18,2,20,34,12,32,6,16。,資料結構-使用 C 語言 15,13.4 合併排序,從上圖大致可以發現最後合併的動作，乃是和上述將兩個已排序好的資料加以合併而成。合併分類是stable，最壞時間與平均時間均為O(nlog2n)。所需的額外空間與檔案大小成正比。,資料結構-使用 C 語言 16,13.5 快速排序,快速排序（quick sort）又稱為劃分交換排序（partition exchange sorting）。就平均時間而言，快速排序是所有排序中最佳的。假設有n個R1,R2,R3,.,Rn，其鍵值為K1,K2,K3,.,Kn。,資料結構-使用 C 語言 17,13.5 快速排序,快速排序法其步驟如下：以第一個記錄的鍵值k1做基準K。由左至右 i=2,3,.,n，一直找到ki K。由右至左 j=n,n-1,n-2,.,2，一直找到kj K。當ij 時Ri與Rj互換，否則R1與Rj互換。,資料結構-使用 C 語言 18,13.5 快速排序,例如有十個記錄，其鍵值分別為39,11,48,5,77,18,70,25,55,33，利用快速排序過程如下：,資料結構-使用 C 語言 19,13.5 快速排序,此時在39的左半部之鍵值皆比39小，而右半部皆比39大。再利用上述方法將左半部與右半部排序，形成遞迴（recursive）。快速排序是unstable，最壞時間是O(n2)，平均時間是O(n log2n)。,資料結構-使用 C 語言 20,13.5 快速排序,全部排序過程如下所示：,資料結構-使用 C 語言 21,13.6 堆積排序,堆積（heap）是一棵二元樹，其特性是每一父節點的資料都比它的兩個子節點來得大或等於。而利用heap來排序的方法稱為堆積排序(heap sort)。圖13-1之(a)符合heap的定義，而(b)則否。,資料結構-使用 C 語言 22,13.6 堆積排序,如何將圖13-2變成heap的型態呢？,資料結構-使用 C 語言 23,13.6 堆積排序,茲以圖13-2之二元樹說明之。從 開始，A10=25 5，故將A4與A8對調。,資料結構-使用 C 語言 24,13.6 堆積排序,A3=80與最大子節點A7=62相比，因80 62，故不必調換。A2=7，由於其小於A5=67，故A2與A5對調，然後A5又比A10小再調換。,資料結構-使用 C 語言 25,13.6 堆積排序,A1=27，小於A3=80，故A1與A3對調，然後A3又比A7小再做調換，故二元樹變為,資料結構-使用 C 語言 26,13.6 堆積排序,不難看出已經變成heap了，第1個資料80最大，此時80與第10個7對調，對調之後，最後一個資料就固定不動了，下面調整時資料量已減少1個。完成了將二元樹變為一棵樹heap之後，也可以利用上述的方法繼續調整之。,資料結構-使用 C 語言 27,13.6 堆積排序,可是這種方去會浪費很多不必要的比較，因為除了第1個資料外，其餘的資料皆相同，因此可以先令第一個節點為父節點，然後比較左、右子節點，視那一個大，若右子節點大，則只要調整右半部即可；反之，調整左半部（因為不須調整的那半部已符合heap的規則了）。,資料結構-使用 C 語言 28,13.6 堆積排序,此時a1=80,A2=67,a3=62,A4=58,A5=25,A6=18,A7=27,A8=5,A9=24,a10=7，當i=1時，樹根節點A1與A10對調，然後輸出A10；i=2，樹根節點與A9對調，然後輸出A9，餘此類推。因此i=1時，輸出80，原先堆積變成,資料結構-使用 C 語言 29,13.6 堆積排序,資料結構-使用 C 語言 30,13.6 堆積排序,此時左、右節點各為67和62，因此將67與父節點7對調，以同樣的方法調整左半部即可（因為67在父節點的左邊），而右半部不必做調整（因右半段沒更動）。調整後為,資料結構-使用 C 語言 31,13.6 堆積排序,i=2，承i=1,資料結構-使用 C 語言 32,13.6 堆積排序,i=3：承i=2,資料結構-使用 C 語言 33,13.6 堆積排序,i=4：承i=3,資料結構-使用 C 語言 34,13.6 堆積排序,i=5：承i=4,資料結構-使用 C 語言 35,13.6 堆積排序,i=6：承i=5,資料結構-使用 C 語言 36,13.6 堆積排序,i=7：承i=6,資料結構-使用 C 語言 37,13.6 堆積排序,i=8：承i=7,資料結構-使用 C 語言 38,13.6 堆積排序,i=9：承i=8只剩下節點5，再將其輸出。此時已全部排序完成，順序為輸出80,67,62,58,27,25,24,18,7,5,資料結構-使用 C 語言 39,13.7 二元樹排序,二元樹排序(binary tree sort)乃是先將所有的資料建立成二元搜尋樹，再利用中序法來追蹤，步驟如下：將第一個資料放在樹根。進來的資料皆與樹根相比較，若比樹根大，則置於右子樹；反之，置於左子樹。二元搜尋樹建立完後，利用中序法追蹤，即可得到由小至大的排序資料。,資料結構-使用 C 語言 40,13.7 二元樹排序,資料結構-使用 C 語言 41,13.7 二元樹排序,資料結構-使用 C 語言 42,13.7 二元樹排序,最後利用中序法來追蹤就可排序（由小至大）完成。,資料結構-使用 C 語言 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。,資料結構-使用 C 語言 44,13.8 謝耳排序,先比較每一部份的前兩個，如1:5，2:6，3:7，4:8。前兩個比較完成後，再比較每一部份的第二個和第三個，將較小的放入第二個，放入後還要和第一個相比較，若比第一個小，則需要調換。,資料結構-使用 C 語言 45,13.8 謝耳排序,資料結構-使用 C 語言 46,13.9 基數排序,基數排序（radix sort）又稱為bucket sort或bin sort。它是屬於distribution sort。基數排序是依據每個記錄的鍵值劃分為若干單元，把相同的單元放置在同一箱子。基數排序是stable，所需的平均時間是O(n logr m)。,資料結構-使用 C 語言 47,13.9 基數排序,然後利用LSD的基數排序，此處所採取的基數為10，第1 次依每個鍵值最右邊的數字，放在對應的箱子，其情形如下所示：,資料結構-使用 C 語言 48,13.9 基數排序,資料結構-使用 C 語言 49,13.9 基數排序,然後將每一箱的記錄，由F(i)開始，0 i r，連接成一鏈結串列，如下所示：同樣的做法，再以每一鍵值由最右邊起的第二位數字為準，將之放置於對應的箱子。,資料結構-使用 C 語言 50,13.9 基數排序,資料結構-使用 C 語言 51,13.9 基數排序,上圖所形成的鏈結串列如下：最後再以每一鍵值由最右邊起第三位數字為準，將之放入其所對應的箱子。,資料結構-使用 C 語言 52,13.9 基數排序,資料結構-使用 C 語言 53,13.9 基數排序,最後所形成的鏈結串列為此時排序已告完成。,
