第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個(gè)記錄個(gè)記錄,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)。本章僅考慮遞增排序本章僅考慮遞增排序 當(dāng)待排序記錄的關(guān)鍵字均不相同時(shí)，排序的結(jié)果是惟一當(dāng)待排序記錄的關(guān)鍵字均不相同時(shí)，排序的結(jié)果是惟一的的, ,否則排序的結(jié)果不一定唯一。如果待排序的表中否則排序的結(jié)果不一定唯一。如果待排序的表中, ,存在有存在有多個(gè)關(guān)鍵字相同的記錄多個(gè)關(guān)鍵字相同的記錄, ,經(jīng)過(guò)排序后這些具有相同關(guān)鍵字的記經(jīng)過(guò)排序后這些具有相同關(guān)鍵字的記錄之間的相對(duì)次序保持不變錄之間的相對(duì)次序保持不變, ,則稱這種排序方法是則稱這種排序方法是穩(wěn)定穩(wěn)定的；反的；反之之, ,若具有相同關(guān)鍵字的記錄

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

4、的過(guò)程。列長(zhǎng)度的過(guò)程。經(jīng)過(guò)一趟排序經(jīng)過(guò)一趟排序有序序列區(qū)無(wú) 序 序 列 區(qū)有序序列區(qū)無(wú) 序 序 列 區(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)鍵字項(xiàng)關(guān)鍵字項(xiàng) InfoType data; /其他數(shù)據(jù)項(xiàng)其他數(shù)據(jù)項(xiàng),類型為類型為InfoType RecType; /排序的記錄類型定義排序的記錄類型定義 存放數(shù)據(jù)的結(jié)構(gòu)：存放數(shù)據(jù)的

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

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

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

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;/插入插入 折半插入排序的元素移動(dòng)次數(shù)與直接插入排序相同，不折半插入排序的元素移動(dòng)次數(shù)與直接插入排序相同，不同的僅是變分散移動(dòng)為集合移動(dòng)。在同的僅是變分散移動(dòng)為集合移動(dòng)。在R0.i-1中查找插入中查找插入Ri的位置，折半查找的平均關(guān)鍵字比較次數(shù)為的位置，折半查找的平均關(guān)鍵字比較次數(shù)為log2(i+1)-1，平均，平均移動(dòng)元素的次數(shù)為移動(dòng)元素的次數(shù)為i/2+2，所以平均時(shí)間復(fù)雜度為：，所以平均時(shí)間復(fù)雜度為：)()221) 1(log(2112nOii

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

12、行直接插入排序；在各組內(nèi)進(jìn)行直接插入排序； 然后取第二個(gè)增量然后取第二個(gè)增量d2（d1），重復(fù)上述的分組和排序，），重復(fù)上述的分組和排序，直至所取的增量直至所取的增量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個(gè)記錄個(gè)記錄,其關(guān)鍵字分別為其關(guān)鍵字分別為9,8,7,6,5,4,3,2,1,0。說(shuō)明采用希爾排序方法進(jìn)行排序的過(guò)程。說(shuō)明采用希爾排序方法進(jìn)行排序的過(guò)程。 9 8 7 6 5 4 3

13、2 1 0 初初始始狀狀態(tài)態(tài) (連連線線部部分分為為下下一一趟趟作作準(zhǔn)準(zhǔn)備備) 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é)果果) 希爾排序的時(shí)間復(fù)雜度約為希爾排序的時(shí)間復(fù)雜度約為O(n1.3)。為什么希爾排序比直接插入排序好？為什么希爾排序比直接插入排序好？例如：有例如：有10個(gè)元素要排序。個(gè)元素要排序。希爾排序希爾排序直接插入排序直接插入排序大約時(shí)間大約時(shí)間=102=100d=5：分為：分為5組，時(shí)間約為組，時(shí)

