數(shù)據(jù)結(jié)構(gòu)第九章內(nèi)部排序

1、第九章 內(nèi)部排序?qū)個(gè)性質(zhì)相同的數(shù)據(jù)元素按關(guān)鍵字值從小到大或從大到小排為有序序列。F外部排序F內(nèi)部排序當(dāng)待排數(shù)據(jù)元素的數(shù)量較少時(shí)，可將其一次全部調(diào)入內(nèi)存進(jìn)行排序，即稱內(nèi)部排序。當(dāng)待排數(shù)據(jù)元素的數(shù)量較大時(shí)，在排序過(guò)程中尚需對(duì)外存進(jìn)行訪問(wèn)，則稱外部排序。F排序一、基本術(shù)語(yǔ)注意當(dāng)按次關(guān)鍵字進(jìn)行排序時(shí)，由于可能存在關(guān)鍵字值相同的元素，因而排序結(jié)果不惟一。一、基本術(shù)語(yǔ)舉例原序列排序結(jié)果學(xué)號(hào)姓名成績(jī)1王云672李永強(qiáng)833劉小玲724趙祥925陳曉壯83學(xué)號(hào)姓名成績(jī)1王云673劉小玲722李永強(qiáng)835陳曉壯834趙祥92排序方法A必然穩(wěn)定的排序方法舉例原序列排序結(jié)果學(xué)號(hào)姓名成績(jī)1王云672李永強(qiáng)833劉小

2、玲724趙祥925陳曉壯83學(xué)號(hào)姓名成績(jī)1王云673劉小玲725陳曉壯832李永強(qiáng)834趙祥92排序方法B可能非穩(wěn)定的排序方法F插入排序按排序原則分F交換排序F選擇排序F歸并排序F計(jì)數(shù)排序二、內(nèi)部排序法分類F簡(jiǎn)單的內(nèi)部排序法O(n2)按排序的時(shí)間復(fù)雜度分F先進(jìn)的內(nèi)部排序法O(nlogn)F基數(shù)排序法O(dn)二、內(nèi)部排序法分類F折半插入排序法F2路插入排序法F表插入排序法F直接插入排序法F希爾排序法三、插入排序法設(shè)對(duì)數(shù)據(jù)元素序列R1,R2,Rn進(jìn)行排序，則：僅含R1的序列是長(zhǎng)度為1的按關(guān)鍵字值有序的序列；方法舉例4938659776132749012345678初始1、直接插入排序法依次逐個(gè)將

3、Ri（i=2,3,n）插入已有的按關(guān)鍵字值有序的序列，并使插入完成后的序列仍按關(guān)鍵字值有序。方法舉例4938659776132749012345678一趟比較次數(shù)移動(dòng)次數(shù)1次1次2次3次1、直接插入排序法依次逐個(gè)將Ri（i=2,3,n）插入已有的按關(guān)鍵字值有序的序列，并使插入完成后的序列仍按關(guān)鍵字值有序。方法舉例3849659776132749012345678二趟比較次數(shù)移動(dòng)次數(shù)1次1、直接插入排序法依次逐個(gè)將Ri（i=2,3,n）插入已有的按關(guān)鍵字值有序的序列，并使插入完成后的序列仍按關(guān)鍵字值有序。方法舉例3849659776132749012345678三趟比較次數(shù)移動(dòng)次數(shù)1次1、直接插

4、入排序法依次逐個(gè)將Ri（i=2,3,n）插入已有的按關(guān)鍵字值有序的序列，并使插入完成后的序列仍按關(guān)鍵字值有序。方法舉例3849659776132749012345678四趟比較次數(shù)移動(dòng)次數(shù)1次1次2次3次2次1、直接插入排序法依次逐個(gè)將Ri（i=2,3,n）插入已有的按關(guān)鍵字值有序的序列，并使插入完成后的序列仍按關(guān)鍵字值有序。方法舉例3849657690132749012345678五趟比較次數(shù)移動(dòng)次數(shù)1次1次2次3次2次3次4次4次5次5次6次7次1、直接插入排序法依次逐個(gè)將Ri（i=2,3,n）插入已有的按關(guān)鍵字值有序的序列，并使插入完成后的序列仍按關(guān)鍵字值有序。方法舉例133849657

