第10章內(nèi)排序

1、第第10章章 內(nèi)內(nèi) 排排 序序10.6 基數(shù)排序基數(shù)排序10.1 排序的基本概念排序的基本概念10.2 插入排序插入排序10.3 交換排序交換排序10.4 選擇排序選擇排序10.5 歸并排序歸并排序10.7 各種內(nèi)排序方法的比較和選擇各種內(nèi)排序方法的比較和選擇10.1 排序的基本概念排序的基本概念 所謂排序，是要整理表中的記錄，使之按關(guān)鍵字遞增所謂排序，是要整理表中的記錄，使之按關(guān)鍵字遞增（或遞減）有序排列。其確切定義如下：（或遞減）有序排列。其確切定義如下： 輸入：輸入：n個記錄個記錄,R0,R1,Rn-1,其相應(yīng)的關(guān)鍵字分別為其相應(yīng)的關(guān)鍵字分別為k0,k1,kn-1。 輸出：輸出：Ri,0

2、,Ri,1,Ri,n-1,使得使得ki,0ki,1ki,n-1 (或或ki,0ki,1ki,n-1)。本章僅考慮遞增排序本章僅考慮遞增排序 當待排序記錄的關(guān)鍵字均不相同時，排序的結(jié)果是惟一當待排序記錄的關(guān)鍵字均不相同時，排序的結(jié)果是惟一的的, ,否則排序的結(jié)果不一定唯一。如果待排序的表中否則排序的結(jié)果不一定唯一。如果待排序的表中, ,存在有存在有多個關(guān)鍵字相同的記錄多個關(guān)鍵字相同的記錄, ,經(jīng)過排序后這些具有相同關(guān)鍵字的記經(jīng)過排序后這些具有相同關(guān)鍵字的記錄之間的相對次序保持不變錄之間的相對次序保持不變, ,則稱這種排序方法是則稱這種排序方法是穩(wěn)定穩(wěn)定的；反的；反之之, ,若具有相同關(guān)鍵字的記錄

3、之間的相對次序發(fā)生變化若具有相同關(guān)鍵字的記錄之間的相對次序發(fā)生變化, ,則稱則稱這種排序方法是這種排序方法是不穩(wěn)定不穩(wěn)定的。的。 在排序過程中，若整個表都是放在內(nèi)存中處理，排序時在排序過程中，若整個表都是放在內(nèi)存中處理，排序時不涉及數(shù)據(jù)的內(nèi)、外存交換，則稱之為不涉及數(shù)據(jù)的內(nèi)、外存交換，則稱之為內(nèi)排序內(nèi)排序；反之，若排；反之，若排序過程中要進行數(shù)據(jù)的內(nèi)、外存交換，則稱之為序過程中要進行數(shù)據(jù)的內(nèi)、外存交換，則稱之為外排序外排序。 算法的穩(wěn)定性算法的穩(wěn)定性內(nèi)排序和外排序內(nèi)排序和外排序內(nèi)排序的基本方法內(nèi)排序的基本方法內(nèi)部排序的過程是一個逐步擴大記錄的有序序內(nèi)部排序的過程是一個逐步擴大記錄的有序序列長度

4、的過程。列長度的過程。經(jīng)過一趟排序經(jīng)過一趟排序有序序列區(qū)無 序 序 列 區(qū)有序序列區(qū)無 序 序 列 區(qū)正序和反序正序和反序若待排序的表中元素已按關(guān)鍵字排好序，稱此表中元素若待排序的表中元素已按關(guān)鍵字排好序，稱此表中元素為為正序正序；反之，若待排序的表中元素的關(guān)鍵字順序正好和排；反之，若待排序的表中元素的關(guān)鍵字順序正好和排好序的順序相反，稱此表中元素為好序的順序相反，稱此表中元素為反反序。序。排序的分類排序的分類根據(jù)排序算法是否基于關(guān)鍵字的比較，將排序算法分為根據(jù)排序算法是否基于關(guān)鍵字的比較，將排序算法分為基于比較的排序算法基于比較的排序算法和和不基于比較的排序算法不基于比較的排序算法。像插入排

5、序、。像插入排序、交換排序、選擇排序和歸并排序都是基于比較的排序算法；交換排序、選擇排序和歸并排序都是基于比較的排序算法；而基數(shù)排序是不基于比較的排序算法。而基數(shù)排序是不基于比較的排序算法。 待排序的順序表類型的類型定義如下：待排序的順序表類型的類型定義如下： typedef int KeyType; /定義關(guān)鍵字類型定義關(guān)鍵字類型 typedef struct /記錄類型記錄類型 KeyType key; /關(guān)鍵字項關(guān)鍵字項 InfoType data; /其他數(shù)據(jù)項其他數(shù)據(jù)項,類型為類型為InfoType RecType; /排序的記錄類型定義排序的記錄類型定義 存放數(shù)據(jù)的結(jié)構(gòu)：存放數(shù)據(jù)的

