專業(yè)課參考數(shù)據(jù)結(jié)構(gòu)

1第10章內(nèi)部排序2排序：將一個(gè)數(shù)據(jù)元素（記錄）的任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列。 設(shè)：R1，R2，R3，…，Rn

是n個(gè)記錄，k1，k2，k3，…，kn

為它們的關(guān)鍵字，排序就是將記錄按關(guān)鍵字遞增（或遞減）的次序排列起來。常見的排序結(jié)果遞增：ki＜ki+1

遞減：ki＞ki+1

非遞減：ki≤ki+1

非遞增：ki≥ki+110.1排序概述3排序分類按照排序記錄所在的位置分內(nèi)部排序：待排序記錄存放在計(jì)算機(jī)隨機(jī)存儲器中（內(nèi)存）進(jìn)行排序過程。外部排序：待排序記錄數(shù)量很大，內(nèi)存無法一次容納全部記錄，在排序過程中尚需對外存進(jìn)行訪問的排序過程。10.1排序概述4排序分類按照排序依據(jù)的原則分插入排序：直接插入排序、折半插入排序、希爾排序交換排序：冒泡排序、快速排序選擇排序：簡單選擇排序、堆排序歸并排序：2-路歸并排序基數(shù)排序10.1排序概述5排序分類按排序所需工作量簡單的排序方法：T(n)=O(n2)先進(jìn)的排序方法：T(n)=O(nlogn)基數(shù)排序：T(n)=O(d.n)排序基本操作比較兩個(gè)關(guān)鍵字大小。將記錄從一個(gè)位置移動到另一個(gè)位置。10.1排序概述6評價(jià)排序的性能——穩(wěn)定性穩(wěn)定的排序方法：設(shè)在排序前的序列中記錄Ri領(lǐng)先于Rj（即i<j），且Ri、Rj

對應(yīng)的關(guān)鍵字為Ki、Kj，如果Ki＝Kj

并且在排序后的序列中Ri仍領(lǐng)先于Rj，稱所用方法是穩(wěn)定的。不穩(wěn)定的排序方法：排序后的序列中Rj領(lǐng)先于Ri。10.1排序概述待排序列：49,38,65,97,76,13,27,49

排序后:13,27,38,49,49,65,76,97—

穩(wěn)定排序后:13,27,38,49,49,65,76,97—不穩(wěn)定7穩(wěn)定排序的應(yīng)用 例：股票交易系統(tǒng)?？紤]一種股票交易 1)顧客委托：股票編碼、價(jià)格、數(shù)量、買/賣

2)交易原則-價(jià)格高者先成交-價(jià)格相同，按時(shí)間順序成交10.1排序概述按價(jià)格排序

((06,10.5),(09,10),(051,10),(033,9.8))委托隊(duì)列（反映委托提交的時(shí)間先后）

((09,10),(06,10.5),(033,9.8),(051,10))8#defineMAXSIZE20 //順序表的最大長度typedefintKeyType； //定義關(guān)鍵字類型typedefstruct{KeyTypekey; //關(guān)鍵字InfoTypeotherinfo; //其他數(shù)據(jù)項(xiàng)}RedType; //記錄類型10.1排序概述typedefstruct{RedTyper[MAXSIZE+1];//r[0]閑置或作哨兵

intlength;}SqList;9

直接插入排序是一種最簡單的排序方法。 基本思想：將一個(gè)記錄插入到已排好序的有序表中，得到一個(gè)新的、記錄數(shù)增1的有序表。 整個(gè)排序過程為n-1趟插入，即先將序列中第

1

個(gè)記錄看成是一個(gè)有序子序列，然后從第

2

個(gè)記錄開始，逐個(gè)進(jìn)行插入，直至整個(gè)序列有序。10.2插入排序—直接插入排序10直接插入排序10.2插入排序—直接插入排序

