數(shù)據(jù)結(jié)構(gòu)講義-內(nèi)部排序

2023/2/191數(shù)據(jù)結(jié)構(gòu)(DataStructure)2023/2/192第十章內(nèi)部排序10.1概述10.2插入排序10.3快速排序10.4選擇排序10.5歸并排序10.6基數(shù)排序10.7各種內(nèi)部排序方法的比較討論2023/2/1931、什么是排序？排序是將無序的記錄序列調(diào)整為有序記錄序列的一種操作。

如：將如下序列

{10，64，34，47，57，48，58}

調(diào)整為：

{10，34，47，48，57，58，64}

10.1概述2023/2/1942、穩(wěn)定性與不穩(wěn)定性對(duì)于序列：27，21，27，31穩(wěn)定的排序方法 排序結(jié)果：21，27，27，31不穩(wěn)定的方法 排序結(jié)果：21，27，27，3110.1概述2023/2/1953、排序的種類

根據(jù)在排序過程中涉及的存儲(chǔ)器不同，可將排序方法分為兩大類：1)內(nèi)部排序:待排序記錄存放在計(jì)算機(jī)RAM中。2)外部排序：部分記錄放在外在，排序過程中尚需對(duì)外在進(jìn)行訪問。本章僅討論各種內(nèi)部排序的方法。10.1概述2023/2/19610.1概述4、內(nèi)部排序的方法1）按排序過程依據(jù)的不同原則分為5類：（1）插入排序（2）交換排序（3）選擇排序

(4)歸并排序（5）基數(shù)排序2）按排序過程所需的工作量分為3類：（1）簡(jiǎn)單排序方法，時(shí)間復(fù)雜度為O（n2)（1）先進(jìn)排序方法，時(shí)間復(fù)雜度為O（nlogn)（1）基數(shù)排序方法，時(shí)間復(fù)雜度為O（d·n)2023/2/1975、排序的兩種基本操作：（1）比較兩個(gè)關(guān)鍵字的大?。唬?）將記錄從一個(gè)位置移動(dòng)到另一個(gè)位置。6、待排序記錄序列的3種存儲(chǔ)方式：（1）存放在地址連續(xù)的一組存儲(chǔ)單元上，排序時(shí)需移動(dòng)記錄。（2）存放在靜態(tài)鏈表中，排序時(shí)不需移動(dòng)記錄，僅需修改指針。（3）存放在地址連續(xù)的一組存儲(chǔ)單元內(nèi)，另設(shè)一個(gè)各記錄存儲(chǔ)位置的地址向量，排序時(shí)僅需移動(dòng)地址向量中記錄的“地址”，不需移動(dòng)記錄本身。10.1概述2023/2/19810.1概述7、本章使用的待排記錄的數(shù)據(jù)類型

#defineMAXSIZE20

typedef

int

KeyType;

typedef

struct{

KeyTypekey;

InfoType

otherinfo;}RedType

typedef

struct{

RedTyper[MAXSIZE+1];

intlength;}Sqlist;2023/2/199插入排序的基本方法：每步將一個(gè)待排序的對(duì)象，按其關(guān)鍵碼大小，插入到前面已經(jīng)排好序的一組對(duì)象的適當(dāng)位置上，直到對(duì)象全部插入為止。10.2插入排序2023/2/1910直接插入排序(StraightInsertionSort)的基本思想是：當(dāng)插入第i(i1)個(gè)對(duì)象時(shí)，前面的R[0],R[1],…,R[i-1]已經(jīng)排好序。這時(shí)，用R[i]的關(guān)鍵碼與R[i-1],R[i-2],…的關(guān)鍵碼順序進(jìn)行比較，找到插入位置即將R[i]插入，原來位置上的對(duì)象向后順移。10.2.1直接插入排序2023/2/1911

直接插入排序一趟插入排序的過程

1)在R[1..i-1]

中查找R[i]

的插入位置，即確定j(1≤j＜i)使得

R[1..j].key≤R[i].key＜R[j+1..i-1].key2)將R[j+1..i-1]

中的記錄后移一個(gè)位置；

3)將R[i]

插入到j(luò)+1的位置。10.2.1直接插入排序2023/2/1912對(duì)順序表L作直接插入排序void

InsertSort(SqList

&L){

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

if(L.r[i].key<L.r[i-1].key){

L.r[0]=L.r[i];L.r[i]=L.r[i-1];

for(j=i-2;L.r[0].key<L.r[j].key;--j)

L.r[j+1]=L.r[j];

L.r[j+1]=L.r[0];

}//if

}//InsertSort

