大一下相關(guān)課程課件數(shù)據(jù)結(jié)構(gòu)

第10章內(nèi)部排序李巖信息與電子學(xué)院-雷達(dá)與對(duì)抗技術(shù)研究所

本章內(nèi)容10.1概述10.2插入排序直接插入排序其他插入排序：折半插入排序、表插入排序希爾排序10.3快速排序10.4選擇排序簡(jiǎn)單選擇排序堆排序3一、排序的定義二、內(nèi)部排序和外部排序三、內(nèi)部排序方法的分類(lèi)10.1概述4一、什么是排序？排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一組“無(wú)序”的記錄序列調(diào)整為“有序”的記錄序列。例如：將下列關(guān)鍵字序列52,49,80,36,14,58,61,23,97,75調(diào)整為14,23,36,49,52,58,61,75,80,9710.1概述5一般情況下，假設(shè)含n個(gè)記錄的序列為{R1,R2,…，Rn}，其相應(yīng)的關(guān)鍵字序列為{K1,K2,…，Kn}這些關(guān)鍵字相互之間可以進(jìn)行比較，即在它們之間存在著這樣一個(gè)關(guān)系：

Kp1≤Kp2≤…≤Kpn按此固有關(guān)系將上式記錄序列重新排列為

{Rp1,Rp2,

…，Rpn}的操作稱(chēng)作排序。10.1概述6二、內(nèi)部排序和外部排序若整個(gè)排序過(guò)程不需要訪(fǎng)問(wèn)外存便能完成，則稱(chēng)此類(lèi)排序問(wèn)題為內(nèi)部排序；反之，若參加排序的記錄數(shù)量很大，整個(gè)序列的排序過(guò)程不可能在內(nèi)存中完成，則稱(chēng)此類(lèi)排序問(wèn)題為外部排序。10.1概述7三、內(nèi)部排序的方法內(nèi)部排序的過(guò)程是一個(gè)逐步擴(kuò)大記錄的有序序列長(zhǎng)度的過(guò)程。經(jīng)過(guò)一趟排序有序序列區(qū)無(wú)序序列區(qū)有序序列區(qū)無(wú)序序列區(qū)10.1概述8基于不同的“擴(kuò)大”有序序列長(zhǎng)度的方法，內(nèi)部排序方法大致可分下列幾種類(lèi)型：插入類(lèi)交換類(lèi)選擇類(lèi)歸并類(lèi)其它方法10.1概述91.插入類(lèi)將無(wú)序子序列中的一個(gè)或幾個(gè)記錄“插入”到有序序列中，從而增加記錄的有序子序列的長(zhǎng)度。10.1概述102.交換類(lèi)通過(guò)“交換”無(wú)序序列中的記錄從而使得關(guān)鍵字最小或最大的記錄逐漸移至有序子序列中，以此方法增加記錄的有序子序列的長(zhǎng)度。10.1概述113.選擇類(lèi)從記錄的無(wú)序子序列中“選擇”關(guān)鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長(zhǎng)度。10.1概述124.歸并類(lèi)通過(guò)“歸并”兩個(gè)或兩個(gè)以上的記錄有序子序列，逐步增加記錄有序序列的長(zhǎng)度。10.1概述13待排記錄的數(shù)據(jù)類(lèi)型定義如下:#defineMAXSIZE1000//待排順序表最大長(zhǎng)度typedefintKeyType;//關(guān)鍵字類(lèi)型為整數(shù)類(lèi)型typedefstruct{KeyTypekey;//關(guān)鍵字項(xiàng)

InfoTypeotherinfo;//其它數(shù)據(jù)項(xiàng)}RcdType;//記錄類(lèi)型typedefstruct{RcdTyper[MAXSIZE+1];//r[0]閑置

intlength;//順序表長(zhǎng)度}SqList;//順序表類(lèi)型14有序序列R[1..i-1]R[i]無(wú)序序列R[i..n]一趟直接插入排序的基本思想：有序序列R[1..i]無(wú)序序列R[i+1..n]10.2插入排序15實(shí)現(xiàn)“一趟插入排序”可分三步進(jìn)行：3．將R[i]插入(復(fù)制)到R[j+1]的位置上。2．將R[j+1..i-1]中的所有記錄均后移一個(gè)位置；1．在R[1..i-1]中查找R[i]的插入位置，

R[1..j].keyR[i].key<R[j+1..i-1].key；10.2插入排序16直接插入排序（基于順序查找）表插入排序（基于鏈表存儲(chǔ)）不同的具體實(shí)現(xiàn)方法導(dǎo)致不同的算法描述折半插入排序（基于折半查找）希爾排序（基于逐趟縮小增量）10.2插入排序17一、直接插入排序利用