6、結(jié)構(gòu)：10.2 插入排序插入排序 插入排序的基本思想是：每次將一個待排序的記錄插入排序的基本思想是：每次將一個待排序的記錄, ,按其按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子表中的適當位置關(guān)鍵字大小插入到前面已經(jīng)排好序的子表中的適當位置, ,直到直到全部記錄插入完成為止。全部記錄插入完成為止。 兩種插入排序方法：兩種插入排序方法： （1 1）直接插入排序（含二分插入排序）直接插入排序（含二分插入排序） （2 2）希爾排序）希爾排序10.2.1 直接插入排序直接插入排序 假設(shè)待排序的記錄存放在數(shù)組假設(shè)待排序的記錄存放在數(shù)組R0.n-1中，排序過程的某中，排序過程的某一中間時刻，一中間時刻，R被劃分成

7、兩個子區(qū)間被劃分成兩個子區(qū)間R0.i-1和和Ri.n-1，其中：，其中：前一個子區(qū)間是已排好序的有序區(qū)，后一個子區(qū)間則是當前未前一個子區(qū)間是已排好序的有序區(qū)，后一個子區(qū)間則是當前未排序的部分，不妨稱其為無序區(qū)。排序的部分，不妨稱其為無序區(qū)。 直接插入排序的基本操作是將當前無序區(qū)的第直接插入排序的基本操作是將當前無序區(qū)的第1個記錄個記錄Ri插入到有序區(qū)插入到有序區(qū)R0.i-1中適當?shù)奈恢蒙希怪羞m當?shù)奈恢蒙?，使R0.i變?yōu)樾碌挠凶優(yōu)樾碌挠行騾^(qū)。這種方法通常稱為序區(qū)。這種方法通常稱為增量法增量法，因為它每次使有序區(qū)增加，因為它每次使有序區(qū)增加1個記錄。個記錄。 R0Ri-1 有序區(qū)有序區(qū) RiRn

