數(shù)據(jù)結(jié)構(gòu)第十章

概述排序：將一個數(shù)據(jù)元素(或記錄)的隨意序列，重新排列成一個按關(guān)鍵字有序的序列排序穩(wěn)定性：若有兩個關(guān)鍵字相同記錄Ri和Rj,排序之前Ri在Rj之前，排序后仍滿足這種次序,這種排序是穩(wěn)定的內(nèi)部排序：對內(nèi)存中數(shù)據(jù)進行排序內(nèi)部排序分類：⑴插入排序⑵交換排序⑶選擇排序⑷歸并排序⑸計數(shù)排序(1)插入排序干脆插入排序其它插入排序希爾排序干脆插入排序：是一種最簡潔的排序方法,它的基本操作思想是將一個記錄插入到已排好序的有序表中,從而得到一個新的,記錄數(shù)增1的有序表排序過程：將序列分成兩部分，一部分已排序，一部分未排序，初始時，已經(jīng)排序部分只有這個序列第一個元素依次取未排序中的每一個元素，插入到已排序部分恰當(dāng)位置.例：干脆插入排序初始關(guān)鍵字(49)38659776132749i=2(38)(3849)659776132749i=3

(65)(384965)9776132749i=4(97)(38496597)76132749i=5(76)(3849657697)132749i=6(13)(133849657697)2749i=7(27)(13273849657697)49i=8(49)(1327384949657697)