5、6972749012345678六趟比較次數(shù)移動(dòng)次數(shù)1次1次2次3次2次3次4次4次5次5次6次6次1、直接插入排序法依次逐個(gè)將Ri（i=2,3,n）插入已有的按關(guān)鍵字值有序的序列，并使插入完成后的序列仍按關(guān)鍵字值有序。方法舉例1327384965769749012345678七趟比較次數(shù)移動(dòng)次數(shù)1次1次2次3次2次3次4次4次5次1、直接插入排序法4927存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)stst384965977613021345678#define LENGTH 8typedef ElemType SortTableLENGTH+1;1、直接插入排序法算法void InsertSort(SortTable &

6、amp;st)for(i=2;i=1 & stj.keyst0.key)if(sti.keysti-1.key)stj+1=stj;j-;1、直接插入排序法/if/InsertSortstj+1=st0;1、直接插入排序法元素的移動(dòng)，最少次，最多次。最多次；算法分析插入第i個(gè)數(shù)據(jù)元素時(shí)，關(guān)鍵字值間的比較最少次，況下需進(jìn)行次關(guān)鍵字值間的比較，次元素的移動(dòng)；在最壞情況下則需進(jìn)行次關(guān)鍵字值間的比較，次元素的移動(dòng)。若待排序列中有n個(gè)數(shù)據(jù)元素，則要完成排序在最好情1i-10i+1n-10(1+2+n-1)=n(n-1)/2(3+4+n+1)=(n-1)(n+4)/21、直接插入排序法并需要的輔助

7、存儲(chǔ)空間。算法時(shí)間復(fù)雜度在最好時(shí)為，最壞時(shí)為，可見(jiàn)直接插入排序法在或時(shí)效率較高。O(n)O(n2)一個(gè)元素待排數(shù)據(jù)元素序列已基本有序待排數(shù)據(jù)元素個(gè)數(shù)較少1、直接插入排序法改進(jìn)思路F減少關(guān)鍵字值間的比較次數(shù)F減少數(shù)據(jù)元素的移動(dòng)次數(shù)F盡可能創(chuàng)造待排元素序列基本有序或是待排數(shù)據(jù)元素個(gè)數(shù)較少的場(chǎng)景1、直接插入排序法在直接插入排序法中，關(guān)鍵字值間的比較主要用于確定元素的插入位置。由于插入第i個(gè)元素時(shí)，前i-1個(gè)元素已經(jīng)思路有序，所以可用折半查找確定其插入位置。2、折半插入排序法舉例3849657697132749012345678六趟比較次數(shù)移動(dòng)次數(shù)1次1次2次3次2次l lh hm m3次4次5次6次

8、7次2、折半插入排序法與直接插入排序法相比，折半插入排序法減少了關(guān)鍵字值間比較的次數(shù)，但沒(méi)有減少元素移動(dòng)的次數(shù)，因此算法的算法分析時(shí)間復(fù)雜度仍為O(n2)，并仍需一個(gè)元素的輔助存儲(chǔ)空間。2、折半插入排序法直接插入排序法在待排數(shù)據(jù)元素個(gè)數(shù)較少時(shí)效率較高，若先在待排元素中選擇一個(gè)R作為參照，然后把關(guān)鍵字值大思路于R的插入在其后，關(guān)鍵字值小于R的插入在其前，則能縮短元素所插入的表的長(zhǎng)度，從而減少排序過(guò)程中關(guān)鍵字值的比較次數(shù)和元素的移動(dòng)次數(shù)。3、二路插入排序法設(shè)置輔助數(shù)組sortedn，將R1保存至sorted0；方法設(shè)對(duì)數(shù)據(jù)元素序列R1,R2,Rn進(jìn)行排序，則：關(guān)鍵字值大于R1的插入在其后，關(guān)鍵字值