8、-1 無序區(qū)無序區(qū) 一趟排序一趟排序 R0Ri-1 Ri Ri+1Rn-1 有序區(qū)有序區(qū) 無序區(qū)無序區(qū) R0jRij=i-1插入位置插入位置在有序區(qū)中插入在有序區(qū)中插入Ri的過程的過程void InsertSort(RecType R,int n) /對對R0.n-1按遞增有序進行直接插入排序按遞增有序進行直接插入排序 int i,j; RecType temp; for (i=1;i=0 & temp.keyj且且Ri.key=Rj.key時，本算法將時，本算法將Ri插入在插入在Rj的后面，使的后面，使Ri和和Rj的相對位置保持不變，所以直接插入的相對位置保持不變，所以直接插入排序是

9、一種排序是一種穩(wěn)定的排序方法穩(wěn)定的排序方法。 Rj Ri 有序區(qū)有序區(qū)Ri插入在插入在Rj的后面的后面10.2.2 折半折半插入排序插入排序查找采用查找采用折半折半查找方法，稱為二分插入排序或折半插入排序。查找方法，稱為二分插入排序或折半插入排序。void InsertSort1(RecType R,int n)int i,j,low,high,mid; RecType tmp; for (i=1;in;i+) tmp=Ri; /將將Ri保存到保存到tmp中中l(wèi)ow=0;high=i-1;while (low=high) /在在Rlow.high中查找插入的位置中查找插入的位置 mid=(lo

10、w+high)/2;/取中間位置取中間位置 if (tmp.key=high+1;j-)/記錄后移記錄后移 Rj+1=Rj;Rhigh+1=tmp;/插入插入 折半插入排序的元素移動次數(shù)與直接插入排序相同，不折半插入排序的元素移動次數(shù)與直接插入排序相同，不同的僅是變分散移動為集合移動。在同的僅是變分散移動為集合移動。在R0.i-1中查找插入中查找插入Ri的位置，折半查找的平均關(guān)鍵字比較次數(shù)為的位置，折半查找的平均關(guān)鍵字比較次數(shù)為log2(i+1)-1，平均，平均移動元素的次數(shù)為移動元素的次數(shù)為i/2+2，所以平均時間復雜度為：，所以平均時間復雜度為：)()221) 1(log(2112nOii

11、ni就平均性能而言，折半查找優(yōu)于順序查找，所以折就平均性能而言，折半查找優(yōu)于順序查找，所以折半插入排序也優(yōu)于直接插入排序。折半插入排序的空間半插入排序也優(yōu)于直接插入排序。折半插入排序的空間復雜度為復雜度為O(1)。10.2.3 希爾排序希爾排序 希爾排序也是一種插入排序方法希爾排序也是一種插入排序方法,實際上是一種分組插入方實際上是一種分組插入方法。法。 基本思想：基本思想： 先取定一個小于先取定一個小于n的整數(shù)的整數(shù)d1作為第一個增量，把表的全部記作為第一個增量，把表的全部記錄分成錄分成d1個組，所有距離為個組，所有距離為d1的倍數(shù)的記錄放在同一個組中，的倍數(shù)的記錄放在同一個組中，在各組內(nèi)進

12、行直接插入排序；在各組內(nèi)進行直接插入排序； 然后取第二個增量然后取第二個增量d2（d1），重復上述的分組和排序，），重復上述的分組和排序，直至所取的增量直至所取的增量dt=1（dtdt-1d20) for (i=gap;i=0 & tmp.keyRj.key) Rj+gap=Rj;j=j-gap; Rj+gap=tmp;gap=gap/2;/減小增量減小增量 例例10.2 設(shè)待排序的表有設(shè)待排序的表有10個記錄個記錄,其關(guān)鍵字分別為其關(guān)鍵字分別為9,8,7,6,5,4,3,2,1,0。說明采用希爾排序方法進行排序的過程。說明采用希爾排序方法進行排序的過程。 9 8 7 6 5 4 3

13、2 1 0 初初始始狀狀態(tài)態(tài) (連連線線部部分分為為下下一一趟趟作作準準備備) 4 3 2 1 0 9 8 7 6 5 d=5 (d=5 執(zhí)執(zhí)行行結(jié)結(jié)果果) 0 1 2 3 4 5 6 7 8 9 d=2 (d=2 執(zhí)執(zhí)行行結(jié)結(jié)果果) 0 1 2 3 4 5 6 7 8 9 d=1 (d=1 執(zhí)執(zhí)行行結(jié)結(jié)果果) 希爾排序的時間復雜度約為希爾排序的時間復雜度約為O(n1.3)。為什么希爾排序比直接插入排序好？為什么希爾排序比直接插入排序好？例如：有例如：有10個元素要排序。個元素要排序。希爾排序希爾排序直接插入排序直接插入排序大約時間大約時間=102=100d=5：分為：分為5組，時間約為組，時

14、間約為5*2220d=2：分為：分為2組，時間約為組，時間約為2*5250d=1：分為：分為1組，幾乎有序，時間約為組，幾乎有序，時間約為1080希爾排序算法不穩(wěn)定的反例希爾排序算法不穩(wěn)定的反例希爾排序法是一種不穩(wěn)定的排序算法。希爾排序法是一種不穩(wěn)定的排序算法。例如，若希爾排序分為兩組：例如，若希爾排序分為兩組：3,10,7,8,20和和5,8,2,1,6，顯，顯然，第然，第1組的組的8排列在第排列在第2組的組的8的后面，兩組采用直接插入排序的后面，兩組采用直接插入排序后的結(jié)果為：后的結(jié)果為：3,7,8,10,20和和1,2,5,6,8，這樣第，這樣第1組的組的8排列到第排列到第2組的組的8的

15、前面，它們的相對位置發(fā)生了改變。的前面，它們的相對位置發(fā)生了改變。思考題：思考題：希爾排序中的有序區(qū)是全局有序嗎？希爾排序中的有序區(qū)是全局有序嗎？10.3 交換排序交換排序 交換排序的基本思想：兩兩比較待排序記錄的關(guān)鍵字交換排序的基本思想：兩兩比較待排序記錄的關(guān)鍵字,發(fā)現(xiàn)兩個記錄的次序相反時即進行交換發(fā)現(xiàn)兩個記錄的次序相反時即進行交換,直到?jīng)]有反序的記直到?jīng)]有反序的記錄為止。錄為止。 兩種交換排序兩種交換排序: （1）冒泡排序）冒泡排序 （2）快速排序）快速排序10.3.1 冒泡排序冒泡排序 冒泡排序的基本思想冒泡排序的基本思想：通過無序區(qū)中相鄰記錄關(guān)鍵字間的：通過無序區(qū)中相鄰記錄關(guān)鍵字間的比

16、較和位置的交換，使關(guān)鍵字最小的記錄如氣泡一般逐漸往比較和位置的交換，使關(guān)鍵字最小的記錄如氣泡一般逐漸往上上“漂浮漂浮”直至直至“水面水面”。 整個算法是從最下面的記錄開始，對每兩個相鄰的關(guān)鍵字整個算法是從最下面的記錄開始，對每兩個相鄰的關(guān)鍵字進行比較進行比較,且使關(guān)鍵字較小的記錄換至關(guān)鍵字較大的記錄之上，且使關(guān)鍵字較小的記錄換至關(guān)鍵字較大的記錄之上，使得經(jīng)過一趟冒泡排序后，關(guān)鍵字最小的記錄到達最上端，使得經(jīng)過一趟冒泡排序后，關(guān)鍵字最小的記錄到達最上端，接著再在剩下的記錄中找關(guān)鍵字次小的記錄，并把它換在第接著再在剩下的記錄中找關(guān)鍵字次小的記錄，并把它換在第二個位置上。依次類推，一直到所有記錄都有

