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