9、小于R1的插入在其前。以R1為參照，依次逐個(gè)有序插入Ri（i=2, 3,n），其中3、二路插入排序法舉例493865977613274901234567初始493865977613274901234567sortedf fr r一趟3、二路插入排序法舉例493865977613274901234567初始493865977613274901234567f fr r二趟sorted3、二路插入排序法舉例493865977613274901234567初始493865977613274901234567f fr r三趟sorted3、二路插入排序法舉例49386597761327490123456

10、7初始493865977613274901234567f fr r四趟sorted3、二路插入排序法舉例493865977613274901234567初始493865977613274901234567f fr r五趟sorted3、二路插入排序法舉例493865977613274901234567初始493865977613274901234567f fr r六趟sorted3、二路插入排序法舉例493865977613274901234567初始493865977613274901234567f fr r七趟sorted3、二路插入排序法與直接插入排序法相比，二路插入排序法中關(guān)鍵字值間的

11、比較次數(shù)及元素的移動(dòng)次數(shù)平均可減少一半左右，但時(shí)間算法分析復(fù)雜度仍為O(n2)，且需n個(gè)元素的輔助空間。當(dāng)R1的關(guān)鍵字值在待排元素中為最大值或最小值時(shí)，二路插入排序法退化為直接插入排序法。3、二路插入排序法如果在插入的過(guò)程中不改變數(shù)據(jù)元素的存儲(chǔ)位置，則不需要進(jìn)行元素的移動(dòng)，但應(yīng)另外設(shè)法記錄各待排元素間依關(guān)思路鍵字值從小到大或從大到小的先后次序。4、表插入排序法設(shè)置輔助數(shù)組addrn+1，其中addr0記錄結(jié)果序列中排方法在第一位的數(shù)據(jù)元素的下標(biāo)，addri（i=1,2,n）記錄設(shè)對(duì)數(shù)據(jù)元素序列R1,R2,Rn進(jìn)行排序，則：結(jié)果序列中排在Ri的下一位的數(shù)據(jù)元素的下標(biāo)，若結(jié)果序僅含R1的序列是長(zhǎng)度

12、為1的按關(guān)鍵字值有序的序列，所以令addr0=1，addr1=0；列中最后一個(gè)元素為Rj，則令addrj=0；4、表插入排序法入過(guò)程中不對(duì)數(shù)據(jù)元素進(jìn)行移動(dòng)，而只改變addr數(shù)組中相應(yīng)位置的值。的序列，并使插入完成后的序列仍按關(guān)鍵字值有序，在插依次逐個(gè)將Ri（i=2,3,n）插入已有的按關(guān)鍵字值有序4、表插入排序法舉例498初始14923836549757661372701234567addr一趟804981492383654975766137274、表插入排序法舉例498初始14923836549757661372701234567addr二趟8049814923836549757661372

13、74、表插入排序法舉例498初始14923836549757661372701234567addr三趟804981492383654975766137274、表插入排序法舉例498初始14923836549757661372701234567addr四趟804981492383654975766137274、表插入排序法舉例498初始14923836549757661372701234567addr五趟804981492383654975766137274、表插入排序法舉例498初始14923836549757661372701234567addr六趟804981492383654975766

14、137274、表插入排序法舉例498初始14923836549757661372701234567addr七趟804981492383654975766137274、表插入排序法舉例498初始14923836549757661372701234567addr八趟804981492383654975766137274、表插入排序法舉例498初始14923836549757661372701234567addr80812345674、表插入排序法與直接插入排序法相比，表插入排序法通過(guò)修改2n次指針值代替了數(shù)據(jù)元素的移動(dòng)，但未減少關(guān)鍵字值間的比較次算法分析數(shù)，時(shí)間復(fù)雜度仍為O(n2)，且需長(zhǎng)度為n的

15、整型輔助數(shù)組。經(jīng)表插入排序所得的有序鏈表只能進(jìn)行順序查找，若要進(jìn)行折半查找，則需對(duì)表中元素進(jìn)行重排。4、表插入排序法插入排序，待整個(gè)序列中的元素基本有序時(shí)，再對(duì)全體元素思路進(jìn)行一次直接插入排序。先將整個(gè)待排元素序列分割成若干子序列分別進(jìn)行直接這里子序列的構(gòu)成不是簡(jiǎn)單地逐段分割，而是將相隔某個(gè)“增量”的元素組成為一個(gè)子序列。5、希爾排序法舉例設(shè)增量序列為5,3,1。4938659776132749012345678初始55904105、希爾排序法舉例設(shè)增量序列為5,3,1。4938659776132749012345678第一趟：增量為555904105、希爾排序法舉例設(shè)增量序列為5,3,1。1

