排序算法詳解

排序算法詳解第1頁，共68頁，2023年，2月20日，星期一問題的提出：為什么要排序？有序表的優(yōu)點(diǎn)？缺點(diǎn)？構(gòu)造關(guān)系。按照什么原則排序？比較？如何進(jìn)行排序？第2頁，共68頁，2023年，2月20日，星期一基本概念排序（Sorting）：簡單地說，排序就是把一組記錄按照某個(gè)（或某幾個(gè)）字段的值以遞增（由小到大）或遞減（由大到?。┑拇涡蛑匦屡帕械倪^程。（如按年齡從小到大排序）學(xué)號(hào)姓名年齡性別2004001張佳18男2004002王鵬19男2004003劉寧17女2004004李娟18女2004005陳濤19男2004006李小燕18女第3頁，共68頁，2023年，2月20日，星期一作為比較基礎(chǔ)的一個(gè)(或多個(gè))字段，稱為排序碼。排序碼可以是數(shù)值、符號(hào)或符號(hào)串。排序碼不一定是關(guān)鍵碼，關(guān)鍵碼可以作為排序碼。關(guān)鍵碼是唯一的，但排序碼不一定唯一。排序碼不唯一時(shí)，排序的結(jié)果可能不唯一。參與排序的對(duì)象，稱為記錄。一個(gè)記錄可以包含多個(gè)字段。如果記錄集合中存在多個(gè)排序碼相同的記錄，經(jīng)過排序后，排序碼相同的記錄的前后次序保持不變，則這種排序方法稱為是穩(wěn)定的，否則是不穩(wěn)定的。排序碼與關(guān)鍵碼（primarykey）第4頁，共68頁，2023年，2月20日，星期一排序方法可以分為五種∶插入排序、選擇排序、交換排序、分配排序和歸并排序。在排序過程中，全部記錄存放在內(nèi)存，則稱為內(nèi)排序，如果排序過程中需要使用外存，則稱為外排序。

本章側(cè)重討論內(nèi)排序的方法，但有些方法(特別是歸并排序的思想)也可以用于外排序。排序的類型第5頁，共68頁，2023年，2月20日，星期一排序算法的評(píng)價(jià)評(píng)價(jià)排序算法好壞的標(biāo)準(zhǔn)執(zhí)行算法所需的時(shí)間執(zhí)行算法所需要的附加空間算法本身的復(fù)雜程度也是考慮的一個(gè)因素排序的時(shí)間開銷是算法好壞的最重要的標(biāo)志排序的時(shí)間開銷衡量標(biāo)準(zhǔn):算法執(zhí)行中的比較次數(shù)（必須）。算法執(zhí)行中的移動(dòng)次數(shù)（有可能避免）。通常會(huì)關(guān)注最壞情況和平均情況的開銷。第6頁，共68頁，2023年，2月20日，星期一插入排序基本思想：每步將一個(gè)待排序的記錄，按其排序碼大小插到前面已經(jīng)排序的字序列的合適位置，直到全部插入排序完為止。x

順次選取一個(gè)元素插入到合適位置第7頁，共68頁，2023年，2月20日，星期一插入排序的細(xì)分類如何插入到已排好序的序列中？直接插入（從后向前找位置后插入）

O(n2)

二分法插入（按二分法找位置后插入）

O(nlog2n)

表插入排序（按鏈表查找位置后插入）

O(n2)第8頁，共68頁，2023年，2月20日，星期一直接插入排序基本思想：假定前面m個(gè)元素已經(jīng)排序；取第(m+1)個(gè)元素，插入到前面的適當(dāng)位置；一直重復(fù)，到m=n為止。（初始情況下，m=1）第9頁，共68頁，2023年，2月20日，星期一

第一趟：{23}，[起始只有一個(gè)記錄]{11,23}11

第二趟：{11，23}，{11，23，55}55

第三趟：{11，23，55}，{11，23，55，97}97

第四趟：{11，23，55，97}，{11，19，23，55，97}19