17、序為止。二個位置上。依次類推，一直到所有記錄都有序為止。 一趟排序一趟排序 R0 有序區(qū)有序區(qū) 無序區(qū)無序區(qū) Ri-1 Ri Rn-1 Ri+1 R0 Ri Ri-1 將無序區(qū)中將無序區(qū)中最小記錄放最小記錄放在在 Ri Ri+1 Rn-1 有序區(qū)有序區(qū) 無序區(qū)無序區(qū) void BubbleSort(RecType R,int n) int i,j; RecType temp; for (i=0;ii;j-) /比較找本趟最小關(guān)鍵字的記錄比較找本趟最小關(guān)鍵字的記錄 if (Rj.keyRj-1.key) temp=Rj; /Rj與與Rj-1進行交換進行交換 Rj=Rj-1; Rj-1=temp;

18、 全局有序區(qū)全局有序區(qū) Ri Rn-1用交換找最小記錄放到用交換找最小記錄放到Ri處處 例例10.3 設(shè)待排序的表有設(shè)待排序的表有10個記錄個記錄,其關(guān)鍵字分別為其關(guān)鍵字分別為9,8,7,6,5,4,3,2,1,0。說明采用冒泡排序方法進行排序的過程。說明采用冒泡排序方法進行排序的過程。 初始關(guān)鍵字初始關(guān)鍵字 9 8 7 6 5 4 3 2 1 0 i=0 0 9 8 7 6 5 4 3 2 1 i=1 0 1 9 8 7 6 5 4 3 2 i=2 0 1 2 9 8 7 6 5 4 3 i=3 0 1 2 3 9 8 7 6 5 4 i=4 0 1 2 3 4 9 8 7 6 5 i=5

19、0 1 2 3 4 5 9 8 7 6 i=6 0 1 2 3 4 5 6 9 8 7 i=7 0 1 2 3 4 5 6 7 9 8 i=8 0 1 2 3 4 5 6 7 8 9 思考題：思考題：冒泡冒泡排序中的有序區(qū)是全局有序嗎？排序中的有序區(qū)是全局有序嗎？ 在有些情況下，在第在有些情況下，在第i（in-1）趟時已排好序了，）趟時已排好序了，但仍執(zhí)行后面幾趟的比較。實際上，一旦算法中某一趟但仍執(zhí)行后面幾趟的比較。實際上，一旦算法中某一趟比較時不出現(xiàn)記錄交換，說明已排好序了，就可以結(jié)束比較時不出現(xiàn)記錄交換，說明已排好序了，就可以結(jié)束本算法。本算法。 為此得到改進冒泡排序算法如下：為此得到改

20、進冒泡排序算法如下：void BubbleSort(RecType R,int n) int i,j; bool exchange;RecType temp; for (i=0;ii;j-)/比較比較,找出最小關(guān)鍵字的記錄找出最小關(guān)鍵字的記錄 if (Rj.keyRj-1.key) temp=Rj; Rj=Rj-1;Rj-1=temp; exchange=true; if (exchange=false) return; /中途結(jié)束算法中途結(jié)束算法 最好的情況（關(guān)鍵字在記錄序列中順序有序）：最好的情況（關(guān)鍵字在記錄序列中順序有序）： 只需進行一趟冒泡只需進行一趟冒泡“比較比較”的次數(shù)：的次數(shù)：