16、338659776492749012345678第一趟：增量為555904105、希爾排序法舉例設(shè)增量序列為5,3,1。1327659776493849012345678第一趟：增量為555904105、希爾排序法舉例設(shè)增量序列為5,3,1。1327659776493849012345678第一趟：增量為555904105、希爾排序法舉例設(shè)增量序列為5,3,1。1327655576493849012345678第一趟：增量為597904105、希爾排序法舉例設(shè)增量序列為5,3,1。1327655504493849012345678第二趟：增量為397976105、希爾排序法舉例設(shè)增量序列為5,

17、3,1。1327653804495549012345678第二趟：增量為397976105、希爾排序法舉例設(shè)增量序列為5,3,1。1304653827495549012345678第二趟：增量為397976105、希爾排序法舉例設(shè)增量序列為5,3,1。1304653827495549012345678第三趟：增量為197976105、希爾排序法舉例設(shè)增量序列為5,3,1。0413653827495549012345678第三趟：增量為197976105、希爾排序法舉例設(shè)增量序列為5,3,1。0413653827495549012345678第三趟：增量為197976105、希爾排序法在希爾排序

18、中，關(guān)鍵字較小的元素能跳躍式地前移，從而在進(jìn)行最后一趟增量為1的插入排序時(shí)，序列已基本有序，算法分析只要進(jìn)行少量的比較和移動(dòng)即可完成排序，因而時(shí)間復(fù)雜度比直接插入排序低。希爾排序的時(shí)間復(fù)雜度與所取增量序列有關(guān)。增量序列可有各種取法，但各增量值間應(yīng)無(wú)除1之外的公因子，且最后一個(gè)增量值必為1。5、希爾排序法F快速排序法F起泡排序法四、交換排序方法對(duì)相鄰的兩個(gè)數(shù)據(jù)元素的關(guān)鍵字值進(jìn)行比較，若為逆序，方法設(shè)對(duì)數(shù)據(jù)元素序列R1,R2,Rn進(jìn)行排序，則：一趟排序完成后，關(guān)鍵字值最大的數(shù)據(jù)元素排在了最后，如此重復(fù)n-1次，即可完成排序。則交換；1、起泡排序法舉例498初始1492383654975766137

19、27一趟比較次數(shù)移動(dòng)次數(shù)1次3次6次9次2次3次12次4次15次5次6次7次1、起泡排序法舉例978初始138249365476513627749一趟比較次數(shù)移動(dòng)次數(shù)1次3次6次9次2次3次4次5次6次二趟15次7次1、起泡排序法三趟二趟舉例978初始138249365413527649776一趟比較次數(shù)移動(dòng)次數(shù)1次3次6次9次2次3次4次5次15次7次9次6次1、起泡排序法四趟二趟舉例978初始138249313427549665776一趟比較次數(shù)移動(dòng)次數(shù)1次3次6次2次3次4次15次7次9次6次三趟9次5次1、起泡排序法五趟二趟舉例978初始138213327449549665776一趟比