10.2.1直接插入排序2023/2/1913直接插入排序演示4938659776132749i=200監(jiān)視哨L.r[0]i=3383849初始關(guān)鍵字i=4i=5769776i=61365i=727i=849for(i=2;i<=L.length;++i)

if(L.r[i].key<L.r[i-1].key){

L.r[0]=L.r[i];L.r[i]=L.r[i-1];

for(j=i-2;L.r[0].key<L.r[j].key;--j)

L.r[j+1]=L.r[j];

L.r[j+1]=L.r[0];

}//if

2023/2/1914排序中的兩個(gè)基本操作是：（關(guān)鍵字間的）比較和（記錄的）移動(dòng)。因此排序的時(shí)間性能取決于排序過程中這兩個(gè)操作的次數(shù)。這兩個(gè)操作的次數(shù)取決于待排記錄序列的狀態(tài)“正序”時(shí)，比較(n-1).

移動(dòng)0次?！澳嫘颉睍r(shí)，比較（n+2）(n-1)/2.

移動(dòng)(n+4)(n-1)/2。隨機(jī)狀態(tài)，取最壞和最好的情況的平均值。一般情況下，直接插入排序的時(shí)間復(fù)雜度O(n*n)。

插入排序--算法分析2023/2/1915在直接插入排序的基礎(chǔ)上，從減少“比較”和“移動(dòng)”的次數(shù)著眼，有如下插入排序方法：

折半插入排序:記錄移動(dòng)次數(shù)

0—(n+4)(n-1)/2

2-路插入排序:記錄移動(dòng)次數(shù)n2/8

表插入排序:可以不移動(dòng)記錄，修改2n次指針。10.2.2其他插入排序2023/2/19161.對(duì)順序表L作折半插入排序voidBInsertSort(SqList&L)

{

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

{

L.r[0]=L.r[i];

low=1;high=i-1;

while(low<=high)

{

m=(low+high)/2;

if

(L.r[0].key<L.r[m].key)high=m-1;

elselow=m+1;

}//while

for(j=i-1;j>=low;--j)

L.r[j+1]=L.r[j];

L.r[high+1]=L.r[0];

}

}//BInsertSort2023/2/19172.2-路插入排序2-路插入排序是在折半插入排序的基礎(chǔ)上改進(jìn)而來，目的是減少排序過程中移動(dòng)記錄的次數(shù)。需增加n個(gè)記錄的輔助空間。方法：另設(shè)一個(gè)和L.r同類型的數(shù)組d，先將L.r[1]賦值給d[1]，并把d[1]看成是排好序中處于中間位置的記錄，然后從L.r

中第2個(gè)記錄起依次插入到d[1]之前或之后的有序序列中。可將d看成是一個(gè)循環(huán)向量，并設(shè)兩個(gè)指針first和final分別指示排序過程中第一個(gè)和最后一個(gè)記錄在d中的位置。2023/2/1918初始關(guān)鍵字4938659776132749排序過程中d的狀態(tài)如下i=149firstfinal386597i=2i=3i=476i=5i=61327i=7i=8492-路插入排序演示2023/2/1919移動(dòng)記錄次數(shù)約為。因此2-路插入排序只能減少移動(dòng)記錄的次數(shù)，不能避免移動(dòng)記錄。并且，當(dāng)L.r[1]是待排記錄中關(guān)鍵字最小或最大的記錄時(shí)，2-路插入排序失去優(yōu)越性。因此若希望在排序過程中不移動(dòng)記錄，只有改變存儲(chǔ)結(jié)構(gòu)，進(jìn)行表插入排序。

2-路插入排序算法分析2023/2/1920表插入排序是以靜態(tài)鏈表作待排記錄序列的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的插入排序。表插入排序分兩步進(jìn)行：首先構(gòu)造一個(gè)有序鏈表；然后按照“附加指針”的指示將結(jié)點(diǎn)中的記錄重新排列成一個(gè)有序序列。

3.

表插入排序2023/2/1921初始狀態(tài)49MAXINT3865977613491001234567278KEY

域NEXT域i=221i=303i=440i=554i=662i=772i=883初始狀態(tài)49MAXINT3865977613491(7)01234567278i=251i=30(6)i=4(7)0i=554i=662i=77283下面是重排過程i=1P=649P=727P=(2),77813493838651P=(1),6978(6)P=8497634(8)P=(3),7659705(7)P=(5),8977640(8)

表插入排序演示2023/2/1922根據(jù)Next[]中的指針值調(diào)整記錄位置，使得L中記錄按關(guān)鍵字非遞減有序順序排列（P270-271)voidArrange(SqList&L，intNext[])