“順序查找”實(shí)現(xiàn)“在R[1..i-1]中查找R[i]的插入位置”10.2插入排序18從R[i-1]起向前進(jìn)行順序查找，監(jiān)視哨設(shè)置在R[0]；R[0]=R[i];//設(shè)置“哨兵”R[0]jR[i]for(j=i-1;R[0].key<R[j].key;--j);

//從后往前找，循環(huán)結(jié)束表明R[i]的插入位置為j+1j=i-1插入位置10.2插入排序19對(duì)于在查找過(guò)程中找到的那些關(guān)鍵字不小于R[i].key的記錄，并在查找的同時(shí)實(shí)現(xiàn)記錄向后移動(dòng)；for(j=i-1;R[0].key<R[j].key;--j)

R[j+1]=R[j]R[0]jR[i]j=i-1上述循環(huán)結(jié)束后可以直接進(jìn)行“插入”插入位置10.2插入排序20令i=2，3，…,n,實(shí)現(xiàn)整個(gè)序列的排序。for(i=2;i<=n;++i)

if(R[i].key<R[i-1].key)

{在

R[1..i-1]中查找R[i]的插入位置;

插入R[i];

}如：1、2、4、3…..10.2插入排序21voidInsertionSort(SqList&L){

//對(duì)順序表L作直接插入排序。

for(i=2;i<=L.length;++i)if(L.r[i].key<L.r[i-1].key){

}}//InsertSortL.r[0]=L.r[i];//復(fù)制為監(jiān)視哨for(j=i-1;L.r[0].key<L.r[j].key;--j)L.r[j+1]=L.r[j];//記錄后移L.r[j+1]=L.r[0];//插入到正確位置10.2插入排序22因?yàn)镽[1..i-1]是一個(gè)按關(guān)鍵字有序的有序序列，則可以利用折半查找實(shí)現(xiàn)“在R[1..i-1]中查找R[i]的插入位置”，如此實(shí)現(xiàn)的插入排序?yàn)檎郯氩迦肱判?。二、折半插入排?0.2插入排序23voidBiInsertionSort(SqList&L){}//BInsertSort在L.r[1..i-1]中折半查找插入位置；for(i=2;i<=L.length;++i){}//forL.r[0]=L.r[i];//將L.r[i]暫存到L.r[0]for(j=i-1;j>=high+1;--j)L.r[j+1]=L.r[j];//記錄后移L.r[high+1]=L.r[0];//插入10.2插入排序24low=1;high=i-1;while

(low<=high)

{}m=(low+high)/2;//折半if

(L.r[0].key<L.r[m].key)

high=m-1;

//插入點(diǎn)在低半?yún)^(qū)else

low=m+1;

//插入點(diǎn)在高半?yún)^(qū)10.2插入排序2514364952805861239775ilowhighmmlowlowmhigh14364952586180239775ilowhighmhighmhighmlow例如:再如:插入位置插入位置L.rL.r10.2插入排序26三、表插入排序?yàn)榱藴p少在排序過(guò)程中進(jìn)行的“移動(dòng)”記錄的操作，必須改變排序過(guò)程中采用的存儲(chǔ)結(jié)構(gòu)。利用靜態(tài)鏈表進(jìn)行排序，并在排序完成之后，一次性地調(diào)整各個(gè)記錄相互之間的位置，即將每個(gè)記錄都調(diào)整到它們所應(yīng)該在的位置上。10.2插入排序27四、希爾排序（又稱(chēng)縮小增量排序）基本思想：對(duì)待排記錄序列先作“宏觀”調(diào)整，再作“微觀”調(diào)整。所謂“宏觀”調(diào)整，指的是“跳躍式”的插入排序。10.2插入排序28將記錄序列分成若干子序列，分別對(duì)每個(gè)子序列進(jìn)行直接插入排序。其中，d

稱(chēng)為增量，它的值在排序過(guò)程中從大到小逐漸縮小，直至最后一趟排序減為1。例如：將n個(gè)記錄分成d個(gè)子序列：

{R[1]，R[1+d]，R[1+2d]，…，R[1+kd]}{R[2]，R[2+d]，R[2+2d]，…，R[2+kd]}…{R[d]，R[2d]，R[3d]，…，R[kd]，R[(k+1)d]}10.2插入排序29例如：162512304711233691831

第一趟希爾排序，設(shè)增量d=51123

12

9

181625

36

30

4731

第二趟希爾排序，設(shè)增量d=3918

121123

162531

304736第三趟希爾排序，設(shè)增量d=1