21、最壞的情況（關(guān)鍵字在記錄序列中逆序有序）：最壞的情況（關(guān)鍵字在記錄序列中逆序有序）： 需進行需進行n-1趟冒泡趟冒泡“比較比較”的次數(shù)：的次數(shù)：0“移動移動”的次數(shù)：的次數(shù)：“移動移動”的次數(shù)：的次數(shù)：n-121110)n(n)in(ni 2131320)n(n)in(ni 10.3.2 快速排序快速排序 快速排序是由冒泡排序改進而得的?？焖倥判蚴怯擅芭菖判蚋倪M而得的。 基本思想基本思想：在待排序的：在待排序的n n個記錄中任取一個記錄（通常取個記錄中任取一個記錄（通常取第一個記錄），把該記錄放入適當位置后第一個記錄），把該記錄放入適當位置后, ,數(shù)據(jù)序列被此記錄數(shù)據(jù)序列被此記錄劃分成兩部分。

22、所有關(guān)鍵字比該記錄關(guān)鍵字小的記錄放置在前劃分成兩部分。所有關(guān)鍵字比該記錄關(guān)鍵字小的記錄放置在前一部分一部分, ,所有比它大的記錄放置在后一部分所有比它大的記錄放置在后一部分, ,并把該記錄排在這并把該記錄排在這兩部分的中間兩部分的中間( (稱為該記錄歸位稱為該記錄歸位) )，這個過程稱作一趟快速排序。，這個過程稱作一趟快速排序。 首先對無序的記錄序列進行首先對無序的記錄序列進行“一次劃分一次劃分”，之后分別對分割，之后分別對分割所得兩個子序列所得兩個子序列“遞歸遞歸”進行快速排序。進行快速排序。無 序 的 記 錄 序 列無序記錄子序列(1)無序子序列(2)基準基準一次劃分分別進行快速排序需要確

23、定排序的序列，采用什么存儲結(jié)構(gòu)？需要確定排序的序列，采用什么存儲結(jié)構(gòu)？52 49 80 36 14 58 61 97 23 75stlowhigh設(shè)設(shè) Rs=52 為樞軸為樞軸 將將 Rhigh.key 和基準的關(guān)鍵字進行比較，要求和基準的關(guān)鍵字進行比較，要求Rhigh.key 基準的關(guān)鍵字基準的關(guān)鍵字 將將 Rlow.key 和基準的關(guān)鍵字進行比較，要求和基準的關(guān)鍵字進行比較，要求Rlow.key 基基準的關(guān)鍵字準的關(guān)鍵字high23low80high14low52例如例如R052lowhighhighhighlow 可見，經(jīng)過可見，經(jīng)過“一次劃分一次劃分” ，將關(guān)鍵字序列，將關(guān)鍵字序列 5

24、2, 49, 80, 36, 14, 58, 61, 97, 23, 75 調(diào)整為調(diào)整為: 23, 49, 14, 36, (52) 58, 61, 97, 80, 75 在調(diào)整過程中，設(shè)立了兩個指針：在調(diào)整過程中，設(shè)立了兩個指針： low 和和high，它們的初值，它們的初值分別為：分別為： s 和和 t。 之后逐漸減小之后逐漸減小 high，增加，增加 low，并保證，并保證 Rhigh.key52，和，和 Rlow.key52, ,否則進行記錄的否則進行記錄的“交交換換”。 以后對所有的兩部分分別重復上述過程，直至每部分以后對所有的兩部分分別重復上述過程，直至每部分內(nèi)只有一個記錄為止。內(nèi)

25、只有一個記錄為止。簡而言之，每趟使表的簡而言之，每趟使表的第一個元素第一個元素放入適當位置，將放入適當位置，將表一分為二，對子表按遞歸方式繼續(xù)這種劃分，直至劃分表一分為二，對子表按遞歸方式繼續(xù)這種劃分，直至劃分的子表長為的子表長為1。void QuickSort(RecType R,int s,int t) /對對Rs至至Rt的元素進行快速排序的元素進行快速排序 int i=s,j=t;RecType temp; if (si & Rj.keytemp.key) j-; Ri=Rj; while (ij & Ri.keytemp.key) i+; Rj=Ri; Ri=temp;

26、 QuickSort(R,s,i-1); /對左區(qū)間遞歸排序?qū)ψ髤^(qū)間遞歸排序 QuickSort(R,i+1,t); /對右區(qū)間遞歸排序?qū)τ覅^(qū)間遞歸排序 劃分劃分 例例10.4 設(shè)待排序的表有設(shè)待排序的表有10個記錄個記錄,其關(guān)鍵字分別為其關(guān)鍵字分別為6,8,7,9,0,1,3,2,4,5。說明采用快速排序方法進行排序的過程。說明采用快速排序方法進行排序的過程。 6 8 7 9 0 1 3 2 4 5 5 4 2 3 0 1 6 9 7 8 (a) 第 1 次劃分 6 8 7 9 0 1 3 2 4 5 5 4 2 3 0 1 6 9 7 8 (b) 第 2 次劃分 1 4 2 3 0 5 6

27、 8 7 9 0 1 3 2 4 5 5 4 2 3 0 1 6 9 7 8 1 4 2 3 0 5 0 1 2 3 4 6 8 7 9 0 1 3 2 4 5 5 4 2 3 0 1 6 9 7 8 1 4 2 3 0 5 0 1 2 3 4 2 3 4 (c) 第 3 次劃分 (d) 第 4 次劃分 6 8 7 9 0 1 3 2 4 5 5 4 2 3 0 1 6 9 7 8 1 4 2 3 0 5 0 1 2 3 4 2 3 4 (e) 第 5 次劃分 3 4 6 8 7 9 0 1 3 2 4 5 5 4 2 3 0 1 6 9 7 8 1 4 2 3 0 5 0 1 2 3 4 2