14、間約為5*2220d=2：分為：分為2組，時(shí)間約為組，時(shí)間約為2*5250d=1：分為：分為1組，幾乎有序，時(shí)間約為組，幾乎有序，時(shí)間約為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、前面，它們的相對(duì)位置發(fā)生了改變。的前面，它們的相對(duì)位置發(fā)生了改變。思考題：思考題：希爾排序中的有序區(qū)是全局有序嗎？希爾排序中的有序區(qū)是全局有序嗎？10.3 交換排序交換排序 交換排序的基本思想：兩兩比較待排序記錄的關(guān)鍵字交換排序的基本思想：兩兩比較待排序記錄的關(guān)鍵字,發(fā)現(xiàn)兩個(gè)記錄的次序相反時(shí)即進(jìn)行交換發(fā)現(xiàn)兩個(gè)記錄的次序相反時(shí)即進(jìn)行交換,直到?jīng)]有反序的記直到?jīng)]有反序的記錄為止。錄為止。 兩種交換排序兩種交換排序: （1）冒泡排序）冒泡排序 （2）快速排序）快速排序10.3.1 冒泡排序冒泡排序 冒泡排序的基本思想冒泡排序的基本思想：通過(guò)無(wú)序區(qū)中相鄰記錄關(guān)鍵字間的：通過(guò)無(wú)序區(qū)中相鄰記錄關(guān)鍵字間的比

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

17、序?yàn)橹?。二個(gè)位置上。依次類推，一直到所有記錄都有序?yàn)橹埂?一趟排序一趟排序 R0 有序區(qū)有序區(qū) 無(wú)序區(qū)無(wú)序區(qū) Ri-1 Ri Rn-1 Ri+1 R0 Ri Ri-1 將無(wú)序區(qū)中將無(wú)序區(qū)中最小記錄放最小記錄放在在 Ri Ri+1 Rn-1 有序區(qū)有序區(qū) 無(wú)序區(qū)無(wú)序區(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進(jìn)行交換進(jìn)行交換 Rj=Rj-1; Rj-1=temp;

18、 全局有序區(qū)全局有序區(qū) Ri Rn-1用交換找最小記錄放到用交換找最小記錄放到Ri處處 例例10.3 設(shè)待排序的表有設(shè)待排序的表有10個(gè)記錄個(gè)記錄,其關(guān)鍵字分別為其關(guān)鍵字分別為9,8,7,6,5,4,3,2,1,0。說(shuō)明采用冒泡排序方法進(jìn)行排序的過(guò)程。說(shuō)明采用冒泡排序方法進(jìn)行排序的過(guò)程。 初始關(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）趟時(shí)已排好序了，）趟時(shí)已排好序了，但仍執(zhí)行后面幾趟的比較。實(shí)際上，一旦算法中某一趟但仍執(zhí)行后面幾趟的比較。實(shí)際上，一旦算法中某一趟比較時(shí)不出現(xiàn)記錄交換，說(shuō)明已排好序了，就可以結(jié)束比較時(shí)不出現(xiàn)記錄交換，說(shuō)明已排好序了，就可以結(jié)束本算法。本算法。 為此得到改進(jìn)冒泡排序算法如下：為此得到改

20、進(jìn)冒泡排序算法如下：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)鍵字在記錄序列中順序有序）： 只需進(jìn)行一趟冒泡只需進(jìn)行一趟冒泡“比較比較”的次數(shù)：的次數(shù)：

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

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

23、定排序的序列，采用什么存儲(chǔ)結(jié)構(gòu)？需要確定排序的序列，采用什么存儲(chǔ)結(jié)構(gòu)？52 49 80 36 14 58 61 97 23 75stlowhigh設(shè)設(shè) Rs=52 為樞軸為樞軸 將將 Rhigh.key 和基準(zhǔn)的關(guān)鍵字進(jìn)行比較，要求和基準(zhǔn)的關(guān)鍵字進(jìn)行比較，要求Rhigh.key 基準(zhǔn)的關(guān)鍵字基準(zhǔn)的關(guān)鍵字 將將 Rlow.key 和基準(zhǔn)的關(guān)鍵字進(jìn)行比較，要求和基準(zhǔn)的關(guān)鍵字進(jìn)行比較，要求Rlow.key 基基準(zhǔn)的關(guān)鍵字準(zhǔn)的關(guān)鍵字high23low80high14low52例如例如R052lowhighhighhighlow 可見(jiàn)，經(jīng)過(guò)可見(jiàn)，經(jīng)過(guò)“一次劃分一次劃分” ，將關(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)整過(guò)程中，設(shè)立了兩個(gè)指針：在調(diào)整過(guò)程中，設(shè)立了兩個(gè)指針： low 和和high，它們的初值，它們的初值分別為：分別為： s 和和 t。 之后逐漸減小之后逐漸減小 high，增加，增加 low，并保證，并保證 Rhigh.key52，和，和 Rlow.key52, ,否則進(jìn)行記錄的否則進(jìn)行記錄的“交交換換”。 以后對(duì)所有的兩部分分別重復(fù)上述過(guò)程，直至每部分以后對(duì)所有的兩部分分別重復(fù)上述過(guò)程，直至每部分內(nèi)只有一個(gè)記錄為止。內(nèi)

25、只有一個(gè)記錄為止。簡(jiǎn)而言之，每趟使表的簡(jiǎn)而言之，每趟使表的第一個(gè)元素第一個(gè)元素放入適當(dāng)位置，將放入適當(dāng)位置，將表一分為二，對(duì)子表按遞歸方式繼續(xù)這種劃分，直至劃分表一分為二，對(duì)子表按遞歸方式繼續(xù)這種劃分，直至劃分的子表長(zhǎng)為的子表長(zhǎng)為1。void QuickSort(RecType R,int s,int t) /對(duì)對(duì)Rs至至Rt的元素進(jìn)行快速排序的元素進(jìn)行快速排序 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); /對(duì)左區(qū)間遞歸排序?qū)ψ髤^(qū)間遞歸排序 QuickSort(R,i+1,t); /對(duì)右區(qū)間遞歸排序?qū)τ覅^(qū)間遞歸排序 劃分劃分 例例10.4 設(shè)待排序的表有設(shè)待排序的表有10個(gè)記錄個(gè)記錄,其關(guān)鍵字分別為其關(guān)鍵字分別為6,8,7,9,0,1,3,2,4,5。說(shuō)明采用快速排序方法進(jìn)行排序的過(guò)程。說(shuō)明采用快速排序方法進(jìn)行排序的過(guò)程。 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é)論: 快速排序的時(shí)間復(fù)雜度為快速排序的時(shí)間復(fù)雜度為O(nlog2n)由此可得快速排序所需時(shí)間的平均值為：由此可得快速排序所需時(shí)間的平均值為：平均所需棧空間為平均所需?？臻g為O(log2n)。nk-1n-k1次劃分的時(shí)間次劃分的時(shí)間Tavg(n)=Cnlog2n。10

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