在插入第i（i＞1）個(gè)記錄時(shí)，前面的i-1個(gè)記錄已經(jīng)排好序。有序序列無序序列r1r2ri-1rirnri+1…………r'1r'2r'i-1r'i……rnri+1……11直接插入排序10.2插入排序—直接插入排序L.r[0][初始關(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）（1327484949657697）12算法實(shí)現(xiàn)10.2插入排序—直接插入排序StatusInsertSort(SqList&L){for(i=2;i<=L.length;++i)

if(LT(L.r[i].key,L.r[i-1].key))

{L.r[0].key=L.r[i].key;//設(shè)置哨兵

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直接插入排序算法是穩(wěn)定的1310.2插入排序—直接插入排序直接插入排序算法性能分析“移動”次數(shù)=0“比較”次數(shù)=最好的情況（正序序列）“比較”次數(shù)=最壞的情況（逆序序列）

平均復(fù)雜度

O(n2)“移動”次數(shù)==n-11?ni=2i?ni=22)1)(2(-+=nn2+(i-1)?ni=22(n+4)(n-1)=(i+1)?ni=214如何改進(jìn)直接插入排序?10.2插入排序—折半插入排序在插入第i（i＞1）個(gè)記錄時(shí)，前面的i-1個(gè)記錄已經(jīng)排好序，在尋找插入位置時(shí)，可以用折半查找來代替順序查找，從而減少比較次數(shù)。折半插入排序基本思想：用折半查找方法確定插入位置的排序。1510.2插入排序—折半插入排序例i=1(30)1370853942620i=213(1330)70853942620i=76(6133039427085)20…i=820(6133039427085)20sjmi=820(6133039427085)20i=820(6133039427085)20i=820(6133039427085)20i=820(61320

3039427085)sjmjsmsj16希爾排序基本思想 將整個(gè)待排記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對全體記錄進(jìn)行一次直接插入排序。

子序列的構(gòu)成不是簡單的“逐段分割”，而是將相隔某個(gè)“增量”的記錄組成一個(gè)子序列。10.2插入排序—希爾排序17具體實(shí)現(xiàn)辦法 先取一個(gè)正整數(shù)d1<n，把所有相隔d1的記錄放一組，組內(nèi)進(jìn)行直接插入排序；

然后取

d2<d1，重復(fù)上述分組和排序操作；

直至

di=1，即所有記錄放進(jìn)一個(gè)組中排序?yàn)橹埂?0.2插入排序—希爾排序18希爾排序?qū)嵗?假設(shè)：d1=5，d2=3，d3=1。10.2插入排序—希爾排序[初始關(guān)鍵字]：49386597761327495504

49

13

3827

6549

9755

7604一趟排序結(jié)果：13

27

4955

04

49

38

6597

76

13553876

270465

494997二趟排序結(jié)果：13

04

49

38

27

49

55

65

97

76三趟排序結(jié)果:0413273849495565769719 由于在前兩趟的插入排序中，記錄的關(guān)鍵字是與同一子序列中的前一個(gè)記錄的關(guān)鍵字進(jìn)行比較，因此關(guān)鍵字較小的記錄不是一步一步的往前挪動，而是跳躍式的往前移。 在進(jìn)行最后一趟增量為1的插入排序時(shí)，序列已基本有序，只要作記錄的少量比較和移動即可完成排序。因此比直接插入排序快。 希爾排序算法是不穩(wěn)定的排序算法。10.2插入排序—希爾排序20交換排序的基本思想 交換排序的主要操作是交換。 在待排序列中選兩個(gè)記錄，將它們的關(guān)鍵碼相比較，如果反序（即排列順序與排序后的次序正好相反），則交換它們的存儲位置。10.3交換排序—起泡排序反序則交換rirj21起泡排序

兩兩比較相鄰記錄的關(guān)鍵碼，如果反序則交換，直到?jīng)]有反序的記錄為止。10.3交換排序—起泡排序一趟起泡排序無序序列R[1..i]有序序列R[i+1..n]例：49

38659776132749

3849

65761327499722起泡排序

兩兩比較相鄰記錄的關(guān)鍵碼，如果反序則交換，直到?jīng)]有反序的記錄為止。10.3交換排序—起泡排序rj

rj+1ri+1≤……

≤rn-1≤rn

無序區(qū)有序區(qū)1≤j≤i-1已經(jīng)位于最終位置反序則交換23 將第1個(gè)記錄的關(guān)鍵字與第2個(gè)記錄的關(guān)鍵字進(jìn)行比較，若為逆序r[1].key>r[2].key，則交換；

然后比較第2個(gè)記錄與第3個(gè)記錄；依次類推，直至第

n-1個(gè)記錄和第

n個(gè)記錄比較為止——第一趟冒泡排序，結(jié)果關(guān)鍵字最大的記錄被安置在最后一個(gè)（第n個(gè)）記錄上。

對前

n-1個(gè)記錄進(jìn)行第二趟冒泡排序，結(jié)果使關(guān)鍵字次大的記錄被安置在第n-1個(gè)記錄位置。

重復(fù)上述過程，直到“在一趟排序過程中沒有進(jìn)行過交換記錄的操作”為止。 一般：n個(gè)記錄最多進(jìn)行n-1趟冒泡排序。10.3交換排序—起泡排序24例：10.3交換排序—起泡排序初始關(guān)鍵字：4938659776132749第一趟排序后：38496576132749