28、 3 4 (f) 第 6 次劃分 3 4 8 7 9 6 8 7 9 0 1 3 2 4 5 5 4 2 3 0 1 6 9 7 8 1 4 2 3 0 5 0 1 2 3 4 2 3 4 (g) 第 7 次劃分 3 4 8 7 9 7 8 nkavgavgavgknTkTnCnnT1)() 1(1)(則可得結(jié)果：則可得結(jié)果：結(jié)論結(jié)論: 快速排序的時間復雜度為快速排序的時間復雜度為O(nlog2n)由此可得快速排序所需時間的平均值為：由此可得快速排序所需時間的平均值為：平均所需?？臻g為平均所需?？臻g為O(log2n)。nk-1n-k1次劃分的時間次劃分的時間Tavg(n)=Cnlog2n。10

29、.4 選擇排序選擇排序 選擇排序的基本思想是：每一趟從待排序的記錄中選出關(guān)選擇排序的基本思想是：每一趟從待排序的記錄中選出關(guān)鍵字最小的記錄，順序放在已排好序的子表的最后，直到全鍵字最小的記錄，順序放在已排好序的子表的最后，直到全部記錄排序完畢。部記錄排序完畢。 兩種選擇排序方法：兩種選擇排序方法： （1）簡單選擇排序（或稱直接選擇排序）簡單選擇排序（或稱直接選擇排序） （2）堆排序）堆排序10.4.1 直接選擇排序直接選擇排序基本思想：第基本思想：第i趟排序開始時趟排序開始時,當前有序區(qū)和無序區(qū)分別為當前有序區(qū)和無序區(qū)分別為R0.i-1和和Ri.n-1（0in-1），該趟排序則是從當前無序區(qū)）

30、，該趟排序則是從當前無序區(qū)中選出關(guān)鍵字最小的記錄中選出關(guān)鍵字最小的記錄Rk，將它與無序區(qū)的第，將它與無序區(qū)的第1個記錄個記錄Ri交換，使交換，使R0.i和和Ri+1.n-1分別變?yōu)樾碌挠行騾^(qū)和新的無序分別變?yōu)樾碌挠行騾^(qū)和新的無序區(qū)。區(qū)。 假設(shè)排序過程中，待排記錄序列的狀態(tài)為：假設(shè)排序過程中，待排記錄序列的狀態(tài)為：有序序列有序序列R0.i-1無序序列無序序列 Ri.n-1 第第 i 趟趟簡單選擇排序簡單選擇排序從中選出關(guān)鍵字最從中選出關(guān)鍵字最小的記錄小的記錄有序序列有序序列R0.i-1無序序列無序序列 Ri+1.n-1void SelectSort(RecType R,int n) int i,

31、j,k; RecType temp; for (i=0;in-1;i+) /做第做第i趟排序趟排序 k=i;for (j=i+1;jn;j+) /在在i.n-1中選中選key最小的最小的Rk if (Rj.keyRk.key) k=j; /k記下的最小關(guān)鍵字所在的位置記下的最小關(guān)鍵字所在的位置if (k!=i) /交換交換Ri和和Rk temp=Ri; Ri=Rk; Rk=temp; 全局有序區(qū)全局有序區(qū) Ri Rn-1用選擇找最小記錄放到用選擇找最小記錄放到Ri處處 例例10.5 設(shè)待排序的表有設(shè)待排序的表有10個記錄，其關(guān)鍵字分別為個記錄，其關(guān)鍵字分別為6,8,7,9,0,1,3,2,4,

32、5。說明采用直接選擇排序方法進行排序的過。說明采用直接選擇排序方法進行排序的過程。程。 初始關(guān)鍵字初始關(guān)鍵字 6 8 7 9 0 1 3 2 4 5 i=0 0 8 7 9 6 1 3 2 4 5 i=1 0 1 7 9 6 8 3 2 4 5 i=2 0 1 2 9 6 8 3 7 4 5 i=3 0 1 2 3 6 8 9 7 4 5 i=4 0 1 2 3 4 8 9 7 6 5 i=5 0 1 2 3 4 5 9 7 6 8 i=6 0 1 2 3 4 5 6 7 9 8 i=7 0 1 2 3 4 5 6 7 9 8 i=8 0 1 2 3 4 5 6 7 8 9 對對 n 個記錄進