第五趟：{11，19，23，55，97}，{11，19，23，55，80，97}80示例：{23，11，55，97，19，80}第10頁，共68頁，2023年，2月20日，星期一直接插入排序的算法中記錄的數(shù)據(jù)結(jié)構(gòu)typedefintKeyType;typedefintDataType;typedefstruct{

KeyTypekey; /*排序碼字段*/DataTypeinfo;/*記錄的其他字段*/}RecordNode;typedefstruct{ intn;/*n為文件中的記錄個(gè)數(shù)，n<MAXNUM*/RecordNode*record;}SortObject;第11頁，共68頁，2023年，2月20日，星期一直接插入排序算法復(fù)雜度評(píng)價(jià)極端情況下：最小比較次數(shù)∶每個(gè)記錄僅比較一次最大比較次數(shù)∶每個(gè)記錄比較已排好序的記錄長度第12頁，共68頁，2023年，2月20日，星期一直接插入排序算法評(píng)價(jià)2最小移動(dòng)次數(shù)∶最大移動(dòng)次數(shù)∶第13頁，共68頁，2023年，2月20日，星期一直接插入排序算法評(píng)價(jià)3初始數(shù)據(jù)狀態(tài)相關(guān)：文件初態(tài)不同時(shí)，直接插入排序所耗費(fèi)的時(shí)間有很大差異。若文件初態(tài)為正序，則算法的時(shí)間復(fù)雜度為O(n)若初態(tài)為反序，則時(shí)間復(fù)雜度為O(n2)第14頁，共68頁，2023年，2月20日，星期一直接插入排序算法評(píng)價(jià)4——平均復(fù)雜度插入記錄Ri-1，有i種可能的插入位置，即插入到第0，1，…，i-1位置上，假設(shè)每種情況發(fā)生的概率是相等的，均為pj=1/i(j=0,1,…,i-1)比較次數(shù)為Cj=j+1(j=0,…,i-2,i-2)，則插入記錄Ri-1的平均比較次數(shù)為∶第15頁，共68頁，2023年，2月20日，星期一直接插入排序算法評(píng)價(jià)5——平均復(fù)雜度直接插入排序的總的比較次數(shù)為：第16頁，共68頁，2023年，2月20日，星期一直接插入排序算法評(píng)價(jià)直接插入排序算法的平均移動(dòng)次數(shù)與平均比較次數(shù)同級(jí)，也是O(n2)直接插入排序的平均時(shí)間復(fù)雜度為T(n)=O(n2)算法中引入了一個(gè)附加的記錄空間temp，因此輔助空間為S(n)=O(1)直接插入排序是穩(wěn)定的第17頁，共68頁，2023年，2月20日，星期一存儲(chǔ)結(jié)構(gòu)與算法優(yōu)化順序存儲(chǔ)結(jié)構(gòu)：二分插入算法，減少比較次數(shù)。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：減少移動(dòng)次數(shù)。第18頁，共68頁，2023年，2月20日，星期一二分法插入排序特點(diǎn)：在直接插入排序的基礎(chǔ)上減少比較的次數(shù)，即在插入Ri時(shí)改用二分法比較找插入位置，便得到二分法插入排序限制：必須采用順序存儲(chǔ)方式。第19頁，共68頁，2023年，2月20日，星期一例：有6個(gè)記錄，前5個(gè)已排序的基礎(chǔ)上，對(duì)第6個(gè)記錄排序。[1527365369]42

lowmidhigh

[1527365369]42

lowhigh

mid

[1527365369]42