97第二趟排序后：384965132749

76第三趟排序后：3849132749

65第四趟排序后：3813274949第五趟排序后：13273849第六趟排序后：132738逐步有序25快速排序

在起泡排序中，記錄的比較和移動是在相鄰單元中進(jìn)行的，記錄每次交換只能上移或下移一個(gè)單元，因而總的比較次數(shù)和移動次數(shù)較多。10.3交換排序—快速排序減少總的比較次數(shù)和移動次數(shù)增大記錄的比較和移動距離較大記錄從前面直接移動到后面較小記錄從后面直接移動到前面26基本思想：通過一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小。然后分別對這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序。 一趟快速排序：首先選取一個(gè)記錄（通常選取第一個(gè)記錄）作為界點(diǎn)，然后將所有關(guān)鍵字中比它小的記錄都安置在它的位置之前，將所有關(guān)鍵字比它大的記錄都放在它的位置之后。 由此，以該“界點(diǎn)”記錄最后所落的位置i為分界線，將整個(gè)序列分割成兩個(gè)子序列。10.3交換排序—快速排序27基本思想 選定一記錄，以它的關(guān)鍵字作為“樞軸”，關(guān)鍵字小于樞軸的記錄移至該記錄之前；關(guān)鍵字大于樞軸的記錄移至該記錄之后。

記錄序列R[s..t]被分割成兩部分：R[s..i-1]和R[i+1..t]；繼續(xù)對R前后兩部分記錄進(jìn)行快速排序。10.3交換排序—快速排序無序序列一次劃分樞軸無序子序列1無序子序列2快速排序快速排序28具體算法：

設(shè)兩個(gè)指針low

和high，其初值分別指向數(shù)組的元素1和元素n。 選第1個(gè)記錄為樞軸，關(guān)鍵字為pivotkey。 將pivotkey復(fù)制到r[0]中，從high所指的位置起向前搜索找到第一個(gè)關(guān)鍵字小于pivotkey的記錄，復(fù)制到low所指位置中；然后從low所指位置起向后搜索，找到第一個(gè)關(guān)鍵字大于pivotkey的記錄，復(fù)制到high所指位置中。 重復(fù)這兩步直到low＝high為止。10.3交換排序—快速排序29一趟快速排序算法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[&&].key<=pivotkey)++low;L.r[high]=L.r[low];

}L.r[low]=L.r[0]; //樞軸記錄到位

returnlow; //返回樞軸的位置}//Partition10.3交換排序—快速排序30一趟快速排序的過程10.3交換排序—快速排序012345

6784938659776132749初始關(guān)鍵字pivotkey=49lowhigh012345

6782738659776132749第一次交換lowhigh012345

6782738659776136549第二次交換lowhigh31一趟快速排序的過程10.3交換排序—快速排序012345

6782738139776136549第三次交換lowhigh012345

6782738139776976549第四次交換lowhigh012345

6782738134976976549第一趟完成lowhighpivotkey=49子序列1子序列232快速排序的過程10.3交換排序—快速排序初始狀態(tài){4938659776132749}一趟快速排序后{273813}49{76976549}分別進(jìn)行快速排序{13}27{38}結(jié)束結(jié)束{4965}76{97}49{65}結(jié)束結(jié)束有序序列{1327384949657697}整個(gè)快速排序過程可遞歸進(jìn)行3310.3交換排序—快速排序voidQSort(SqList&L,intlow,inthigh){//對表L中的子序列L.r[low…h(huán)igh]作快速排序

if(low<high)//長度大于1

{pivotloc=Partition(L,low,high);//將L.r[low…h(huán)igh]一分為二

QSort(L,low,pivotloc-1);//對低子表遞歸排序，pivotloc是界點(diǎn)位置

QSort(L,pivotloc+1,high);//對高子表

}}//QSortvoidQuickSort(SqList&L)//對順序表L快速排序{QSort(L,1,L.length);}//QuickSort3410.3交換排序—快速排序快速排序特點(diǎn) 存儲結(jié)構(gòu)：順序 時(shí)間復(fù)雜度為O(nlog2n) 空間復(fù)雜度為O(log2n) 不穩(wěn)定最壞情況：每次劃分選擇樞軸是最小或最大元素

13[…….]最好情況（每次劃分折半）：[…..,]49[……]3510.4選擇排序選擇排序基本思想 每趟排序在當(dāng)前待排序序列中選擇關(guān)鍵碼最小的記錄，添加到有序序列中。有序序列r1r2ri-1rirnrk…………無序序列rnri+1r1r2ri-1……riri……交換最小記錄3610.4選擇排序—簡單選擇排序一趟簡單選擇排序：通過