20、較次數(shù)移動(dòng)次數(shù)1次3次6次2次3次15次7次9次6次三趟9次5次比較次數(shù)移動(dòng)次數(shù)四趟6次4次1、起泡排序法六趟二趟舉例978初始113227338449549665776一趟比較次數(shù)移動(dòng)次數(shù)1次2次15次7次9次6次三趟9次5次比較次數(shù)移動(dòng)次數(shù)四趟6次4次五趟6次3次1、起泡排序法元素的移動(dòng)，最少次，最多次。最多次；算法分析在第i趟起泡排序中，關(guān)鍵字值間的比較最少次，況下需進(jìn)行次關(guān)鍵字值間的比較，次元素的移動(dòng)；在最壞情況下則需進(jìn)行次關(guān)鍵字值間的比較，次元素的移動(dòng)。若待排序列中有n個(gè)數(shù)據(jù)元素，則要完成排序在最好情n-in-i03(n-i)n-10(1+2+n-1)=n(n-1)/23(1+2+n

21、)=3n(n-1)/21、起泡排序法并需要的輔助存儲(chǔ)空間。算法時(shí)間復(fù)雜度在最好時(shí)為，最壞時(shí)為，O(n)O(n2)一個(gè)元素1、起泡排序法若s=t ，即序列中僅一個(gè)元素，則排序完成；方法設(shè)對(duì)數(shù)據(jù)元素序列Rs,Rt進(jìn)行排序，則：若st，則以Rs為樞軸進(jìn)行一趟快速排序：493865977613274912345678初始02、快速排序法鍵字值的元素，若該元素在樞軸之后，則交換兩者位置；493865977613274912345678一趟h hl l令low=s，high=t；從high所指位置開(kāi)始向前找第一個(gè)關(guān)鍵字值小于樞軸關(guān)鍵02、快速排序法值的元素，若該元素在樞軸之前，則交換兩者位置；493865

22、977613274912345678一趟h hl l從low所指位置開(kāi)始向后找第一個(gè)關(guān)鍵字值大于樞軸關(guān)鍵字02、快速排序法493865977613274912345678一趟h hl l0如此重復(fù)直至high=low，則本趟快排完成；2、快速排序法493865977613274912345678二趟h hl l0分別對(duì)樞軸元素之前和之后的序列進(jìn)行快排。2、快速排序法493865977613274912345678二趟h hl l0分別對(duì)樞軸元素之前和之后的序列進(jìn)行快排。2、快速排序法493865977613274912345678三趟h hl l0分別對(duì)樞軸元素之前和之后的序列進(jìn)行快排。2、快

23、速排序法則可減少元素移動(dòng)次數(shù)。改進(jìn)在快速排序的過(guò)程中，若用一輔助空間暫存樞軸元素，493865977613274912345678初始0h hl l2、快速排序法4927存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)stst384965977613021345678#define LENGTH 8typedef ElemType SortTableLENGTH+1;2、快速排序法算法int Partition(SortTable &st,int low,int high)/以stlow為樞軸，對(duì)stlow至sthigh完成一趟快排st0=stlow;/暫存樞軸元素while(lowhigh)while(low=st0.

24、key)-high;/返回本趟快排完成后樞軸元素所在位置的下標(biāo)stlow=sthigh;2、快速排序法sthigh=stlow;/whilereturn low;/Partitionstlow=st0;/樞軸元素到位while(lowhigh&stlow.key=st0.key)+low;2、快速排序法if (lowhigh)p=Partition(L,low,high);/完成一趟快排QSort(st,p+1,high);/ifQSort(st,low,p-1);void QSort(SortTable &st,int low,int high)/QSort2、快速排序法QS

25、ort(st,1,LENGTH);/QuickSortvoid QuickSort(SortTable &st)2、快速排序法快速排序法平均時(shí)間復(fù)雜度為O(knlogn)，經(jīng)驗(yàn)證明，在所有時(shí)間復(fù)雜度處于同數(shù)量級(jí)的內(nèi)部排序算法中，快速排算法分析序法的常數(shù)因子k最小。若待排元素序列初始即為正序或基本有序，快速排序法將退化為起泡排序法，時(shí)間復(fù)雜度達(dá)O(n2)。2、快速排序法F樹(shù)形選擇排序法F簡(jiǎn)單選擇排序法F堆排序法五、選擇排序方法n-i+1 (i=1,n-1) 個(gè)元素中選擇一個(gè)關(guān)鍵字值最小的，方法設(shè)對(duì)數(shù)據(jù)元素序列R1,R2,Rn進(jìn)行排序，則每趟在排序完成。并將它與序列中的第i個(gè)元素交換，如此