highlow[152736425369](high<low，查找結(jié)束，插入位置為low或high+1)(42>36)(42<53)第20頁，共68頁，2023年，2月20日，星期一二分法插入排序算法voidbinSort(SortObject*pvector){

inti,j,left,mid,right;

RecordNodetemp;

for(i=1;i<pvector->n;i++)

{

temp=pvector->record[i];

left=0;right=i–1;

while(left<=right)

{

mid=(left+right)/2；if(temp.key<vector->record[mid].key)

right=mid-1;

else left=mid+1;}//while

for(j=i-1;j>=left;j--)pvector->record[j+1]=pvector->record[j]; if(left!=i)pvector->record[left]=temp;}//for}//binSort第21頁，共68頁，2023年，2月20日，星期一二分插入排序比較次數(shù)二分插入排序的比較次數(shù)與待排序記錄的初始狀態(tài)無關(guān)，僅依賴于記錄的個(gè)數(shù)，插入第i個(gè)記錄時(shí)，如果，則無論排序碼的大小，都恰好經(jīng)過次比較才能確定插入位置，如果，則比較次數(shù)為j+1，因此，將n(n=2k)個(gè)記錄排序的總比較次數(shù)為第22頁，共68頁，2023年，2月20日，星期一二分法插入排序方法性能分析當(dāng)n較大時(shí)，比直接插入排序的最大比較次數(shù)少得多。但大于直接插入排序的最小比較次數(shù)算法的移動(dòng)次數(shù)與直接插入排序算法的相同最壞的情況為n2/2最好的情況為n平均移動(dòng)次數(shù)為O(n2)二分法插入排序算法的平均時(shí)間復(fù)雜度為T(n)=O(n2)二分插入排序法是穩(wěn)定的排序算法,在檢索時(shí)采用left>right結(jié)束，left、right的修改原則是：temp.key<pvector->record[mid].key，保證排序是穩(wěn)定的。第23頁，共68頁，2023年，2月20日，星期一結(jié)論移動(dòng)次數(shù)與直接插入排序相同，最壞的情況為n2/2，最好的情況為n，平均移動(dòng)次數(shù)為O(n2)二分法插入排序算法的平均時(shí)間復(fù)雜度為T(n)=O(n2)二分法插入排序是穩(wěn)定的第24頁，共68頁，2023年，2月20日，星期一表插入排序表插入排序是在直接插入排序的基礎(chǔ)上減少移動(dòng)的次數(shù)?；舅枷?在記錄中設(shè)置一個(gè)指針字段，記錄用鏈表連接插入記錄Ri時(shí)，記錄R0至Ri-1已經(jīng)排序，先將記錄Ri脫鏈再采用順序比較的方法找到Ri應(yīng)插入的位置，將Ri插入鏈表。第25頁，共68頁，2023年，2月20日，星期一structNode; /*單鏈表結(jié)點(diǎn)類型*/typedefstructNodeListNode;structNode{KeyTypekey; /*排序碼字段*/DataTypeinfo; /*記錄的其它字段*/ListNode*next; /*記錄的指針字段*/};typedefListNode*LinkList;表插入算法中記錄的數(shù)據(jù)結(jié)構(gòu)第26頁，共68頁，2023年，2月20日，星期一表插入排序的算法性能分析

第i趟排序：最多比較次數(shù)i次，最少比較次數(shù)1次。

n-1趟總的比較次數(shù)：最多：最少：n-1

記錄移動(dòng)次數(shù)：0

時(shí)間效率：O(n2)

輔助空間：O(n)[指針]

穩(wěn)定性：p->key<=now->key保證穩(wěn)定的排序。第27頁，共68頁，2023年，2月20日，星期一選擇排序思想：每趟從待排序的記錄序列中選擇關(guān)鍵字最小的記錄放置到已排序表的最前位置，直到全部排完。關(guān)鍵問題：在剩余的待排序記錄序列中找到最小關(guān)鍵碼記錄。方法：直接選擇排序堆排序。第28頁，共68頁，2023年，2月20日，星期一直接選擇排序方法是∶首先在所有記錄中選出排序碼最小的記錄，與第一個(gè)記錄交換然后在其余的記錄中再選出排序碼最小的記錄與第二個(gè)記錄交換以此類推，直到所有記錄排好序第29頁，共68頁，2023年，2月20日，星期一直接選擇排序性能分析選擇排序的比較次數(shù)與記錄的初始狀態(tài)無關(guān)。第i趟排序：從第i個(gè)記錄開始，順序比較選擇最小關(guān)鍵碼記錄需要n-i次比較?？偟谋容^次數(shù)：移動(dòng)次數(shù)：Mmin=0(初始為正序時(shí)）最多移動(dòng)次數(shù)：Mmax=3(n-1)(初始為逆序時(shí)，每趟1次交換，3次移動(dòng)完成）

時(shí)間復(fù)雜度：T(n)=O(n2)，輔助空間1個(gè)記錄單位：Temp，穩(wěn)定性：不穩(wěn)定的排序。

第30頁，共68頁，2023年，2月20日，星期一31起泡排序方法先將序列中的第一個(gè)記錄R0與第二個(gè)記錄R1比較，若前者大于后者，則兩個(gè)記錄交換位置，否則不交換然后對(duì)新的第二個(gè)記錄R1與第三個(gè)記錄R2作同樣的處理依次類推，直到處理完第n-1個(gè)記錄和第n個(gè)記錄從(R0，R1)到(Rn-2，Rn-1)的n-1次比較和交換過程稱為一次起泡經(jīng)過這次起泡，n個(gè)記錄中最大者被安置在第n個(gè)位置上第31頁，共68頁，2023年，2月20日，星期一32此后，再對(duì)前n-1個(gè)記錄進(jìn)行同樣處理，使n-1個(gè)記錄的最大者被安置在整個(gè)序列的第n-1個(gè)位置上。然后再對(duì)前n-2個(gè)記錄重復(fù)上述過程……，這樣最多做n-1次起泡就能完成排序可以設(shè)置一個(gè)標(biāo)志noswap表示本次起泡是否有記錄交換，如果沒有交換則表示整個(gè)排序過程完成起泡排序是通過相鄰記錄之間的比較與交換，使值較大的記錄逐步從前(上)向后(下)移，值較小的記錄逐步從后(下)向前(上)移，就像水底的氣泡一樣向上冒，故稱為起泡排序起泡排序方法第32頁，共68頁，2023年，2月20日，星期一若文件初狀為正序，則一趟起泡就可完成排序，排序碼的比較次數(shù)為n-1，且沒有記錄移動(dòng)，時(shí)間復(fù)雜度是O(n)若文件初態(tài)為逆序，則需要n-1趟起泡，每趟進(jìn)行n-i次排序碼的比較，且每次比較都移動(dòng)三次，比較和移動(dòng)次數(shù)均達(dá)到最大值∶起泡排序的算法評(píng)價(jià)第33頁，共68頁，2023年，2月20日，星期一起泡排序的算法評(píng)價(jià)(續(xù))起泡排序最好時(shí)間復(fù)雜度是O(n)起泡排序最壞時(shí)間復(fù)雜度為O(n2)起泡排序平均時(shí)間復(fù)雜度為O(n2)起泡排序算法中增加一個(gè)輔助空間temp，輔助空間為S(n)=O(1)起泡排序是穩(wěn)定的第34頁，共68頁，2023年，2月20日，星期一歸并排序（mergesort）歸并排序的基本操作是將兩個(gè)或兩個(gè)以上的記錄有序序列歸并為一個(gè)有序序列。最簡單的情況是:只含一個(gè)記錄的序列顯然是個(gè)有序序列，經(jīng)過"逐趟歸并"使整個(gè)序列中的有序子序列的長度逐趟增大，直至整個(gè)記錄序列為有序序列止。

第35頁，共68頁，2023年，2月20日，星期一歸并排序（mergesort）88149825625279302331DivideandConquer第36頁，共68頁，2023年，2月20日，星期一MergeSort88149825625279302331SplitSetintoTwo

(norealwork)25,31,52,88,98Getonefriendto

sortthefirsthalf.14,23,30,62,79Getonefriendto

sortthesecondhalf.第37頁，共68頁，2023年，2月20日，星期一MergeSortMergetwosortedlistsintoone25,31,52,88,9814,23,30,62,7914,23,25,30,31,52,62,79,88,98第38頁，共68頁，2023年，2月20日，星期一第39頁，共68頁，2023年，2月20日，星期一二路歸并算法的基本思路：兩組歸并算法merge：按low,m,high歸并兩組記錄。結(jié)果放于low,high之間。voidmerge(RecordNode*r,RecordNode*r1,intlow,intm,inthigh)一趟歸并算法mergePass：兩兩歸并長度為length的一組記錄：voidmergePass(RecordNode*r,RecordNode*r1,intn,intlength)

第40頁，共68頁，2023年，2月20日，星期一具有n個(gè)記錄的文件排序，必須做log2n

趟歸并，每趟歸并所花費(fèi)的時(shí)間是O(n)二路歸并排序算法的時(shí)間復(fù)雜度為T(n)=O(nlog2n)算法中增加了一個(gè)數(shù)組record，算法的輔助空間為S(n)=O(n)二路歸并排序是穩(wěn)定的算法評(píng)價(jià)第41頁，共68頁，2023年，2月20日，星期一Quicksort第42頁，共68頁，2023年，2月20日，星期一Quicksort(cont.)Divide:Partition(rearrange)thearrayA[p‥r]intotwosubarraysA[p‥q-1]andA[q+1‥r]suchthat：

eachelementofA[p‥q-1]<=A[q],inturn:A[q+1..r]>A[q]Conquer:SortthetwosubarraysA[p‥q-1]andA[q+1‥r]byrecursivecallstoquicksort.Combine:Sincethesubarraysaresortedinplace,noworkisneededtocombinethem:theentirearrayA[p‥r]isnowsorted.第43頁，共68頁，2023年，2月20日，星期一Quicksort(cont.)O(n)?第44頁，共68頁，2023年，2月20日，星期一分配排序分配排序是一種借助多關(guān)鍵碼排序思想對(duì)單關(guān)鍵碼排序的方法第45頁，共68頁，2023年，2月20日，星期一例子∶撲克牌排序要求:每張撲克牌具有兩個(gè)屬性∶花色（梅花<方塊<紅心<黑桃）和面值（2<3<…<10<J<Q<K<A），且花色的地位高于面值，排序后為∶梅花2，…，梅花A，方塊2，…，方塊A，紅心2，…，紅心A，黑桃2，…，黑桃A 分配排序例子第46頁，共68頁，2023年，2月20日，星期一撲克牌排序方法排序有以下兩種方法∶第一是先將牌按花色分成4堆，然后將每堆按面值從小到大排序，最后按花色從小到大迭在一起第二種是先將牌按面值大小分成13堆，然后從小到大把它們收集起來，再按花色分成4堆，最后順序地收集起來

第47頁，共68頁，2023年，2月20日，星期一對(duì)多關(guān)鍵碼有序一般情況下，假設(shè)文件F有n個(gè)記錄

F=(R0，R1，…Rn-1)且每個(gè)記錄Ri中含有d個(gè)關(guān)鍵碼(ki0,ki1,…,kid-1)，則文件對(duì)關(guān)鍵碼(k0,k1,…,kd-1)有序是指∶文件中任意兩個(gè)記錄Ri和Rj(0≤i≤j≤n-1)滿足詞典次序有序關(guān)系

(ki0,ki1,…,kid-1)<(kj0,kj1,…,kjd-1)

其中k0稱為最高位關(guān)鍵碼，kd-1稱為最低位關(guān)鍵碼第48頁，共68頁，2023年，2月20日，星期一高位優(yōu)先法:先對(duì)最高位關(guān)鍵碼k0排序，將文件分成若干堆每堆中的記錄都具有相同的k0然后分別就每堆對(duì)關(guān)鍵碼k1排序，分成若干子堆，如此重復(fù)，直到對(duì)kd-1排序最后將各堆按次序疊在一起成為一個(gè)有序文件低位優(yōu)先法:從最低位關(guān)鍵碼kd-1起排序然后再對(duì)高一位關(guān)鍵碼kd-2排序如此重復(fù)，直到對(duì)K0排序后便成為一個(gè)有序文件多關(guān)鍵碼排序算法第49頁，共68頁，2023年，2月20日，星期一低位優(yōu)先法比高位優(yōu)先法簡單，高位優(yōu)先排序必須將文件逐層分割成若干子文件，然后各子文件獨(dú)立排序低位優(yōu)先排序不必分成子堆，對(duì)每個(gè)關(guān)鍵碼都是整個(gè)文件參加排序，且可通過若干次“分配”和“收集”實(shí)現(xiàn)排序基數(shù)排序就是用低位優(yōu)先法對(duì)單邏輯關(guān)鍵碼排序的一種方法分配排序算法第50頁，共68頁，2023年，2月20日，星期一方法:把每個(gè)排序碼看成是一個(gè)d元組∶

Ki=(Ki0,Ki1,…,Kid-1)其中每個(gè)Ki都是集合{C0，C1，…，Cr-1}(C0<C1<…<Cr-1)中的值即C0≤Kij≤Cr-1(0≤i≤n-1,0≤j≤d-1)其中r稱為基數(shù)排序時(shí)先按Kid-1從小到大將記錄分配到r個(gè)堆中然后依次收集，再按Kid-2分配到r個(gè)堆中如此反復(fù)，直到對(duì)Ki0分配、收集，得到的便是排好序的序列基數(shù)排序第51頁，共68頁，2023年，2月20日，星期一基數(shù)排序方法(續(xù))基數(shù)排序時(shí)，為了實(shí)現(xiàn)記錄的分配和收集，可以設(shè)r個(gè)隊(duì)列，排序前為空隊(duì)列，分配時(shí)將記錄插入到各自的隊(duì)列中，收集時(shí)將隊(duì)列中的記錄排在一起。第52頁，共68頁，2023年，2月20日，星期一初始序列為36，5，16，98，95，47，32，36’，48，10，請(qǐng)用基數(shù)排序法排序。

(1)初始狀態(tài)

36→5→16→98→95→47→32→36’→48→10

例題第53頁，共68頁，2023年，2月20日，星期一54例題(續(xù))(2)第一趟分配后

第54頁，共68頁，2023年，2月20日，星期一(3)第一趟收集后

10→32→5→95→36→16→36’→47→98→48(4)第二趟分配后 例題(續(xù))第55頁，共68頁，2023年，2月20日，星期一例題(續(xù))第56頁，共68頁，2023年，2月20日，星期一(5)第二趟收集后

5→10→16→32→36→36’→47’→48→95→98

例題(續(xù))第57頁，共68頁，2023年，2月20日，星期一基數(shù)排序算法中，沒有排序碼的比較和記錄的移動(dòng)，只是對(duì)鏈表的掃描和指針的賦值，所以，時(shí)間耗費(fèi)主要在修改指針上每趟排序中，清隊(duì)列的時(shí)間為O(r)，將n個(gè)記錄分配到隊(duì)列的時(shí)間為O(n)，收集的時(shí)間為O(r)，因此，一趟排序的時(shí)間為O(r+n)總共要進(jìn)行d趟排序，基數(shù)排序的時(shí)間復(fù)雜度是T(n)=O(d*(r+n))當(dāng)n較大、d較小，特別是記錄的信息量較大時(shí)，基數(shù)排序非常有效基數(shù)排序算法評(píng)價(jià)第58頁，共68頁，2023年，2月20日，星期一基數(shù)排序中，每個(gè)記錄中增加了一個(gè)next字段，還增加了一個(gè)queue數(shù)組，故輔助空間為S(n)=O(n+r)基數(shù)排序是穩(wěn)定的基數(shù)排序算法評(píng)價(jià)(續(xù))第59頁，共68頁，2023年，2月20日，星期一Countingsort（8.2）第60頁，共68頁，2023年，2月20日，星期一COUNTING-SORT(A,B,k)1(for

i←0to

k)