{

p=Next[0];

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

{

while(p<i)p=Next[p];

q=Next[p];

if(p!=i){

L.r[p]←→L.r[i];

Next[i]=p;

}//if

p=q;

}//for

}//Arrange

2023/2/1923表插入排序以修改2n次指針代替移動(dòng)記錄，其他與直接插入排序相同。因此，時(shí)間復(fù)雜度仍是O(n*n)。重排記錄過程中，最壞情況是每個(gè)記錄到位都進(jìn)行交換，即3次移動(dòng)記錄，所以重排記錄至多需進(jìn)行3(n-1)

次記錄的移動(dòng)，不增加表插入排序的時(shí)間復(fù)雜度。表插入排序算法分析2023/2/1924希爾排序又稱“縮小增量排序”，它的基本思想是：

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

希爾排序示例：P271增量等于5的插入排序49386597761327495504增量等于3的插入排序1327495504493865977613044938274955659776增量等于1的插入排序10.2.3希爾排序2023/2/1926對(duì)順序表L作一趟增量為dk的希爾排序

voidShellInsert(SqList&L，int

dk)

{

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

if(L.r[i].key<L.r[i-dk].key){

L.r[0]=L.r[i];L.r[i]=L.r[i-dk];

for(j=i-2*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];

}//if

}//ShellInsert2023/2/1927對(duì)順序表L作一趟增量為dk的希爾排序voidShellSort(SqList&L,int

dlta[],intt)

{//按增量序列dlta[0..t-1]

對(duì)順序表L作希爾排序

for(k=0;k<t;++k)

ShellInsert(L,dlta[k]);//一趟增量為dlta[k]的插入排序

}//ShellSort2023/2/1928

希爾排序的時(shí)間復(fù)雜度分析是一個(gè)相當(dāng)復(fù)雜的問題，因?yàn)樗退≡隽啃蛄邢嚓P(guān)。目前已有一些局部性結(jié)論。 例如已有學(xué)者證明，當(dāng)增量序列為

2t-k-1(k=0,1,…，t-1)時(shí)，希爾排序的時(shí)間復(fù)雜度為O(n3/2)。希爾排序算法分析2023/2/1929起泡排序是交換類排序方法中的一種簡(jiǎn)單排序方法。其基本思想為：依次比較相鄰兩個(gè)記錄的關(guān)鍵字，若和所期望的相反，則互換這兩個(gè)記錄。10.3快速排序--起泡排序2023/2/1930對(duì)順序表L作起泡排序

void

BubbleSort(SqList

&L)

{

for(i=L.length,change=TRUE;i>1&&change;--i)

{change=FALSE;

for(j=1;j<i;++j)

if(L.r[j].key>L.r[j+1].key)

{L.r[j]←→L.r[j+1];change=TRUE}

}//fori

}//BubbleSort2023/2/19314938659776132749初始關(guān)鍵字第一趟排序第二趟排序第三趟排序第四趟排序第五趟排序第六趟排序排序完成10.3快速排序--起泡排序演示2023/2/1932當(dāng)待排序列中的記錄已按關(guān)鍵字有序排列時(shí)，顯然，在進(jìn)行n-1次關(guān)鍵字的比較，而不需要交換記錄；然而，當(dāng)待排序列中的記錄按關(guān)鍵字逆序排列時(shí)，需進(jìn)行n-1趟起泡，并且每一趟起泡都需進(jìn)行所有記錄的互換，因此進(jìn)行的關(guān)鍵字比較的總數(shù)為：

進(jìn)行的記錄移動(dòng)的總數(shù)為：

10.3快速排序--起泡排序算法分析2023/2/1933快速排序是起泡排序的一種改進(jìn)基本思想是：根據(jù)樞軸通過一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排列以達(dá)到整個(gè)序列有序。10.3快速排序--快速排序2023/2/1934一趟快排過程