26、重復(fù)n-1次，則1、簡(jiǎn)單選擇排序法舉例4938659776132749012345678初始1、簡(jiǎn)單選擇排序法舉例4938659776132749012345678一趟minmini i比較次數(shù)移動(dòng)次數(shù)1次2次3次4次5次6次7次3次1、簡(jiǎn)單選擇排序法舉例1338659776492749012345678二趟minmini i比較次數(shù)移動(dòng)次數(shù)1次2次3次4次5次6次3次1、簡(jiǎn)單選擇排序法舉例1327659776493849012345678三趟minmini i比較次數(shù)移動(dòng)次數(shù)1次2次3次4次5次3次1、簡(jiǎn)單選擇排序法舉例1327389776496549012345678四趟minmini i

27、比較次數(shù)移動(dòng)次數(shù)1次2次3次4次3次1、簡(jiǎn)單選擇排序法舉例1327384976976549012345678五趟minmini i比較次數(shù)移動(dòng)次數(shù)1次2次3次3次1、簡(jiǎn)單選擇排序法舉例1327384976976549012345678六趟minmini i比較次數(shù)移動(dòng)次數(shù)1次2次3次1、簡(jiǎn)單選擇排序法舉例1327384976659749012345678七趟minmini i比較次數(shù)移動(dòng)次數(shù)1次3次1、簡(jiǎn)單選擇排序法舉例1327384997657649012345678七趟1、簡(jiǎn)單選擇排序法鍵字值間的比較，次元素的移動(dòng)。次元素的移動(dòng)；元素的移動(dòng)，最少次，最多次。最多次；算法分析在第i趟簡(jiǎn)單選擇

28、排序中，關(guān)鍵字值間比較最少 次，況下需進(jìn)行次關(guān)鍵字值間的比較，在最壞情況下則需進(jìn)行次關(guān)若待排序列中有n個(gè)數(shù)據(jù)元素，則要完成排序在最好情n-in-i030n(n-1)/23(n-1)(n-1)+2+1=n(n-1)/21、簡(jiǎn)單選擇排序法空間。算法的時(shí)間復(fù)雜度為O(n2)，并需要一個(gè)元素的輔助存儲(chǔ)1、簡(jiǎn)單選擇排序法先對(duì)n個(gè)元素的關(guān)鍵字值進(jìn)行兩兩比較，然后在其中的方法設(shè)對(duì)數(shù)據(jù)元素序列R1,R2,Rn進(jìn)行排序，則：出關(guān)鍵字值最小的元素，該過(guò)程可用一棵有n個(gè)葉子結(jié) n/2 個(gè)較小者間再進(jìn)行兩兩比較，如此重復(fù)，直至選點(diǎn)的完全二叉樹(shù)表示；2、樹(shù)形選擇排序法舉例493865977613274901234567

29、8初始2、樹(shù)形選擇排序法舉例4938659776132749比較次數(shù)移動(dòng)次數(shù)1次2次3次4次5次6次7次i i38651327381313minmin4938659776132749012345678一趟2、樹(shù)形選擇排序法中的對(duì)應(yīng)關(guān)鍵字值改為，并修改從該結(jié)點(diǎn)到根的路徑上方法通過(guò)交換，使關(guān)鍵字值最小的元素到位，然后將葉子結(jié)點(diǎn)如此重復(fù)n-1次，則排序完成。各結(jié)點(diǎn)的值，以選出關(guān)鍵字值次小的數(shù)據(jù)元素；2、樹(shù)形選擇排序法舉例4938659776132749比較次數(shù)移動(dòng)次數(shù)7次3次i i38651327381313minmin4938659776132749012345678一趟2、樹(shù)形選擇排序法舉例49

30、38659776132749比較次數(shù)移動(dòng)次數(shù)i i386513273813131338659776492749012345678二趟1次2次3次3次762727minmin2、樹(shù)形選擇排序法舉例49386597762749比較次數(shù)移動(dòng)次數(shù)i i386576273827271327659776493849012345678三趟1次2次3次3次minmin4949382、樹(shù)形選擇排序法舉例493865977649比較次數(shù)移動(dòng)次數(shù)i i386576493849381327389776496549012345678四趟1次2次3次3次minmin4949492、樹(shù)形選擇排序法舉例4965977649比