91112161823253031364730一、起泡排序假設(shè)在排序過(guò)程中，記錄序列R[1..n]的狀態(tài)為：第i趟起泡排序無(wú)序序列R[1..n-i+1]有序序列R[n-i+2..n]n-i+1無(wú)序序列R[1..n-i]有序序列R[n-i+1..n]比較相鄰記錄，將關(guān)鍵字最大的記錄交換到

n-i+1的位置上10.3快速排序31voidBubbleSort(ElemR[],intn){

while(i>1){

}

//while}//BubbleSorti=n;i=lastExchangeIndex;//本趟進(jìn)行過(guò)交換的

//最后一個(gè)記錄的位置if(R[j+1].key<R[j].key)

{

Swap(R[j],R[j+1]);

lastExchangeIndex=j;//記下進(jìn)行交換的記錄位置

}

//iffor(j=1;j<i;j++)lastExchangeIndex=1;32注意:2.一般情況下，每經(jīng)過(guò)一趟“起泡”，“i減1”，但并不是每趟都如此。例如:2553157989i=7i=6for(j=1;j<i;j++)if(R[j+1].key<R[j].key)…13i=21.起泡排序的結(jié)束條件為：最后一趟沒(méi)有進(jìn)行“交換記錄”。10.3快速排序33二、一趟快速排序（一次劃分）目標(biāo)：找一個(gè)記錄，以它的關(guān)鍵字作為“樞軸”，凡其關(guān)鍵字小于樞軸的記錄均移動(dòng)至該記錄之前，反之，凡關(guān)鍵字大于樞軸的記錄均移動(dòng)至該記錄之后。致使一趟排序之后，記錄的無(wú)序序列R[s..t]將分割成兩部分：R[s..i-1]和R[i+1..t]，且

R[j].key≤R[i].key≤R[j].key

(s≤j≤i-1)樞軸(i+1≤j≤t)。10.3快速排序34stlowhigh設(shè)R[s]=52為樞軸將R[high].key和樞軸的關(guān)鍵字進(jìn)行比較，要求R[high].key≥樞軸的關(guān)鍵字將R[low].key和樞軸的關(guān)鍵字進(jìn)行比較，要求R[low].key≤樞軸的關(guān)鍵字high23low80high14low52例如R[0]52lowhighhighhighlow10.3快速排序35

可見(jiàn)，經(jīng)過(guò)“一次劃分”，將關(guān)鍵字序列

52,49,80,36,14,58,61,97,23,75調(diào)整為:23,49,14,36,(52)58,61,97,80,75在調(diào)整過(guò)程中，設(shè)立了兩個(gè)指針：low

和high，它們的初值分別為：s和t，之后逐漸減小high，增加low，并保證R[high].key≥52，和R[low].key≤52,否則進(jìn)行記錄的“交換”。10.3快速排序36intPartition(RedTypeR[],intlow,inthigh)

{}//PartitionR[0]=R[low];pivotkey=R[low].key;//樞軸while(low<high){}while(low<high&&

R[high].key>=pivotkey)--high;//從右向左搜索R[low]=R[high];while(low<high&&

R[low].key<=pivotkey)++low;//從左向右搜索R[high]=R[low];R[low]=R[0];

returnlow;10.3快速排序37三、快速排序首先對(duì)無(wú)序的記錄序列進(jìn)行“一次劃分”，之后分別對(duì)分割所得兩個(gè)子序列“遞歸”進(jìn)行快速排序。無(wú)序的記錄序列無(wú)序記錄子序列(1)無(wú)序子序列(2)樞軸一次劃分分別進(jìn)行快速排序10.3快速排序38voidQSort(RedType&R[],ints,intt){//對(duì)記錄序列R[s..t]進(jìn)行快速排序

if(s<t){//長(zhǎng)度大于1

}}//QSortpivotloc=Partition(R,s,t);//對(duì)R[s..t]進(jìn)行一次劃分QSort(R,s,pivotloc-1);//對(duì)低子序列遞歸排序QSort(R,pivotloc+1,t);//對(duì)高子序列遞歸排序10.3快速排序39voidQuickSort(SqList&L){//對(duì)順序表進(jìn)行快速排序

QSort(L.r,1,L.length);}//QuickSort第一次調(diào)用函數(shù)Qsort時(shí)，待排序記錄序列的上、下界分別為1和L.length。10.3快速排序40一、簡(jiǎn)單選擇排序假設(shè)排序過(guò)程中，待排記錄序列的狀態(tài)為：有序序列R[1..i-1]無(wú)序序列R[i..n]

第i趟簡(jiǎn)單選擇排序從中選出關(guān)鍵字最小的記錄有序序列R[1..i]無(wú)序序列