n-i次關(guān)鍵字間的比較，從n-i+1

個(gè)記錄中選出關(guān)鍵字最小的記錄，并和第i（1<=i<=n）個(gè)記錄交換。voidSelectSort(SqList&L){

for(i=1;i<L.length;++i)

{j=SelectMinKey(L,i);if(i!=j)L.r[i]<=>L.r[j];

}}//SelectSort對于n個(gè)關(guān)鍵字，要進(jìn)行n-1趟選擇排序。3710.4選擇排序—簡單選擇排序例：初始：[49386597761327]ji=11349一趟：13[386597764927]i=2j2738二趟：1327[6597764938]三趟：132738[97764965]四趟：13273849[769765]五趟：1327384965[9776]六趟：132738496576[97]排序結(jié)束：132738496576973810.4選擇排序—簡單選擇排序簡單選擇排序算法的性能分析最壞情況：3(n-1)次移動次數(shù)：最好情況（正序）：0次空間性能：需一個(gè)輔助空間。穩(wěn)定性：是一種穩(wěn)定的排序算法。45231152341253412354123451234比較次數(shù)：=O(n2)21n(n-1)=n-1i=1?（n-i)簡單選擇排序的時(shí)間復(fù)雜度為O(n2)。3910.4選擇排序—堆排序

對排序算法的改進(jìn)改進(jìn)的著眼點(diǎn)：如何減少關(guān)鍵碼之間的比較次數(shù)。若能利用每趟比較后的結(jié)果，也就是在找出鍵值最小記錄的同時(shí)，也找出鍵值較小的記錄，則可減少后面的選擇中所用的比較次數(shù)，從而提高整個(gè)排序過程的效率。減少關(guān)鍵碼間的比較次數(shù)查找最小值的同時(shí)，找出較小值4010.4選擇排序—堆排序堆的定義n個(gè)元素的序列{k1，k2，……，kn}，當(dāng)且僅當(dāng)滿足以下關(guān)系時(shí)，稱之為堆：

ki<=

k2iki>=

k2iki<=

k2i+1ki>=

k2i+1(i=1，2，……，n/2」)或堆是什么東西？與二叉樹的性質(zhì)5有什么關(guān)系？增加了限制條件的完全二叉樹采用一維數(shù)組存儲大根堆小根堆4110.4選擇排序—堆排序或堆的定義：n個(gè)元素的序列{k1，k2，……，kn}，當(dāng)且僅當(dāng)滿足以下關(guān)系時(shí)，稱之為堆：

ki<=

k2iki>=

k2iki<=

k2i+1ki>=

k2i+1(i=1，2，……，n/2」)

堆的含義表明，完全二叉樹中所有非終端結(jié)點(diǎn)的值均不大于（或不小于）其左、右孩子結(jié)點(diǎn)的值。因此若序列{k1，k2，……，kn}是堆，則堆頂元素必為序列中n個(gè)元素的最小值（或最大值）。4210.4選擇排序—堆排序堆的定義堆是具有下列性質(zhì)的完全二叉樹：每個(gè)結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值（稱為小根堆），或每個(gè)結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值（稱為大根堆）。182032364525385040281.小根堆的根結(jié)點(diǎn)是所有結(jié)點(diǎn)的最小者。2.較小結(jié)點(diǎn)靠近根結(jié)點(diǎn)，但不絕對。4310.4選擇排序—堆排序堆的定義堆是具有下列性質(zhì)的完全二叉樹：每個(gè)結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值（稱為小根堆），或每個(gè)結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值（稱為大根堆）。503845402836322018281.大根堆的根結(jié)點(diǎn)是所有結(jié)點(diǎn)的最大者。2.較大結(jié)點(diǎn)靠近根結(jié)點(diǎn)，但不絕對。4410.4選擇排序—堆排序堆與序列的關(guān)系50384540283632201828將堆用順序存儲結(jié)構(gòu)來存儲，則堆對應(yīng)一組序列。5038453236402820182812345678910采用順序存儲45§10.4選擇排序—堆排序堆排序96911832723145124785913624533062731845可將堆序列看成完全二叉樹，則堆頂元素（完全二叉樹的根）必為序列中n個(gè)元素的最小值或最大值。4610.4選擇排序—堆排序堆排序基本思想：首先將待排序的記錄序列構(gòu)造成一個(gè)堆，此時(shí)，選出了堆中所有記錄的最小者，然后將它從堆中移走，并將剩余的記錄再調(diào)整成堆，這樣又找出了次小的記錄，以此類推，直到堆中只有一個(gè)記錄。