r[0]2738659776134949low49high276513974910.3快速排序--快速排序演示2023/2/1935排序的全過程3876494927651397初始狀態(tài)一次劃分之后2738134976976549｛｝｛｝分別進(jìn)行快排132738｛｝｛｝｛｝49657697｛｝結(jié)束結(jié)束4965｛｝結(jié)束結(jié)束有序序列274997137638654910.3快速排序--快速排序演示2023/2/1936快速排序的平均時(shí)間復(fù)雜度為O(nlogn)，在所有同數(shù)量級(jí)的排序方法中，其平均性能最好。但若初始記錄序列按關(guān)鍵字有序或基本有序時(shí)，則蛻化為起泡排序?？焖倥判蛟诳臻g上比其他排序都多需要一個(gè)棧來實(shí)現(xiàn)遞歸。10.3快速排序--快速排序算法分析2023/2/1937選擇排序的基本思想如下圖所示：有序序列R[1,2,…,i-1]無序序列[i,i+1,…,n]選擇最小記錄Rj有序序列R[1,2,…,i-1],RjRi-1,...,Rj-1,Rj+1,…Rn第i趟排序即通過n-i次關(guān)鍵字間的比較，從n-i+1個(gè)記錄中選出關(guān)鍵字最小的記錄并和第i個(gè)記錄交換10.4選擇排序2023/2/1938選擇排序所需進(jìn)行的“比較”次數(shù)都相同，為

n×（n+1）/2“移動(dòng)”次數(shù)在待排序列為“正序”時(shí)達(dá)最小為0，在“逆序”時(shí)達(dá)最大為3(n-1)。減少比較次數(shù)可以改進(jìn)該算法，先參看錦標(biāo)賽示例。10.4選擇排序--簡(jiǎn)單選擇排序算法分析2023/2/1939錦標(biāo)賽過程選拔冠軍ZHAOCHALIUBAODIAOYANGXUEWANGCHABAODIAOWANGBAODIAOBAO選拔亞軍*CHACHA選拔季軍LIUDIAO*2023/2/1940樹形選擇排序，又稱錦標(biāo)賽排序，是一種按照錦標(biāo)賽的思想進(jìn)行選擇排序的方法。首先對(duì)n個(gè)記錄的關(guān)鍵字進(jìn)行兩兩比較，然后在其中個(gè)較小者之間進(jìn)行兩兩比較，直至選出最小關(guān)鍵字的記錄為止。下面是過程演示10.4選擇排序--樹形選擇排序2023/2/1941493865977613274938651327381313輸出最小關(guān)鍵字輸出13之后∞762727輸出13，27之后∞494938以后步驟相同10.4選擇排序--樹形選擇排序演示2023/2/1942由于含有n個(gè)葉子結(jié)點(diǎn)的完全二叉樹的深度為 ，則在樹形選擇排序中，除了最小關(guān)鍵字之外，每選擇一個(gè)次小關(guān)鍵字僅需要進(jìn)行次比較，因此它的時(shí)間復(fù)雜度為需要輔助存儲(chǔ)空間多，和“最大值”進(jìn)行多余的比較等缺點(diǎn)。為了彌補(bǔ)，有人提出另一種選擇排序——堆排序。10.4選擇排序--樹形選擇排序算法分析2023/2/1943堆的定義：n

個(gè)元素的序列(k1,k2,…,kn)當(dāng)且僅當(dāng)滿足如下關(guān)系時(shí)，稱之為堆或(i=1,2,…n/2)10.4選擇排序--堆排序2023/2/194496{96，83，27，38，11，09}堆頂取最大值（大根堆）堆頂取最小值（小根堆）{12，36，24，85，47，30，53，91}278338119123685249130534710.4選擇排序--堆排序2023/2/1945若在輸出堆頂?shù)淖钚≈岛螅沟檬Ｓ鄋-1個(gè)元素的序列又建成一個(gè)堆，則得到n個(gè)元素中的次小值，如此反復(fù)執(zhí)行，便能得到一個(gè)有序序列，這個(gè)過程稱之為堆排序所以，堆排序的兩個(gè)關(guān)鍵問題是：如何將一個(gè)無序序列調(diào)整為堆如何在互換堆頂之后重新調(diào)整為堆10.4選擇排序--堆排序2023/2/1946篩選過程13382749766549979727499713972797重復(fù)篩選過程10.4選擇排序--堆排序演示2023/2/1947建初始堆演示4938652713769749無序序列篩選974997篩選656513篩選3838篩選49491327建成小頂堆10.4選擇排序--堆排序演示2023/2/1948堆排序方法對(duì)于記錄較少的文件并不值得提倡，但對(duì)n較大的文件還是很有效的。建初始堆和調(diào)整新堆時(shí)的篩選占較大比例的運(yùn)行時(shí)間。無論待排序列中的記錄是正序還是逆序排列，堆排序的時(shí)間復(fù)雜度都是O(n*logn)。10.4選擇排序--堆排序算法分析2023/2/1949歸并排序是將兩個(gè)或兩個(gè)以上的有序表組合成一個(gè)新的有序表。假設(shè)初始序列含有n個(gè)記錄，則可看成是n個(gè)有序的子序列，每個(gè)子序列的長度為1，然后兩兩歸并得到n/2個(gè)長度為2或者1的有序子序列，再兩兩歸并，…..，如此重復(fù)直到得到一個(gè)長度為n的有序序列為止，這種排序方法成為2-路歸并排序。10.5歸并排序2023/2/1950下面給出一個(gè)2-路歸并排序的例子初始關(guān)鍵字49386597761327一趟歸并38496597137627二趟歸并38496597132776三趟歸并1327384965769710.5歸并排序--2-路歸并排序演示2023/2/1951與快速排序和堆排序相比，歸并排序的最大特點(diǎn)是，它是一種穩(wěn)定的排序方法。但在一般情況下，很少用2-路歸并排序法進(jìn)行內(nèi)部排序。2-路歸并排序的時(shí)間復(fù)雜度為O(nlogn)。10.5歸并排序--2-路歸并排序算法分析2023/2/1952基數(shù)排序是一種借助多關(guān)鍵字排序的思想對(duì)單邏輯關(guān)鍵字進(jìn)行排序的方法。定義 假設(shè)含有n個(gè)記錄的序列為：