31、較次數(shù)移動(dòng)次數(shù)i i496576494949491327384976976549012345678五趟1次2次3次3次minmin65492、樹(shù)形選擇排序法舉例65977649比較次數(shù)移動(dòng)次數(shù)i i6576496549491327384949976576012345678六趟1次2次3次3次minmin76652、樹(shù)形選擇排序法舉例659776比較次數(shù)移動(dòng)次數(shù)i i65766576651327384949659776012345678七趟1次2次3次3次minmin9797762、樹(shù)形選擇排序法由此可見(jiàn)，樹(shù)形選擇排序的時(shí)間復(fù)雜度為O(nlogn)，最壞情況下則需進(jìn)行3次元素移動(dòng)。而在其后的每趟

32、樹(shù)形選擇排序中，關(guān)鍵字值間只需進(jìn)行算法分析在第1趟樹(shù)形選擇排序中，關(guān)鍵字值間需進(jìn)行n-1次比較，每趟樹(shù)形選擇排序，在最好情況下需進(jìn)行0次元素移動(dòng)， log2n 次比較。所需輔助空間為(2n-1)+1個(gè)。2、樹(shù)形選擇排序法將含n個(gè)待排元素的初始序列看作一棵完全二叉樹(shù)的層序方法設(shè)對(duì)數(shù)據(jù)元素序列R1,R2,Rn進(jìn)行排序，則：至第1個(gè)元素止，逐一進(jìn)行“篩選”；遍歷序列，在這棵完全二叉樹(shù)上，從第 n/2 個(gè)元素起，3、堆排序法將該元素的關(guān)鍵字值與其左、右孩子的關(guān)鍵字值進(jìn)在完全二叉樹(shù)上對(duì)一個(gè)元素進(jìn)行“篩選”，就是將該元素與關(guān)鍵字值較大的孩子交換。行比較，如果其關(guān)鍵字值不是三者之中最大的，則如此循環(huán)，直至該

33、元素成為葉子結(jié)點(diǎn)或其左、右孩子的關(guān)鍵字值都不比它大為止。舉例4938659776132749012345678初始3、堆排序法舉例0491382653974765136277498一趟3、堆排序法舉例比較次數(shù)移動(dòng)次數(shù)1次2次3次4次5次6次7次4913826539747651362774983次6次8次9次12次9次10次第一輪“篩選”完成后，初始大頂堆建成。3、堆排序法進(jìn)行“篩選”，使剩余元素重又構(gòu)成一個(gè)大頂堆；方法將堆頂元素與該堆最后一個(gè)元素交換，并對(duì)新的堆頂元素如此重復(fù)n-1次，則排序完成。3、堆排序法舉例比較次數(shù)移動(dòng)次數(shù)1次2次3次4次9717626534944951362773883

34、次6次9次二趟3、堆排序法舉例比較次數(shù)移動(dòng)次數(shù)1次2次3次7614926533844951362779783次6次三趟3、堆排序法舉例比較次數(shù)移動(dòng)次數(shù)1次2次3次6514922733844951367679783次6次四趟4次3、堆排序法舉例比較次數(shù)移動(dòng)次數(shù)1次2次3次4914922733841356567679783次6次五趟9次3、堆排序法舉例比較次數(shù)移動(dòng)次數(shù)1次2次4913822731344956567679783次6次六趟3、堆排序法舉例比較次數(shù)移動(dòng)次數(shù)1次3811322734944956567679783次6次七趟3、堆排序法舉例1312723834944956567679783、堆

35、排序法4927存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)stst384965977613021345678#define LENGTH 8typedef ElemType SortTableLENGTH+1;3、堆排序法算法void HeapAdjust(SortTable &st,int s,int m)/在sts.m中，對(duì)sts進(jìn)行篩選k=s;j=2*k;/k為待篩選元素下標(biāo)，j為k的左孩子下標(biāo)while(j=m)/待篩選元素有左孩子，即非葉子結(jié)點(diǎn)st0=sts;/暫存待篩選元素3、堆排序法if(jstj.key)/右孩子鍵值更大stk=stj+1;/右孩子上移elsestk=stj;/左孩子上移k=j;/待篩