R[i+1..n]10.4選擇排序41簡(jiǎn)單選擇排序的算法描述如下：voidSelectSort(ElemR[],intn){//對(duì)記錄序列R[1..n]作簡(jiǎn)單選擇排序。

for(i=1;i<n;++i){

//選擇第i小的記錄，并交換到位

}}//SelectSortj=SelectMinKey(R,i);

//在R[i..n]中選擇關(guān)鍵字最小的記錄if(i!=j)R[i]←→R[j];//與第i個(gè)記錄交換10.4選擇排序42二、堆排序堆是滿(mǎn)足下列性質(zhì)的數(shù)列{r1,r2,…，rn}：或堆的定義:{12,36,27,65,40,34,98,81,73,55,49}例如:是小頂堆{12,36,27,65,40,14,98,81,73,55,49}不是堆(小頂堆)(大頂堆)10.4選擇排序43rir2ir2i+1若將該數(shù)列視作完全二叉樹(shù)，則r2i

是ri

的左孩子；r2i+1

是ri

的右孩子。1236276549817355403498例如:是堆14不10.4選擇排序44堆排序即是利用堆的特性對(duì)記錄序列進(jìn)行排序的一種排序方法。例如：建大頂堆{98,81,49,73,36,27,40,55,64,12}{12,81,49,73,36,27,40,55,64,98}交換98和12重新調(diào)整為大頂堆{81,73,49,64,36,27,40,55,12,98}{40,55,49,73,12,27,98,81,64,36}經(jīng)過(guò)篩選10.4選擇排序45如何由一個(gè)無(wú)序序列構(gòu)建堆？?jī)蓚€(gè)問(wèn)題:如何在輸出堆頂元素后，調(diào)整剩余元素成為新堆？定義堆類(lèi)型為:typedefSqListHeapType;//堆采用順序表表示之10.4選擇排序46所謂“篩選”指的是，對(duì)一棵左/右子樹(shù)均為堆的完全二叉樹(shù)，“調(diào)整”根結(jié)點(diǎn)使整個(gè)二叉樹(shù)也成為一個(gè)堆。堆堆篩選10.4選擇排序4798814973556412362740例如:是大頂堆12但在98和12進(jìn)行互換之后，它就不是堆了，因此，需要對(duì)它進(jìn)行“篩選”。98128173641298比較比較10.4選擇排序48建堆是一個(gè)從下往上進(jìn)行“篩選”的過(guò)程。40554973816436122798例如:排序之前的關(guān)鍵字序列為123681734998817355

現(xiàn)在，左/右子樹(shù)都已經(jīng)調(diào)整為堆，最后只要調(diào)整根結(jié)點(diǎn)，使整個(gè)二叉樹(shù)是個(gè)“堆”即可。9849406436122710.4選擇排序49一、時(shí)間性能1.平均的時(shí)間性能基數(shù)排序時(shí)間復(fù)雜度為O(nlogn)：快速排序、堆排序和歸并排序時(shí)間復(fù)雜度為O(n2)：直接插入排序、折半插入排序、表插入排序、起泡排序和簡(jiǎn)單選擇排序時(shí)間復(fù)雜度為O(n):10.7各種內(nèi)部排序方法的比較502.當(dāng)待排記錄序列按關(guān)鍵字順序有序時(shí)3.簡(jiǎn)單選擇排序、堆排序和歸并排序的時(shí)間性能不隨記錄序列中關(guān)鍵字的分布而改變。直接插入排序和起泡排序能達(dá)到O(n)的時(shí)間復(fù)雜度，快速排序的時(shí)間性能蛻化為O(n2)

。10.7各種內(nèi)部排序方法的比較51二、空間性能指的是排序過(guò)程中所需的輔助空間大小1.

所有的簡(jiǎn)單排序方法(包括：直接插入、起泡和簡(jiǎn)單選擇)和堆排序的空間復(fù)雜度為O(1)；2.

快速排序?yàn)镺(logn)，為遞歸程序執(zhí)行過(guò)程中，棧所需的輔助空間；10.7各種內(nèi)部排序方法的比較3.

歸并排序所需輔助空間最多，其空間復(fù)雜度為O(n);4.鏈?zhǔn)交鶖?shù)排序需附設(shè)隊(duì)列首尾指針，則空間復(fù)雜度為O(rd)。52三、排序方法的穩(wěn)定性能1.

穩(wěn)定的排序方法指的是，對(duì)于兩個(gè)關(guān)鍵字相等的記錄，它們?cè)谛蛄兄械南鄬?duì)位置，在排序之前和經(jīng)過(guò)排序之后，沒(méi)有改變。2.

當(dāng)對(duì)多關(guān)鍵字的記錄序列進(jìn)行排序時(shí)，必須采用穩(wěn)定的排序方法。排序之前:{··