需解決的關(guān)鍵問題?⑴如何由一個(gè)無序序列建成一個(gè)堆（即初始建堆）？⑵如何處理堆頂記錄？⑶如何調(diào)整剩余記錄，成為一個(gè)新堆（即重建堆）？

4710.4選擇排序—堆排序

堆排序：在輸出堆頂?shù)淖钚≈抵?，使得剩余n-1個(gè)元素的序列重又建成一個(gè)堆，則得到n個(gè)元素中的次小值。如此反復(fù)執(zhí)行，得到有序序列。如何由一個(gè)無序序列建成一個(gè)堆？如何在輸出堆頂元素之后調(diào)整剩余元素成為一個(gè)新的堆？4810.4選擇排序—堆排序137650973827496562731845用堆中最后一個(gè)元素替代根765097382749656273145765027389749656273145765027384997656273145769750493865623145

輸出堆頂元素之后，以堆中最后一個(gè)元素替代之；然后將根結(jié)點(diǎn)值與左、右子樹的根結(jié)點(diǎn)值進(jìn)行比較，并與其中小者進(jìn)行交換；重復(fù)上述操作，直至葉子結(jié)點(diǎn)，將得到新的堆，稱這個(gè)從堆頂至葉子的調(diào)整過程為“篩選”。進(jìn)行篩選繼續(xù)篩選繼續(xù)輸出4910.4選擇排序—堆排序13273849657650979727384965765013輸出：132749389765765013輸出：139749382765765013輸出：13273849502765769713輸出：13276549502738769713輸出：1327385010.4選擇排序—堆排序4965502738769713輸出：1327387665502738499713輸出：132738495065762738499713輸出：132738499765762738495013輸出：13273849506597762738495013輸出：13273849509765762738495013輸出：1327384950655110.4選擇排序—堆排序7665972738495013輸出：1327384950659765762738495013輸出：132738495065769765762738495013輸出：13273849506576975210.4選擇排序—堆排序從一個(gè)無序序列建堆的過程就是一個(gè)反復(fù)“篩選”的過程。若將此序列看成是一個(gè)完全二叉樹，則最后一個(gè)非終端結(jié)點(diǎn)是第n/2」個(gè)元素，由此篩選只需從第n/2」個(gè)元素開始。5310.5歸并排序歸并：將兩個(gè)或兩個(gè)以上的有序表組合成一個(gè)新的有序表。

2-路歸并排序：設(shè)初始序列含有n個(gè)記錄，則可看成

n個(gè)有序的子序列，每個(gè)子序列長度為1。

兩兩合并，得到

n/2個(gè)長度為

2

或1的有序子序列。

再兩兩合并，……如此重復(fù)，直至得到一個(gè)長度為

n的有序序列為止。5410.5歸并排序例初始關(guān)鍵字：[49][38][65][97][76][13][27]一趟歸并后：[3849][6597][1376][27]二趟歸并后：[38496597][132776]三趟歸并后：[13273849657697]5510.6基數(shù)排序基數(shù)排序 借助多關(guān)鍵字排序的方法對單關(guān)鍵字排序。 包含多位k=k1,k2,…,kd的單關(guān)鍵字 多關(guān)鍵字排序 最高位優(yōu)先 最低位優(yōu)先5610.6基數(shù)排序例：對52張撲克牌排序 <梅花,2><梅花,3>…<梅花,A> <方塊,2><方塊,3>…<方塊,A> <紅桃,2><紅桃,3>…<紅桃,A> <黑桃,2><黑桃,3>…<黑桃,A>排序方法先按花色分類，再按面值分類先按面值分類，再按花色分類5710.6基數(shù)排序最高位優(yōu)先按花色（最高位）分堆梅花：13張方塊：13張紅桃：13張黑桃：13張 每一堆按面值從小到大排列<梅花,2><梅花,3>…<梅花,A><方塊,2><方塊,3>…<方塊,A><紅桃,2><紅桃,3>…<紅桃,A><黑桃,2><黑桃,3>…<黑桃,A>5810.6基數(shù)排序最低位優(yōu)先 分配（按面值）

<梅花,2><梅花,3>…<梅花,A><方塊,2><方塊,3>…<方塊,A><紅桃,2><紅桃,3>…<紅桃,A><黑桃,2><黑桃,3>…<黑桃,A> 收集（按面值有序）

2：4張，3：4張，4：4張…A：4張5910.6基數(shù)排序分配（按花色）<梅花,2><方塊,2><紅桃,2><黑桃,2><梅花,3><方塊,3><紅桃,3><黑桃,3>……<梅花,A><方塊,A><紅桃