36、選元素的新位置k=j+1;/待篩選元素的新位置if(stj.keyst0.key)/左孩子鍵值較大3、堆排序法if(jst0.key)/右孩子鍵值較大stk=stj+1;/右孩子上移/ifelse break;/左、右孩子的鍵值都比待篩選元素小k=j+1;/待篩選元素的新位置else/左孩子鍵值不大j=2*k;/進(jìn)行下一輪篩選/while/HeapAdjust3、堆排序法for(i=LENGTH/2;i=1;-i)HeapAdjust(st,i,LENGTH);st1=sti;sti=st0;/一個(gè)元素到位HeapAdjust(st,1,i-1);/對(duì)新的堆頂元素做一輪篩選for(i=LENG

37、TH;i1;-i)st0=st1;void HeapSort(SortTable &st)/HeapSort3、堆排序法堆排序法的時(shí)間主要用于反復(fù)篩選，除構(gòu)造初始堆外，每趟排序進(jìn)行一輪篩選，篩選時(shí)進(jìn)行的關(guān)鍵字比較次數(shù)最算法分析壞情況下為(完全二叉樹(shù)的高度-1)*2。若有n個(gè)待排元素，則完全二叉樹(shù)的高度為log2n+1，所以在最壞情況下，堆排序法的時(shí)間復(fù)雜度也為O(nlogn)。另外還需一個(gè)元素的輔助空間。3、堆排序法F多路歸并排序法F二路歸并排序法六、歸并排序方法對(duì)數(shù)據(jù)元素序列R1,R n/2進(jìn)行排序；方法設(shè)對(duì)數(shù)據(jù)元素序列R1,R2,Rn進(jìn)行排序，則：對(duì)由和得到的有序序列進(jìn)行歸并。對(duì)數(shù)

38、據(jù)元素序列Rn/2+1 , Rn進(jìn)行排序；二路歸并排序法舉例493865977613274901234567初始1、二路歸并排序法舉例01234567一趟1、二路歸并排序法比較次數(shù)移動(dòng)次數(shù)1次2次3次4次1次2次3次49386597761327494次5次6次7次8次舉例01234567二趟1、二路歸并排序法比較次數(shù)移動(dòng)次數(shù)1次2次3次4次1次2次3次38496597137627494次5次6次7次8次5次舉例01234567三趟1、二路歸并排序法比較次數(shù)移動(dòng)次數(shù)1次2次3次4次1次2次3次38496597132749764次5次6次7次8次5次6次7次4927存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)stst384965

39、977613021345678#define LENGTH 8typedef ElemType SortTableLENGTH+1;二路歸并排序法對(duì)st1.m排序，m=LENGTH/2；思路對(duì)已有序的st1.m和stm+1.LENGTH歸并。對(duì)stm+1.LENGTH排序；void MSort(SortTable st,int i,int j)void Merge(SortTable st,int i,int j,int k)二路歸并排序法4927stst384965977613021345678思路細(xì)化void MSort(SortTable st,int i,int j)MSort(st,

40、i,(i+j)/2);若i=j，則排序完成；MSort(st,(i+j)/2+1,j);Merge(st,i,(i+j)/2,j)。二路歸并排序法4927stst384965977613021345678設(shè)置輔助數(shù)組temp；思路細(xì)化void Merge(SortTable st,int i,int j,int k)令x=i，y=j+1，z=1；tempxyz比較stx和sty，較小者賦給tempz，并使相應(yīng)指針下移；重復(fù)直至一表結(jié)束；將另一表中剩余元素全部復(fù)制到temp；7649stst493865971327021345678將temp復(fù)制到st。算法void MSort(SortTable st,int i,int j)MSort(st,i,(i+j)/2);if (i=j) return;MSort(st,(i+j)/2+1,j);Merge(st,i,(i+j)/2,j);/MSort二路歸并排序法void Merge(SortTable st,int i,int j,int k)算法x=i;y=j+1;z=1;while(x=j&y=k)if (stx.key=sty.key) tempz+=stx+;else tempz+=sty+;/whilewhile (x=j) tempz+=stx+;while (y=k)