干脆插入排序示例VoidInsertSort(SqList&L){//對依次表L作干脆插入排序for(i=2;i<=L.length;++i)ifLT(L.r[i].key,L.r[i-1].key){L.r[0]=L.r[i];//復(fù)制為哨兵for(j=i-1;LT(L.r[0].key,L.r[j].key);--j)L.r[j+1]=L.r[j];//記錄后移L.r[j+1]=L.r[0];//插入到正確位置}}//InsertSort干脆插入排序算法算法分析干脆插入排序的空間困難度:O(1)時間困難度的分析:1.當(dāng)待排序序列為正序時:須要進行n-1趟排序,每一趟只要進行一次比較,所以在排序過程中關(guān)鍵字的比較,移動記錄的次數(shù)為∑i=2n1,時間困難度為O(n)2.當(dāng)待排序序列為逆序時:須要進行n-1趟排序,在排序過程中,進行∑i=2n(i)=(n+2)(n-1)/2次關(guān)鍵字的比較,記錄移動的次數(shù)為∑i=2n(i+1)=(n+4)(n-1)/2,所以時間困難度為O(n2)一：折半插入排序已排序部分本身有序，找插入位置時可以通過折半查找方法來確定插入位置，這樣削減了元素比較次數(shù)，但沒削減元素移動次數(shù)算法：VoidBinsertSort(Sqlist&L){//對依次表L作折半插入排序for(i=2;i<=L.length;++i){L.r[0]=L.r[i];low=1;high=i-1;其它插入排序

while(low<=high){//在r[low..high]中折半查找有序插入的位置m=(low+high)/2;//折半ifLT(L.r[0].key,L.r[m].key)high=m-1;//插入點在低半?yún)^(qū)elselow=m+1;//插入點在高半?yún)^(qū)}//whilefor(j=i-1;j>=high+1;--j)L[j+1]=L.r[j];//記錄后移L.r[high+1]=L.r[0];//插入}//for}//BinsertSort二：2-路插入排序在折半插入排序的基礎(chǔ)上接著改進，目的是削減排序過程中移動記錄的次數(shù)，但須要n個記錄的幫助空間,當(dāng)l.r[1].key是最小(或者最大)時,2-路插入排序就失去了優(yōu)越性排序過程：⑴原數(shù)組為data[],開拓一個與data[]相等空間d[]⑵將d[]構(gòu)成一個循環(huán)數(shù)組，并設(shè)兩個指針first和final分別指向已排序部分第一個元素和最終一個元素⑶將data[0]賦給d[0]，以d[0]將d[]分成兩部分⑷依次處理data[1]到data[n-1]if(data[i]<d[0])用折半法將data[i]插入第一部分else用折半法插入其次部分例：Data[]4938659776132749D[]

D[]1327384949657697final49first38firstfinal49final6597first13first4938final762749三：表插入排序(目的是在排序過程中,不須要移動記錄)#defineSIZE100//靜態(tài)鏈表容量Typedefstruct{RcdTyperc;//記錄項intnext;//指針項}SLNode;//表結(jié)點類型Typedefstruct{SLNoder[SIZE];//0號單元為表頭結(jié)點intlength;//鏈表當(dāng)前長度}SLinkListType;//靜態(tài)鏈表類型設(shè)上述說明為靜態(tài)鏈表類型作為待排記錄序列的存儲結(jié)構(gòu)，為插入便利起見，設(shè)數(shù)組下標(biāo)為“0”的重量為表頭結(jié)點，并令表頭結(jié)點記錄的關(guān)鍵字取最大整數(shù)MAXINT則表插入排序過程描述如下：首先將靜態(tài)鏈表中數(shù)組下標(biāo)為“1”的重量(結(jié)點)和表頭結(jié)點構(gòu)成一個循環(huán)鏈表，然后依次將下標(biāo)為“2”至“n”的分量(結(jié)點)按記錄關(guān)鍵字非遞減插入到循環(huán)鏈表中具體見p269圖10。3從表插入的基本操作仍是將一個記錄插入到已經(jīng)排好的有序表中。

希爾排序思想：先將整個待排記錄序列分割成為若干子序列分別進行干脆插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行一次干脆插入排序希爾排序特點：子序列的構(gòu)成不是簡潔的“逐段分割是將相隔某個“增量”的記錄組成一個子序列希爾排序希爾排序示例初始關(guān)鍵字49386597761327495504d1=5一趟排序結(jié)果13274955044938659776d2=3二趟排序結(jié)果13044938274955659776d3=1三趟排序結(jié)果：04132738494955657697VoidShellInsert(Sqlist&L,intdk){//對依次表L作一趟希爾插入排序for(i=dk+1;i<=L.length;++i)ifLT(L.r[i].key,L.r[i-dk].key){L.r[0]=L.r[i];for(j=i-dk;j>0&<(L.r[0].key,L.r[j].key);j-=dk)L.r[j+dk]=L.r[j];L.r[j+dk]=L.r[0];}}ShellInsert

希爾排序算法voidShellSort(SqList&L,intdlta[],intt){//按遞增序列dlta[0..t-1]對依次表L作希爾排序for(k=0;k<t;++t)ShellInsert(L,dlta[k]);//一趟增量為dlta[k]的插入排序}ShellSort10。3起泡排序和快速排序起泡排序思想：

依次對未排序部分相鄰的兩個元素進行比較,若逆序則交換位置,每一趟可以使一個最大(最小)元素從這個序列中冒出來,經(jīng)過n-1趟,就可以排好序例：起泡排序示例初始關(guān)鍵字12231814490第一趟排序后

12231814490

其次趟排序后121814423第三趟排序后1214418

第四趟排序后12414

第五趟排序后4算法分析起泡排序結(jié)束條件為:一趟排序過程中,沒有交換記錄的操作.分析:1.當(dāng)待排序序列為正序時:只要一趟排序,在排序過程中,進行n-1次關(guān)鍵字的比較,而且不移動記錄,時間困難度為O(n)2.當(dāng)待排序序列為逆序時:須要進行n-1趟排序,在排序過程中,進行∑i=2n(i-1)=n(n-1)/2次關(guān)鍵字的比較,并且作等數(shù)量的記錄移動,所以時間困難度為O(n2)快速排序快速排序思想：通過一趟排序?qū)⒋庞涗浄指畛瑟毩⒌膬刹糠?，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，再分別對這兩部分記錄接著進行快速排序一趟快速排序的過程1.在待排序序列中隨意選擇一個記錄(通常選擇第一個記錄)作為樞軸記錄L.r[s].設(shè)樞軸記錄的關(guān)鍵字為pivotkey2.設(shè)low指向待排序序列中的第一個記錄,high指向待排序序列中的最終一個記錄.3.先將high向low方向掃描,若l.r[high].key<pivotkey,則將l.r[high]=>l.r[low].樞軸記錄4.再將low向high方向掃描,若l.r[low].key>pivotkey,則將l.r[low]=>l.r[high]5.重復(fù)執(zhí)行3>,4>兩步,直到low=high時,再將pivotkey的記錄=>l.r[low]到此,待排序序列以pivotkey為界,分成兩部分:前一部分的記錄關(guān)鍵字比后一部分小.再分別對這兩部分進行快速排序例：對下列待排序序列進行快速排序49l38132749初始關(guān)鍵字hh2738651349hl第一次交換之后65l2738136549lh其次次交換之后2738136549第三次交換之后49lh完成一趟排序27381365

49分別再進行快速排序分別再進行快速排序最終得到有序序列132738494965算法10.6(a)IntPartition(SqList&L,intlow,inthigh){pivotkey=L.r[low].key;While(low<high){while(low<high&&L.r[high].key>=pivotkey)--high;L.r[low]←→L.r[high];while(low<high&&L.r[low].key<=pivotkey)++low;L.r[low]←→L.r[high];}returnlow;//返回樞軸記錄的位置}//Partition快速排序算法實現(xiàn)改寫上述算法：將樞軸暫存在r[0]的位置上，直至一趟排序結(jié)束后再將樞軸記錄移至正確位置上，算法10.6(b)：IntPartition(SqList&L,intlow,inthigh){L.r[0]=L.r[low];Pivotkey=L.r[low].key;while(low<high){while(low<high&&L.r[high].key>=pivotkey)--high;

L.r[low]=L.r[high];while(low<high&&L.r[low].key<=pivotkey)++low;L.r[high]=L.r[low];}L.r[low]=L.r[0];//樞軸記錄到位returnlow;}//Partition算法10.7voidQsort(SqList&L,intlow,inthigh){if(low<high){pivotloc=Partition(L,low,high);Qsort(L,low,pivotloc-1);Qsort(L,pivotloc+1,high);}}//Qsort算法10.8VoidQuickSort(Sqlist&L){Qsort(L,1,L.length);}//QuickSort;遞歸形式的快速排序算法快速排序算法分析假設(shè)n個關(guān)鍵字是等概率分布的,第k個位置是通過調(diào)用Partition后的樞軸記錄應(yīng)當(dāng)處的位置,它將文件分成兩部分:前一部分有k-1個記錄,后一部分有n-k個記錄.設(shè)T(n)是快速排序的平均時間,則依據(jù)算法QuickSort可以得到下列遞歸公式,設(shè)k為1,2…n中的隨意一個值并且概率相同.快速排序算法分析T(n)=Cn+1/n∑k=2n(T(k-1)+T(n-k))T(1)=T(0)=0求解此遞歸方程:得到:T(n)=2(n+1)log2n+O(n)時間困難度:O(nlog2n)空間困難度:O(log2n)穩(wěn)定性質(zhì):不穩(wěn)定10。4選擇排序簡潔選擇排序樹形選擇排序堆排序算法思想:每一趟在n-i+1個記錄中(i=1,2,3…..n-1)選出關(guān)鍵字最小的記錄作為有序列中的第i個記錄.一趟簡潔選擇排序的操作為：通過n-i次關(guān)鍵字間的比較，從n-i+1個記錄中選出關(guān)鍵字最小記錄，并和第i(1<=i<=n)個記錄交換之,使得待排序部分增加一個記錄簡潔選擇排序簡潔選擇排序算法10.9：voidSelectSort(Sqlist&L){for(i=1;i<L.length;++i){j=SelectMinKey(L,i);if(i!=j)L.r[i]←→L.r[j];}}//SelectSort為了削減“比較”關(guān)鍵字的次數(shù)，引出樹形選擇排序樹形選擇排序：又稱錦標(biāo)賽排序，是一種依據(jù)錦標(biāo)賽思想進行選擇排序的方法。首先對n個記錄的關(guān)鍵字進行兩兩比較，得到n/2個較小者,然后再對對n/2個較小者進行兩兩比較，如次重復(fù)，直至選出最小關(guān)鍵字的記錄為止.這個過程可用一棵有n個葉子結(jié)點的完全二叉樹表示樹形選擇排序樹形選擇排序示例初始關(guān)鍵字49386597761327492749271313763865976538384913最小者輸出：132713輸出13∞762727輸出27∞384949657697同理得出38樹形選擇排序削減了比較次數(shù)，但是輔存增加了，于是為了彌補這個缺點，引出堆排序堆：是一棵完全二叉樹，全部根結(jié)點小于等于或大于等于其孩子結(jié)點值堆排序：若在輸出堆頂?shù)淖钚≈抵?，使得剩余n-1個元素得序列重又建成一個堆，則輸出n個元素的次小值。如此反復(fù)執(zhí)行，便得到一個有序序列,這個過程稱為堆排序堆排序堆排序的過程堆排序:⑴如何將無序序列構(gòu)成一個堆⑵輸出堆頂元素⑶將剩余元素重新構(gòu)成一個堆重復(fù)執(zhí)行(2)和(3)直到所以元素全部輸出，輸出序列就是排好序的有序序列如何將一個無序序列構(gòu)成為一個堆?方法:1.將無序序列按依次構(gòu)成一棵完全二叉樹.2.從完全二叉樹的最終一個非終端結(jié)點起先反復(fù)進行自上而下的”篩選”.最終一個非終端結(jié)點的編號為n/2下取整.”篩選”:將該結(jié)點值與其孩子結(jié)點值進行比較,若不符合堆的定義,則與其孩子中的小者交換,這個”篩選”過程直到葉結(jié)點或者滿足堆的定義如何將剩余元素構(gòu)成一個堆?輸出堆頂元素后,用堆尾元素代替堆頂元素,然后再從根結(jié)點向葉結(jié)點方向”篩選”,構(gòu)成一個新的堆.要進行堆排序首先要把一個無序序列建成一個堆，這個過程也叫“篩選”過程，如圖說明：無序序列769738134927654997被篩選之后的狀態(tài)4997651365被篩選之后的狀態(tài)38被篩選之后的狀態(tài)49被篩選之后建成的堆134927算法10.10：typedefSqListHeapType;//堆接受依次表存儲表示VoidHeadAdjust(HeapType&H,ints,intm){//已知H.r[s..m]中,記錄的關(guān)鍵字除H.r[s].key之外均滿足堆的定義，本函數(shù)調(diào)整H.r[s]的關(guān)鍵字，使H.r[s..m]成為一個大頂堆(對其中記錄的關(guān)鍵字而言)Rc=H.r[s];For(j=2*s;j<=m;j*=2){//沿key較大的孩子結(jié)點向下篩選堆排序算法實現(xiàn)if(j<m&<(h.r[j].key,h.r[j+1].key))++j;//找出兩個孩子中的大者h.r[j].keyif(!LT(rc.key,h.r[j].key))break;//rc應(yīng)插入在位置s上H.r[s]=H.r[j];s=j;}H.r[s]=rc;//插入}//HeadAdjust堆排序算法10.11：voidHeapSort(HeapType&H){//對依次表H進行堆排序for(i=H.length/2;i>0;--i)//把H.r[1..H..length]建成大頂堆HeapAdjust(H.i,H.length);for(i=H.length;i>1;--i){H.r[1]←→H.r[i];//將堆頂記錄和當(dāng)前未經(jīng)排序子序列Hr[1..i]中最終一個記錄相互交換HeapAdjust(H,1,i-1);//將H.r[1..i-1]重新調(diào)整為大頂堆}}//HeapSort例：堆排序在堆頂輸出一個小元素后，以堆中最終一個元素替代之，再重新排成一個小堆頂堆496527977638491349652713763849輸出堆頂13,以最終一個元素97替代之9797654976384927調(diào)整建成新堆同理接著重復(fù)上述操作，接著輸出堆頂27，把最終一個元素替代之，接著輸出全部元素堆排序算法分析堆排序的運行時間主要耗費在建立初始堆和將剩余元素構(gòu)成新堆而進行的反復(fù)篩選上.T(n)=T(建堆)+T(重新構(gòu)堆)對深度為k的堆,篩選算法中進行的關(guān)鍵字的比較次數(shù)至多為2(k-1)(1)建立堆:建立含有n個記錄,深度為h的堆時,總共進行關(guān)鍵字的比較次數(shù)不超過4n,具體請見P282的下批.(2)重新構(gòu)造堆:因為n個結(jié)點的完全二叉樹深度為log2n上取整+1,而調(diào)整建立新堆調(diào)用HeapAdjust過程n-1次,所以總共進行的比較次數(shù)不超過2n(log2n)堆排序算法分析時間困難度:O(nlog2n)空間困難度:O(1)穩(wěn)定性質(zhì):不穩(wěn)定10.5歸并排序歸并排序思想：是又一類不同的排序方法?！皻w并”的含義是將兩個或兩個以上的有序表組合成一個新的有序表。歸并排序過程：假設(shè)初始序列含有n個記錄，則可看成是n個有序的子序列；再兩兩歸并，…，如此重復(fù)，直至得到一個長度為n的有序序列為止，這種方法稱為2-路歸并排序歸并排序特點：比較穩(wěn)定2-路歸并排序核心操作是將一維數(shù)組中前后相鄰的兩個有序序列歸并為一個有序序列2-路歸并排序示例初始關(guān)鍵字[49][38][65][97][76][13][27]一趟歸并之后[3849][6597][1376][27]二趟歸并之后[38496597][132776]三趟歸并之后[13273849657697]算法10.12：VoidMerge(RcdTypeSR[],RcdType&TR[],intm,intn){//將有序的SR[i..m]和SR[m+1..n]歸并為有序的TR[i..n]For(j=m+1,k=i;i<=m&&j<=n;++k){//將SR中記錄由小到大地并入TRifLQ(SR[i].key,SR[j].key)TR[k]=SR[i+1];elseTR[k]=SR[j++];}2-路歸并排序算法if(i<=m)TR[k..n]=SR[i..m];//將剩余的SR[i..m]復(fù)制到TRif(j<=n)TR[k..n]=SR[j..n];//將剩余的SR[j..n]復(fù)制到TR}//Merge算法10.13Voidmsort(RcdtypeSR[],Rcdtype&TR[],ints,intt){//將SR[s..t]歸并排序為TR[s..t];if(s==t)TR1[s]=SR[s];else{m=(s+t)/2;//將SR[s..t]平分為SR[s..m]SR[m+1..t]

MSort(SR,TR2,s,m);//遞歸地將SR[s..m]歸并為TR2[s..m]MSort(SR,TR2,m+1,t);//遞歸地將SR[m+1..t]歸并為TR2[m+1..t]Merge(TR2,TR1,s,m,t);//將TR2[s..m]和TR2[m+1..t]歸并為TR1[s..t]}}算法10.14voidMergeSort(Sqlist&L){//對依次表L進行歸并排序Msort(L.r,L.r,1,L.length);}歸并排序算法分析(1)整個排序須要log2n上取整趟(2)而一趟排序,調(diào)用[n/2h]次算法merge將SR[1..n]中前后相鄰且長度為h的有序段進行兩兩歸并,并且存儲在TR[1..n]中時間困難度:O(nlog2n)空間困難度:O(n)穩(wěn)定性質(zhì):穩(wěn)定基數(shù)排序基數(shù)排序思想：是一種借助多關(guān)鍵字排序的思想對單邏輯關(guān)鍵字進行排序的方法多關(guān)鍵字排序鏈?zhǔn)交鶖?shù)排序最高位優(yōu)先排序（MSD）：先對主關(guān)鍵字進行排序，將序列份成若干個子序列，然后分別就每個子序列對關(guān)鍵字進行排序，依次重復(fù)，直到進行排序之后每個子序列的記錄都具有相同的關(guān)鍵字，再分別對每個子序列進行排序，最終將全部子序列依次聯(lián)接在一起成為有序序列。最低位優(yōu)先法（LSD)：從最次位關(guān)鍵字進行排序，然后再對高一位的關(guān)鍵子進行排序，依次重復(fù)，直至對最高位主關(guān)鍵字進行排序后便成為一個有序序列。多關(guān)鍵字排序鏈?zhǔn)交鶖?shù)排序

基數(shù)排序是借助“支配”和“收集”兩種操作對單邏輯關(guān)鍵字進行排序的一種內(nèi)部排序方法鏈?zhǔn)交鶖?shù)排序示例278109063930e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]930063278109f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]930063278109e[0]e[1]e[2]e[3]