30、，該趟排序則是從當(dāng)前無(wú)序區(qū)中選出關(guān)鍵字最小的記錄中選出關(guān)鍵字最小的記錄Rk，將它與無(wú)序區(qū)的第，將它與無(wú)序區(qū)的第1個(gè)記錄個(gè)記錄Ri交換，使交換，使R0.i和和Ri+1.n-1分別變?yōu)樾碌挠行騾^(qū)和新的無(wú)序分別變?yōu)樾碌挠行騾^(qū)和新的無(wú)序區(qū)。區(qū)。 假設(shè)排序過(guò)程中，待排記錄序列的狀態(tài)為：假設(shè)排序過(guò)程中，待排記錄序列的狀態(tài)為：有序序列有序序列R0.i-1無(wú)序序列無(wú)序序列 Ri.n-1 第第 i 趟趟簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序從中選出關(guān)鍵字最從中選出關(guān)鍵字最小的記錄小的記錄有序序列有序序列R0.i-1無(wú)序序列無(wú)序序列 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個(gè)記錄，其關(guān)鍵字分別為個(gè)記錄，其關(guān)鍵字分別為6,8,7,9,0,1,3,2,4,

32、5。說(shuō)明采用直接選擇排序方法進(jìn)行排序的過(guò)。說(shuō)明采用直接選擇排序方法進(jìn)行排序的過(guò)程。程。 初始關(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 對(duì)對(duì) n 個(gè)記錄進(jìn)

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

34、?。┑挠涗洝ｊP(guān)鍵字最大（或最?。┑挠涗?。 堆的定義是：堆的定義是：n個(gè)關(guān)鍵字序列個(gè)關(guān)鍵字序列K1,K2,Kn稱為稱為堆堆,當(dāng)且僅當(dāng)該當(dāng)且僅當(dāng)該序列滿足如下性質(zhì)（簡(jiǎn)稱為堆性質(zhì)）：序列滿足如下性質(zhì)（簡(jiǎn)稱為堆性質(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ù)，則若將該數(shù)列視作完全二叉樹(shù)，則 r2i 是是 ri 的左孩子；的左孩子； r2i+1 是是 ri 的右孩子。的右孩子。1236276549817355403498例如例如:是堆是堆14不不 堆排序的關(guān)鍵是構(gòu)造堆堆排序的關(guān)鍵是構(gòu)造堆,這里采用篩選算法建堆。這里采用篩選算法建堆。 所謂所謂“篩選篩選”指的是，對(duì)一棵左指的是，對(duì)一棵左/右子樹(shù)均為堆的完全二右子樹(shù)均為堆的完全二叉樹(shù)，叉樹(shù)，“調(diào)整調(diào)整”根結(jié)點(diǎn)使整個(gè)二叉樹(shù)也成為一個(gè)堆。根結(jié)點(diǎn)使整個(gè)二叉樹(shù)也成為

36、一個(gè)堆。堆堆篩選篩選堆堆98814973556412362740例如例如:是大根堆是大根堆12但在但在 98 和和 12 進(jìn)行互換之后，它就不是堆了，進(jìn)行互換之后，它就不是堆了，因此，需要對(duì)它進(jìn)行因此，需要對(duì)它進(jìn)行“篩選篩選”。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-) /進(jìn)行進(jìn)行n-1次循環(huán)次循環(huán),完成推排序完成推排序 temp=R1; /將第一個(gè)元素同當(dāng)前區(qū)間內(nèi)將第一個(gè)元素同當(dāng)前區(qū)間內(nèi)R1對(duì)換對(duì)換 R1=Ri;Ri=temp; sift(R,1,i-1); /篩選篩選R1結(jié)點(diǎn)結(jié)點(diǎn),得到得到i-1個(gè)結(jié)點(diǎn)的堆個(gè)結(jié)點(diǎn)的堆 例例10.6 設(shè)待排序的表有設(shè)待排序的表有10個(gè)記錄，其關(guān)鍵字分別為個(gè)記錄，其關(guān)鍵字分別為6,8,7,9,0,1,3,2,4,5。說(shuō)明采用堆排序方法進(jìn)行排序的過(guò)程。說(shuō)明采用堆排序方法進(jìn)行排序的過(guò)程。 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)整 堆排序過(guò)程：堆排序過(guò)程： 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 堆排序的時(shí)間復(fù)雜度分析：堆排序的時(shí)間復(fù)雜度分析

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

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

42、 high) RecType *R1; int i=low,j=mid+1,k=0; /k是是R1的下標(biāo)的下標(biāo),i、j分別為第分別為第1、2段的下標(biāo)段的下標(biāo) 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()實(shí)現(xiàn)了一次歸并實(shí)現(xiàn)了一次歸并 :空間復(fù)雜度空間復(fù)雜度為為O(hig

43、h-low+1)while (i=mid) /將第將第1段余下部分復(fù)制到段余下部分復(fù)制到R1 R1k=Ri; i+;k+; while (j=high) /將第將第2段余下部分復(fù)制到段余下部分復(fù)制到R1 R1k=Rj; j+;k+; for (k=0,i=low;i=high;k+,i+) /將將R1復(fù)制回復(fù)制回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長(zhǎng)的兩相鄰子表長(zhǎng)的兩相鄰子表 Merge(R,

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

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