33、行簡單選擇排序，所需進行的個記錄進行簡單選擇排序，所需進行的 關(guān)鍵字間關(guān)鍵字間的比較次數(shù)的比較次數(shù) 總計為：總計為：移動記錄的次數(shù)，最小值為移動記錄的次數(shù)，最小值為 0, 最大值為最大值為3(n-1) 。21120)n(n)in(ni 10.4.2 堆排序堆排序 堆排序是一樹形選擇排序，它的特點是，在排序過程中，堆排序是一樹形選擇排序，它的特點是，在排序過程中，將將R1.n看成是一棵看成是一棵完全二叉樹完全二叉樹的順序存儲結(jié)構(gòu)，利用完全二叉的順序存儲結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點和孩子結(jié)點之間的內(nèi)在關(guān)系，在當前無序區(qū)中選擇樹中雙親結(jié)點和孩子結(jié)點之間的內(nèi)在關(guān)系，在當前無序區(qū)中選擇關(guān)鍵字最大（或最

34、小）的記錄。關(guān)鍵字最大（或最小）的記錄。 堆的定義是：堆的定義是：n個關(guān)鍵字序列個關(guān)鍵字序列K1,K2,Kn稱為稱為堆堆,當且僅當該當且僅當該序列滿足如下性質(zhì)（簡稱為堆性質(zhì)）：序列滿足如下性質(zhì)（簡稱為堆性質(zhì)）： （1）KiK2i 且且 KiK2i+1 或或 （2）KiK2i 且且 KiK2i+1（1i n/2 ） 滿足第（滿足第（1）種情況的堆稱為小根堆，滿足第（）種情況的堆稱為小根堆，滿足第（2）種情況的）種情況的堆稱為大根堆。下面討論的堆是大根堆。堆稱為大根堆。下面討論的堆是大根堆。12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49是小根堆是小根堆例如例如

35、:12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49不是堆不是堆rir2i r2i+1 若將該數(shù)列視作完全二叉樹，則若將該數(shù)列視作完全二叉樹，則 r2i 是是 ri 的左孩子；的左孩子； r2i+1 是是 ri 的右孩子。的右孩子。1236276549817355403498例如例如:是堆是堆14不不 堆排序的關(guān)鍵是構(gòu)造堆堆排序的關(guān)鍵是構(gòu)造堆,這里采用篩選算法建堆。這里采用篩選算法建堆。 所謂所謂“篩選篩選”指的是，對一棵左指的是，對一棵左/右子樹均為堆的完全二右子樹均為堆的完全二叉樹，叉樹，“調(diào)整調(diào)整”根結(jié)點使整個二叉樹也成為一個堆。根結(jié)點使整個二叉樹也成為

36、一個堆。堆堆篩選篩選堆堆98814973556412362740例如例如:是大根堆是大根堆12但在但在 98 和和 12 進行互換之后，它就不是堆了，進行互換之后，它就不是堆了，因此，需要對它進行因此，需要對它進行“篩選篩選”。98128173641298比較比較比較比較void sift(RecType R,int low,int high) /調(diào)整堆的算法調(diào)整堆的算法 int i=low,j=2*i; /Rj是是Ri的左孩子的左孩子 RecType temp=Ri; while (j=high) if (jhigh & Rj.keyRj+1.key) j+; if (temp.ke

37、y=1;i-) /循環(huán)建立初始堆循環(huán)建立初始堆 sift(R,i,n); for (i=n;i=2;i-) /進行進行n-1次循環(huán)次循環(huán),完成推排序完成推排序 temp=R1; /將第一個元素同當前區(qū)間內(nèi)將第一個元素同當前區(qū)間內(nèi)R1對換對換 R1=Ri;Ri=temp; sift(R,1,i-1); /篩選篩選R1結(jié)點結(jié)點,得到得到i-1個結(jié)點的堆個結(jié)點的堆 例例10.6 設(shè)待排序的表有設(shè)待排序的表有10個記錄，其關(guān)鍵字分別為個記錄，其關(guān)鍵字分別為6,8,7,9,0,1,3,2,4,5。說明采用堆排序方法進行排序的過程。說明采用堆排序方法進行排序的過程。 6 8 7 9 0 2 4 1 3 5

38、 9 8 7 6 5 2 4 1 3 0 (a) 初始狀態(tài)初始狀態(tài) (b) 建立的初始堆建立的初始堆 0 8 7 6 5 2 4 1 3 8 6 7 4 5 2 0 1 3 (a) 交換交換 9 與與 0，輸出，輸出 9 (b) 篩選調(diào)整篩選調(diào)整 0 6 7 4 5 2 1 3 (c) 交換交換 8 與與 0，輸出，輸出 8 7 6 3 4 5 2 1 0 2 6 3 4 5 1 0 (d) 篩選調(diào)整篩選調(diào)整 (e) 交換交換 7 與與 2，輸出，輸出 7 6 5 3 4 2 1 0 (f) 篩選調(diào)整篩選調(diào)整 堆排序過程：堆排序過程： 0 5 3 4 2 1 5 4 3 0 2 1 (g) 交

39、換交換 6 與與 0，輸出，輸出 6 (h) 篩選調(diào)整篩選調(diào)整 (i) 交換交換 5 與與 1，輸出，輸出 5 1 4 3 0 2 4 2 3 0 1 (j) 篩選調(diào)整篩選調(diào)整 1 2 3 2 3 2 0 (k) 交換交換 4 與與 1，輸出，輸出 4 (l) 篩選調(diào)整篩選調(diào)整 (m) 交換交換 3 與與 1，輸出，輸出 3 0 2 1 2 0 1 (n) 篩選調(diào)整篩選調(diào)整 1 1 0 1 0 (o) 交換交換 2 與與 1，輸出，輸出 2 (p) 篩選調(diào)整篩選調(diào)整 (q) 交換交換 1 與與 0，輸出，輸出 1 0 1 0 (r) 輸出輸出 0 堆排序的時間復雜度分析：堆排序的時間復雜度分析

40、：1. 對深度為對深度為 k 的堆，的堆，“篩選篩選”所需進行的關(guān)鍵字所需進行的關(guān)鍵字比較的次數(shù)至多為比較的次數(shù)至多為2(k-1)；3. 調(diào)整調(diào)整“堆頂堆頂” n-1 次，總共進行的關(guān)鍵次，總共進行的關(guān)鍵 字比較的次數(shù)不超過字比較的次數(shù)不超過 2 ( log2(n-1) + log2(n-2) + +log22) 2n( log2n ) 因此，堆排序的時間復雜度為因此，堆排序的時間復雜度為O(nlogn)。思考題：思考題：選擇排序中的有序區(qū)是全局有序嗎？選擇排序中的有序區(qū)是全局有序嗎？10.5 歸并排序歸并排序 歸并排序是多次將兩個或兩個以上的有序表合并成一個歸并排序是多次將兩個或兩個以上的有

41、序表合并成一個新的有序表。最簡單的歸并是直接將兩個有序的子表合并成新的有序表。最簡單的歸并是直接將兩個有序的子表合并成一個有序的表。一個有序的表。 在內(nèi)部排序中，通常采用的是在內(nèi)部排序中，通常采用的是2-路歸并排序。即：將路歸并排序。即：將兩個位置相鄰的記錄有序子序列。兩個位置相鄰的記錄有序子序列。歸并為一個記錄的有序序列。歸并為一個記錄的有序序列。有有 序序 序序 列列 Rl.n有序子序列有序子序列 Rl.m有序子序列有序子序列 Rm+1.n這個操作對順序表而言，是輕而易舉的。這個操作對順序表而言，是輕而易舉的。void Merge(RecType R,int low,int mid,int

42、 high) RecType *R1; int i=low,j=mid+1,k=0; /k是是R1的下標的下標,i、j分別為第分別為第1、2段的下標段的下標 R1=(RecType *)malloc(high-low+1)*sizeof(RecType); while (i=mid & j=high) if (Ri.key=Rj.key) /將第將第1段中的記錄放入段中的記錄放入R1中中 R1k=Ri; i+;k+; else /將第將第2段中的記錄放入段中的記錄放入R1中中 R1k=Rj; j+;k+; Merge()實現(xiàn)了一次歸并實現(xiàn)了一次歸并 :空間復雜度空間復雜度為為O(hig

43、h-low+1)while (i=mid) /將第將第1段余下部分復制到段余下部分復制到R1 R1k=Ri; i+;k+; while (j=high) /將第將第2段余下部分復制到段余下部分復制到R1 R1k=Rj; j+;k+; for (k=0,i=low;i=high;k+,i+) /將將R1復制回復制回R中中 Ri=R1k; free(R1); void MergePass(RecType R,int length,int n) int i; for (i=0;i+2*length-1n;i=i+2*length) /歸并歸并length長的兩相鄰子表長的兩相鄰子表 Merge(R,

44、i,i+length-1,i+2*length-1); if (i+length-1n) /余下兩個子表余下兩個子表,后者長度小于后者長度小于length Merge(R,i,i+length-1,n-1); /歸并這兩個子表歸并這兩個子表MergePass()實現(xiàn)了一趟歸并實現(xiàn)了一趟歸并 二路歸并排序算法如下：二路歸并排序算法如下：void MergeSort(RecType R,int n) int length; for (length=1;length=0;i-) /從低位到高位做從低位到高位做d趟排序趟排序 /123以以“321”存儲存儲 for (j=0;jdatai-0; /找第

45、找第k個鏈隊個鏈隊 if (headk=NULL) /進行分配進行分配,即采用尾插法建立單鏈表即采用尾插法建立單鏈表 headk=p; tailk=p; else tailk-next=p; tailk=p; p=p-next; /取下一個待排序的元素取下一個待排序的元素 分分配配 p=NULL; for (j=0;jnext=headj; t=tailj; t-next=NULL; /最后一個結(jié)點的最后一個結(jié)點的next域置域置NULL 收收集集排序完成后，排序完成后，p指向的是一個有序單鏈表指向的是一個有序單鏈表 例例10.8 設(shè)待排序的表有設(shè)待排序的表有10個記錄，其關(guān)鍵字分別為個記錄，其關(guān)鍵字分別為75,23,98,44,57,12,29,64,38,82。說明采用基數(shù)排序方法進行。說明采用基數(shù)排序方