{R1，R2，….，Rn}

且每個(gè)記錄Ri

中含有d個(gè)關(guān)鍵字，則稱該序列對(duì)關(guān)鍵字有序指：對(duì)于序列中任意兩個(gè)記錄

Ri

和

Rj（1≤i<j≤n）都滿足下列有序關(guān)系

其中K0被稱作最主位關(guān)鍵字，Kd-1

被稱作最次位關(guān)鍵字10.6基數(shù)排序2023/2/1953多關(guān)鍵字排序經(jīng)常用到的兩種方法。

最高位優(yōu)先法(MostSignificantDigitfirst)

最低位優(yōu)先法(LeastSignificantDigitfirst)10.6基數(shù)排序2023/2/1954鏈?zhǔn)交鶖?shù)排序類似于表插入排序，附設(shè)指針數(shù)組將順序表視作一個(gè)“靜態(tài)鏈表”，利用“修改指針”實(shí)現(xiàn)分配和收集。同時(shí)設(shè)置rd個(gè)隊(duì)列的頭指針和尾指針，分別指示各隊(duì)列的"頭結(jié)點(diǎn)"和"尾結(jié)點(diǎn)"在鏈表中的位置。10.6基數(shù)排序—鏈?zhǔn)交鶖?shù)排序2023/2/1955初始態(tài)一趟分配e[0]e[1]e[2]e[4]e[3]e[6]e[5]e[7]e[9]e[8]f[9]f[8]f[7]f[6]f[5]f[4]f[3]f[2]f[1]f[0]278109063930589184505269008083269589109930083063184505008278一趟收集930063083184505278008109589269依次按次高位，最高位進(jìn)行分配收集10.6基數(shù)排序—鏈?zhǔn)交鶖?shù)排序演示2023/2/1956對(duì)于n個(gè)記錄進(jìn)行鏈?zhǔn)交鶖?shù)排序的時(shí)間復(fù)雜度為O(d(n+rd))

其中每一趟分配的時(shí)間復(fù)雜度為O(n)，每一趟收集的時(shí)間復(fù)雜度為O(rd),

整個(gè)排序需要進(jìn)行d趟分配和收集。所需空間為2rd個(gè)隊(duì)列指針。當(dāng)然，由于需用鏈表作存儲(chǔ)結(jié)構(gòu)，則相對(duì)于其他以順序結(jié)構(gòu)存儲(chǔ)記錄的排序方法而言，還增加了n個(gè)指針域的空間。10.6基數(shù)排序—鏈?zhǔn)交鶖?shù)排序算法分析2023/2/1957排序方法平均時(shí)間最壞情況輔助存儲(chǔ)穩(wěn)定性簡(jiǎn)單排序O(n*n)O(n*n)O(1)√快速排序O(nlogn)O(n*n)O(logn)×堆排序O(nlogn)O(nlogn)O(1)×歸并排序O(nlogn)O(nlogn)O(n)√基數(shù)排序O(d(n+rd))O(d(n+rd))O(rd)√各種排序方法的性能分析如下表所示：10.6各種排序方法的比較討論2023/2/1958記錄較大的序列采用的方法對(duì)于表插入排序，鏈?zhǔn)交鶖?shù)排序可采用靜態(tài)鏈表作存儲(chǔ)結(jié)構(gòu)對(duì)于不能實(shí)現(xiàn)表排序的方法，如快速排序，堆排序，可以進(jìn)行“地址排序”。10.6各種排序方法的比較討論20