數(shù)據(jù)結(jié)構(gòu)PPT演示課件

第7章 排序,排序（sorting）是計(jì)算機(jī)程序設(shè)計(jì)的一個(gè)特別重要的技術(shù)，計(jì)算機(jī)的各個(gè)應(yīng)用領(lǐng)域都有它的身影。如在處理學(xué)生考試成績(jī)和元素的查找等都涉及到了對(duì)數(shù)據(jù)的排序。排列有序的折半查找要比順序查找的效率要高許多。本章主要給大家介紹幾種常用的排序技術(shù)：插入排序、選擇排序、交換排序、歸并排序和基數(shù)排序。 本章重點(diǎn)和難點(diǎn)： 1、希爾排序 2、快速排序 3、堆排序 4、歸并排序 5、基數(shù)排序,7.1 基本概念,排序：把一個(gè)無(wú)序的元素序列按照元素的關(guān)鍵字遞增或遞減排列為有序的序列。 假設(shè)包含n個(gè)元素（記錄）的序列 (E1,E2,En) 其對(duì)應(yīng)的關(guān)鍵字為 (k1,k2,kn) 需確定1,2,n的一種排列p1,p2,pn，使關(guān)鍵字滿足以下非遞減（或非遞增）關(guān)系： kp1kp2kpn 從而使元素構(gòu)成一個(gè)非遞減（或非遞增）的序列： (Ep1,Ep2,Epn) 這樣的一種操作被稱為排序。,7.1 基本概念,穩(wěn)定排序和不穩(wěn)定排序：在待排序的記錄序列中，若存在兩個(gè)或兩個(gè)以上關(guān)鍵字想到呢個(gè)的記錄。假設(shè)ki=kj(1in,1jn,ij)，且排序前的對(duì)應(yīng)的記錄Ei領(lǐng)先于Ej（即i<j）。若在排序之后，如果元素Ei仍領(lǐng)先于Ej，則稱這種排序采用的方法是穩(wěn)定的。如果經(jīng)過(guò)排序之后，元素Ej領(lǐng)先于Ei（即i<j），則稱這種排序方法是不穩(wěn)定的。 一個(gè)排序算法的好壞可以主要通過(guò)時(shí)間復(fù)雜度、空間復(fù)雜度和穩(wěn)定性來(lái)衡量。無(wú)論算法穩(wěn)定還是不穩(wěn)定的，都不會(huì)影響到排序的最終結(jié)果。,7.1 基本概念,內(nèi)排序和外排序：由于待排序的記錄數(shù)量不同，使得排序過(guò)程中涉及的存儲(chǔ)器不同，可將排序方法分為兩類：內(nèi)部排序和外部排序。內(nèi)部排序也稱為內(nèi)排序，指的是待排序記錄存放在計(jì)算機(jī)隨機(jī)存儲(chǔ)器中進(jìn)行的排序過(guò)程；外部排序也稱為外排序，指的是待排序記錄的數(shù)據(jù)流很大，以致內(nèi)存一次不能容納全部記錄，在排序的過(guò)程中需要不斷對(duì)外存進(jìn)行訪問(wèn)的排序過(guò)程。,7.1 基本概念,內(nèi)排序的方法有許多，按照排序過(guò)程中采用的策略將排序分為幾個(gè)大類：插入排序、選擇排序、交換排序和歸并排序。 在排序過(guò)程中，需要以下兩種基本操作： （1）比較兩個(gè)元素相應(yīng)關(guān)鍵字的大??； （2）將元素從一個(gè)位置移動(dòng)到另一個(gè)位置。 其中，第（1）種操作對(duì)大多數(shù)排序方法來(lái)說(shuō)都是必要的，第（2）種操作可通過(guò)改變記錄的存儲(chǔ)方式可以避免。,7.1 基本概念,待排序的記錄序列可有下列3種存儲(chǔ)方式：（1）順序存儲(chǔ)。待排序的元素存儲(chǔ)在一組連續(xù)的存儲(chǔ)單元中，這類似于線性表的順序存儲(chǔ)，在序列中相鄰的兩個(gè)記錄Ei和Ej，它們的物理位置也相鄰。在這種存儲(chǔ)方式中，記錄之間的次序關(guān)系由其存儲(chǔ)位置決定，則實(shí)現(xiàn)排序必須要移動(dòng)記錄。（2）鏈?zhǔn)酱鎯?chǔ)。待排序元素存儲(chǔ)在一組不連續(xù)的存儲(chǔ)單元中，這類似于線性表的鏈?zhǔn)酱鎯?chǔ)，序列中相鄰的兩個(gè)記錄Ei和Ej，其物理位置不一定相鄰。在這種存儲(chǔ)方式中，記錄之間的關(guān)系由附設(shè)的指針指示，在進(jìn)行排序時(shí)，不需要移動(dòng)元素，只需要修改指針即可。（3）靜態(tài)鏈表。帶排序記錄存放在靜態(tài)鏈表中，記錄之間的關(guān)系由被稱為游標(biāo)的指針指示，實(shí)現(xiàn)排序不需要移動(dòng)元素，只需要修改游標(biāo)即可。,7.2 插入排序,7.2.1 直接插入排序 直接插入排序（straight insertion sort）是一種最簡(jiǎn)單的插入排序算法。它的基本算法思想描述如下： 假設(shè)待排序元素有n個(gè)，初始時(shí)，已排序子集只有一個(gè)元素，即第1個(gè)元素。未排序子集是剩下的n-1個(gè)元素。例如，有4個(gè)待排序元素22、6、17和8，排序前的狀態(tài)如圖7.1所示。,7.2 插入排序,第1趟排序：將無(wú)序集中的第一個(gè)元素，也就是6與有序集中的元素22進(jìn)行比較，因?yàn)?2>6，所以需要先將22向后移動(dòng)一個(gè)位置，然后將6插入到第一個(gè)位置，如圖7.2所示。其中，陰影部分表示無(wú)序集，白色部分表示有序集。第2趟排序：將無(wú)序集的元素17從右到左依次與有序集中的元素比較，即先與22比較，因?yàn)?76，所以將17放在第2個(gè)元素的位置，如圖7.3所示。,7.2 插入排序,第3趟排序：將待排序集合中的元素8與已經(jīng)有序的元素集合從右到左依次比較，先與22比較。因?yàn)?6，所以將8放在第2個(gè)位置，如圖7.4所示。,7.2 插入排序,假設(shè)待排序元素有8個(gè)，分別是17、46、32、87、58、9、50、38。使用直接插入排序?qū)υ撛匦蛄械呐判蜻^(guò)程如圖7.5所示。,7.2 插入排序,直接插入排序算法描述如下。void InsertSort(SqList *L)/*直接插入排序*/int i,j;DataType t;for(i=1;ilength;i+)/*前i個(gè)元素已經(jīng)有序，從第i+1個(gè)元素開(kāi)始與前i個(gè)有序的關(guān)鍵字比較*/t=L->datai+1;/*取出第i+1個(gè)元素，即待排序的元素*/j=i;while(j>0/*將當(dāng)前元素插入合適的位置*/,7.2 插入排序,7.2.2 折半插入排序 折半插入排序算法是直接插入排序的改進(jìn)。它的主要改進(jìn)在于，在已經(jīng)有序的集合中使用折半查找法確定待排序元素的插入位置。在找到要插入的位置后，將待排序元素插入到相應(yīng)的位置。 假設(shè)待排序元素有7個(gè)：67、53、73、21、34、98、12。使用折半插入排序?qū)υ撛匦蛄械谝惶伺判蜻^(guò)程如圖7.6所示。,7.2 插入排序,第2趟折半插入排序過(guò)程如圖7.7所示。,7.2 插入排序,void BinInsertSort(SqList *L)/*折半插入排序*/int i,j,mid,low,high;DataType t;for(i=1;ilength;i+)t=L->datai+1;/*取出第i+1個(gè)元素，即待排序的元素*/low=1,high=i;while(lowdatamid.key>t.key)high=mid-1;elselow=mid+1;for(j=i;j>=low;j-)/*移動(dòng)元素，空出要插入的位置*/L->dataj+1=L->dataj;L->datalow=t;/*將當(dāng)前元素插入合適的位置*/,7.2 插入排序,7.2.3 希爾排序 希爾排序（shells sort）也稱為縮小增量排序（diminishing increment sort），它也屬于插入排序類的算法，但時(shí)間效率比前幾種排序有較大改進(jìn)。 設(shè)待排序元素為：48、26、66、57、32、85、55、19，使用希爾排序算法對(duì)該元素序列的排序過(guò)程如圖7.8所示。,7.2 插入排序,相應(yīng)地，希爾排序的算法可描述如下。void ShellInsert(SqList *L,int c)/*對(duì)順序表L進(jìn)行一次希爾排序，c是增量*/int i,j;DataType t;for(i=c+1;ilength;i+)/*將距離為c的元素作為一個(gè)子序列進(jìn)行排序*/if(L->datai.keydatai-c.key)/*如果后者小于前者，則需要移動(dòng)元素*/t=L->datai;for(j=i-c;j>0/*依次將元素插入到正確的位置*/,7.2 插入排序,void ShellInsertSort(SqList *L,int delta,int m)/*希爾排序，每次調(diào)用算法ShellInsert,delta是存放增量的數(shù)組*/int i;for(i=0;i<m;i+)/*進(jìn)行m次希爾插入排序*/ShellInsert(L,deltai); 希爾排序的分析是一個(gè)非常復(fù)雜的事情，問(wèn)題主要在于希爾排序選擇的增量，但是經(jīng)過(guò)大量的研究，當(dāng)增量的序列為2m-k+1-1時(shí)，其中m為排序的次數(shù)，1kt，其時(shí)間復(fù)雜度為O(n3/2)。希爾排序的空間復(fù)雜度為O(1)。,7.2 插入排序,7.2.4 插入排序應(yīng)用舉例 【例7_1】任意給定一組元素序列，利用直接插入排序、折半插入排序和希爾排序?qū)υ撔蛄羞M(jìn)行排序。 【分析】主要考察直接插入排序、折半插入排序和希爾排序的算法思想。,7.2 插入排序,【例7_2】編寫一個(gè)插入排序算法，要求用鏈表實(shí)現(xiàn)?！痉治觥恐饕疾觳迦肱判虻乃惴ㄋ枷牒玩湵淼牟僮鳌Ｋ惴ㄋ枷耄菏紫葎?chuàng)建一個(gè)鏈表，將待排序元素依次插入到鏈表中。將待排序鏈表分為兩個(gè)部分：有序序列和待排序序列。初始時(shí)，有序序列中沒(méi)有元素，令L->next=NULL。指針p指向待排序的鏈表，若有序序列為空，將p指向的第一個(gè)結(jié)點(diǎn)插入到空鏈表L中。然后將有序鏈表即L指向的鏈表的每一個(gè)結(jié)點(diǎn)與p指向的結(jié)點(diǎn)比較，并將結(jié)點(diǎn)*p插入到L指向的鏈表的恰當(dāng)位置。重復(fù)執(zhí)行上述操作，直到待排序鏈表為空。此時(shí)，L就是一個(gè)有序鏈表。,7.3 交換排序,7.3.1 冒泡排序 冒泡排序(bubble sort)是一種簡(jiǎn)單的交換類排序算法，它是通過(guò)交換相鄰的兩個(gè)數(shù)據(jù)元素，逐步將待排序序列變成有序序列。它的基本算法思想描述如下： 假設(shè)待排序元素有n個(gè)，從第1個(gè)元素開(kāi)始，依次交換相鄰的兩個(gè)逆序元素，直到最后一個(gè)元素為止。當(dāng)?shù)?趟排序結(jié)束，就會(huì)將最大的元素移動(dòng)到序列的末尾。然后按照以上方法進(jìn)行第2趟排序，次大的元素將會(huì)被移動(dòng)到序列的倒數(shù)第2個(gè)位置。依次類推，經(jīng)過(guò)n-1趟排序后，整個(gè)元素序列就成了一個(gè)有序的序列。每趟排序過(guò)程中，值小的元素向前移動(dòng)，值大的元素向后移動(dòng)，就像氣泡一樣向上升，因此將這種排序方法稱為冒泡排序。,7.3 交換排序,例如，有5個(gè)待排序元素55、26、48、63和37。第1趟排序：,7.3 交換排序,第2趟排序：從第1個(gè)元素開(kāi)始，依次比較第1個(gè)元素與第2個(gè)元素、第2個(gè)元素與第3個(gè)元素、第3個(gè)元素與第4個(gè)元素，如果前者大于后者，則交換之；否則不進(jìn)行交換。第2趟排序過(guò)程如圖7.12所示。,7.3 交換排序,第3趟排序：按照以上方法，依次比較兩個(gè)相鄰元素，交換逆序的元素。第3趟排序過(guò)程如圖7.13所示。 第4趟排序：此時(shí)，待排序元素只剩下26和37，只需要進(jìn)行一次比較即可。因?yàn)?6<37，所以不需要交換。第4趟排序過(guò)程如圖7.14所示。,7.3 交換排序,設(shè)待排序元素為56、72、44、31、99、21、69、80，使用冒泡排序?qū)υ撛匦蛄械呐判蜻^(guò)程如圖7.15所示。,7.3 交換排序,冒泡排序的算法描述如下。void BubbleSort(SqList *L,int n)/*冒泡排序*/int i,j,flag;DataType t;for(i=1;idataj.key>L->dataj+1.key)t=L->dataj;L->dataj=L->dataj+1;L->dataj+1=t;flag=1;,7.3 交換排序,快速排序的算法思想是：從待排序記錄序列中選取一個(gè)記錄（通常是第一個(gè)記錄）作為樞軸，其關(guān)鍵字設(shè)為key，然后將其余關(guān)鍵字小于key的記錄移至前面，而將關(guān)鍵字大于key的記錄移至后面，結(jié)果將待排序記錄序列分為兩個(gè)子表，最后將關(guān)鍵字key的記錄插入到其分界線的位置。我們將這個(gè)過(guò)程稱為一趟快速排序。通過(guò)這一趟劃分后，就以關(guān)鍵字為key的記錄為界，將待排序序列分為兩個(gè)子表，前面的子表所有記錄的關(guān)鍵字均不大于key，而后面子表的所有記錄的關(guān)鍵字均不小于key。繼續(xù)對(duì)分割后的子表進(jìn)行上述劃分，直至所有子表的表長(zhǎng)不超過(guò)1為止，此時(shí)的待排序記錄就成了一個(gè)有序序列。,7.3 交換排序,【算法步驟】設(shè)待排序序列存放在數(shù)組a1n中，n為元素個(gè)數(shù)，設(shè)置兩個(gè)指針i和j，初值分別為1和n，令a1作為樞軸元素賦給pivot，a1相當(dāng)于空單元，然后執(zhí)行以下操作： （1）j從右往左掃描，若aj.keypivot.key，將ai移至aj中，并執(zhí)行一次j-操作； （3）重復(fù)執(zhí)行（1）和（2），直到出現(xiàn)ij，則將元素pivot移動(dòng)到ai中。此時(shí)整個(gè)元素序列在位置i被劃分成兩個(gè)部分，前一部分的元素關(guān)鍵字都小于ai.key，后一部分元素的關(guān)鍵字都大于等于ai.key。即完成了一趟快速排序。,7.3 交換排序,例如，一組待排序元素序列為55,22,44,67,35,77,18,69，依據(jù)快速排序的算法思想，得到第1趟排序的過(guò)程如圖7.16所示。,7.3 交換排序,設(shè)待排序元素為55、22、44、67、35、77、18、69，用快速排序算法對(duì)該元素序列的排序過(guò)程如圖7.17所示。,7.3 交換排序,進(jìn)行一趟快速排序，即將元素序列進(jìn)行一次劃分的算法描述如下所示。int Partition(SqList *L,int low,int high)/*對(duì)順序表L.rlow.high的元素進(jìn)行一趟排序，使樞軸前面的元素關(guān)鍵字小于樞軸元素的關(guān)鍵字，樞軸后面的元素關(guān)鍵字大于等于樞軸元素的關(guān)鍵字，并返回樞軸位置*/ DataType t;KeyType pivotkey;pivotkey=(*L).datalow.key;/*將表的第一個(gè)元素作為樞軸元素*/t=(*L).datalow;while(low=pivotkey)/*從表的末端向前掃描*/high-;if(low<high)/*將當(dāng)前high指向的元素保存在low位置*/(*L).datalow=(*L).datahigh;low+;,while(low<high/*返回樞軸所在位置*/,7.3 交換排序,7.3 交換排序,通過(guò)多次遞歸調(diào)用一次劃分算法即一趟排序算法，可實(shí)現(xiàn)快速排序，其算法描述如下所示。void QuickSort(SqList *L,int low,int high)/*對(duì)順序表L進(jìn)行快速排序*/ int pivot;if(low<high)/*如果元素序列的長(zhǎng)度大于1*/ pivot=Partition(L,low,high);/*將待排序序列L.rlow.high劃分為兩部分*/QuickSort(L,low,pivot-1);/*對(duì)左邊的子表進(jìn)行遞歸排序，pivot是樞軸位置*/QuickSort(L,pivot+1,high);/*對(duì)右邊的子表進(jìn)行遞歸排序*/,7.3 交換排序,快速排序在最好的情況下是每趟排序?qū)⑿蛄幸环謨砂耄瑥谋碇虚g開(kāi)始，將表分成兩個(gè)大小相同的子表，類似折半查找，這樣快速排序的劃分的過(guò)程就將元素序列構(gòu)成一個(gè)完全二叉樹(shù)的結(jié)構(gòu)，分解的次數(shù)等于樹(shù)的深度即log2n，因此快速排序總的比較次數(shù)為 T(n)n+2T(n/2)n+2*(n/2+2*T(n/4)= 2n+4T(n/4)3n+8T(n/8)nlog2n+nT(1)。 因此，在最好的情況下，時(shí)間復(fù)雜度為O(nlog2n)。,7.3.3 交換排序應(yīng)用舉例【例7_3】編寫算法，使用冒泡排序和快速排序算法對(duì)給定的一組關(guān)鍵字序列(37,22,43,32,19,12,89,26,48,92)進(jìn)行排序，并輸出每趟排序結(jié)果?！痉治觥恐饕疾靸煞N交換排序即冒泡排序和快速排序的算法思想。這兩種算法都是對(duì)存在逆序的元素進(jìn)行交換，從而實(shí)現(xiàn)排序。主要區(qū)別在于：冒泡排序通過(guò)比較相鄰的兩個(gè)元素，并對(duì)兩個(gè)相鄰的逆序元素進(jìn)行交換；而快速排序則是選定一個(gè)樞軸元素作為參考元素，設(shè)置兩個(gè)指針，分別從表頭和表尾開(kāi)始，將當(dāng)前掃描的元素與樞軸元素進(jìn)行比較，存在逆序的元素不一定是相鄰的元素，如果存在逆序，則交換之。,7.3 交換排序,7.4.1 簡(jiǎn)單選擇排序 簡(jiǎn)單選擇排序是一種簡(jiǎn)單的選擇類排序算法，它是通過(guò)依次找到待排序元素序列中最小的數(shù)據(jù)元素，并將其放在序列的最前面，從而使待排序元素序列變?yōu)橛行蛐蛄?。它的基本算法思想描述如下?假設(shè)待排序的元素序列有n個(gè)，在第一趟排序過(guò)程中，從n個(gè)元素序列中選擇最小的元素，并將其放在元素序列的最前面即第一個(gè)位置。在第二趟排序過(guò)程中，從剩余的n-1個(gè)元素中，選擇最小的元素，將其放在第二個(gè)位置。依次類推，直到?jīng)]有待比較的元素，簡(jiǎn)單選擇排序算法結(jié)束。,7.4 選擇排序,簡(jiǎn)單選擇排序的算法描述如下。void SelectSort(SqList *L,int n)/*簡(jiǎn)單選擇排序*/int i,j,k;DataType t;/*將第i個(gè)元素的關(guān)鍵字與后面i+1.n個(gè)元素的關(guān)鍵字比較，將關(guān)鍵字最小的的元素放在第i個(gè)位置*/for(i=1;idatak.keydataj.key)j=k;if(j!=i)/*如果序號(hào)i不等于j，則需要將序號(hào)i和序號(hào)j的元素交換*/t=L->datai;L->datai=L->dataj;L->dataj=t;,7.4 選擇排序,7.4 選擇排序,一組元素的關(guān)鍵字序列為(76,31,19,20,6,83,60,52)，簡(jiǎn)單選擇排序的過(guò)程如圖7.19所示。,7.4.2 堆排序 1什么是堆和堆排序 堆排序(heap sort) 主要是利用了二叉樹(shù)的樹(shù)形結(jié)構(gòu)，按照完全二叉樹(shù)的編號(hào)次序，將元素序列的關(guān)鍵字依次存放在相應(yīng)的結(jié)點(diǎn)。然后從葉子結(jié)點(diǎn)開(kāi)始，從互為兄弟的兩個(gè)結(jié)點(diǎn)中（沒(méi)有兄弟結(jié)點(diǎn)除外），選擇一個(gè)較大（或較?。┱吲c其雙親結(jié)點(diǎn)比較，如果該結(jié)點(diǎn)大于（或小于）雙親結(jié)點(diǎn)，則將兩者進(jìn)行交換，使較大（或較小）者成為雙親結(jié)點(diǎn)。將所有的結(jié)點(diǎn)都做類似操作，直到根結(jié)點(diǎn)為止。這時(shí)，根結(jié)點(diǎn)的元素值的關(guān)鍵字最大（或最?。?。,7.4 選擇排序,這樣就構(gòu)成了堆，堆中的每一個(gè)結(jié)點(diǎn)都大于（或小于）其孩子結(jié)點(diǎn)。堆的數(shù)學(xué)形式定義為：假設(shè)存在n個(gè)元素，其關(guān)鍵字序列為(k1,k2,ki,kn)，如果有： 則稱此元素序列構(gòu)成了一個(gè)堆。如果將這些元素的關(guān)鍵字存放在一維數(shù)組中，將此一維數(shù)組中的元素與完全二叉樹(shù)一一對(duì)應(yīng)起來(lái)，則完全二叉樹(shù)中的每個(gè)非葉子結(jié)點(diǎn)的值都不小于（或不大于）孩子結(jié)點(diǎn)的值。,7.4 選擇排序,在堆中，堆的根結(jié)點(diǎn)元素值一定是所有結(jié)點(diǎn)元素值的最大值或最小值。例如，序列（89,77,65,62,32,55,60,48）和（18,37,29,48,50,43,33,69,77,60）都是堆，相應(yīng)的完全二叉樹(shù)表示如圖7.20所示。,7.4 選擇排序,如果將堆中的根結(jié)點(diǎn)（堆頂）輸出之后，然后將剩余的n-1個(gè)結(jié)點(diǎn)的元素值重新建立一個(gè)堆，則新堆的堆頂元素值是次大（或次?。┲?，將該堆頂元素輸出。然后將剩余的n-2個(gè)結(jié)點(diǎn)的元素值重新建立一個(gè)堆，反復(fù)執(zhí)行以上操作，直到堆中沒(méi)有結(jié)點(diǎn)，就構(gòu)成了一個(gè)有序序列，這樣的重復(fù)建堆并輸出堆頂元素的過(guò)程稱為堆排序。,7.4 選擇排序,2建堆 堆排序的過(guò)程就是建立堆和不斷調(diào)整使剩余結(jié)點(diǎn)構(gòu)成新堆的過(guò)程。假設(shè)將待排序的元素的關(guān)鍵字存放在數(shù)組a中，第1個(gè)元素的關(guān)鍵字a1表示二叉樹(shù)的根結(jié)點(diǎn)，剩下的元素的關(guān)鍵字a a2n分別與二叉樹(shù)中的結(jié)點(diǎn)按照層次從左到右一一對(duì)應(yīng)。例如，a1的左孩子結(jié)點(diǎn)存放在a2中，右孩子結(jié)點(diǎn)存放在a3中，ai的左孩子結(jié)點(diǎn)存放在a2*i中，右孩子結(jié)點(diǎn)存放在a2*i+1中。,7.4 選擇排序,例如，給定一組元素序列(27,58,42,53,42,69,50,62)，建立大頂堆的過(guò)程如圖7.21所示。,7.4 選擇排序,相應(yīng)地，建立大頂堆的算法描述如下所示。void CreateHeap(SqList *H,int n)/*建立大頂堆*/int i;for(i=n/2;i>=1;i-)/*從序號(hào)n/2開(kāi)始建立大頂堆*/AdjustHeap(H,i,n);,7.4 選擇排序,void AdjustHeap(SqList *H,int s,int m)/*調(diào)整H.datas.m的關(guān)鍵字，使其成為一個(gè)大頂堆*/ DataType t;int j;t=(*H).datas;/*將根結(jié)點(diǎn)暫時(shí)保存在t中*/for(j=2*s;j(*H).dataj.key)/*如果孩子結(jié)點(diǎn)的值小于根結(jié)點(diǎn)的值，則不進(jìn)行交換*/break;(*H).datas=(*H).dataj;s=j;(*H).datas=t;/*將根結(jié)點(diǎn)插入到正確位置*/,7.4 選擇排序,3調(diào)整堆 具體實(shí)現(xiàn)：當(dāng)堆頂元素輸出后，可以將堆頂元素放在堆的最后，即將第1個(gè)元素與最后一個(gè)元素交換a1an，則需要調(diào)整的元素序列就是a1n-1。從根結(jié)點(diǎn)開(kāi)始，如果其左、右子樹(shù)結(jié)點(diǎn)元素值大于根結(jié)點(diǎn)元素值，選擇較大的一個(gè)進(jìn)行交換。即如果a2>a3，則將a1與a2比較，如果a1>a2，則將a1與a2交換，否則不交換。如果a2a3，則將a1與a3交換，否則不交換。重復(fù)執(zhí)行此操作，直到葉子結(jié)點(diǎn)不存在，就完成了堆的調(diào)整，構(gòu)成了一個(gè)新堆。,7.4 選擇排序,7.4 選擇排序,例如，一個(gè)大頂堆的關(guān)鍵字序列為(69,62,50,58,42,42,27,53)，當(dāng)輸出69后，調(diào)整剩余的元素序列為大頂堆的過(guò)程如圖7.22所示。,7.4 選擇排序,調(diào)整堆的算法實(shí)現(xiàn)如下。void HeapSort(SqList *H)/*對(duì)順序表H進(jìn)行堆排序*/ DataType t;int i;CreateHeap(H,H->length);/*創(chuàng)建堆*/for(i=(*H).length;i>1;i-)/*將堆頂元素與最后一個(gè)元素交換，重新調(diào)整堆*/ t=(*H).data1;(*H).data1=(*H).datai;(*H).datai=t;AdjustHeap(H,1,i-1);/*將(*H).data1.i-1調(diào)整為大頂堆*/,7.4 選擇排序,例如，一個(gè)大頂堆的元素的關(guān)鍵字序列為(69,62,50,58,42,42,27,53)，其相應(yīng)的完整的堆排序過(guò)程如圖7.23所示。,7.4 選擇排序,7.4.3 選擇排序應(yīng)用舉例【例7_4】編寫算法，利用簡(jiǎn)單選擇排序和堆排序算法對(duì)一組關(guān)鍵字序列 (69,62,50,58,42,42,27,53)進(jìn)行排序，要求輸出每趟排序的結(jié)果。【分析】簡(jiǎn)單選擇排序和堆排序都是一種不穩(wěn)定的排序方法。它們的主要思想：每次從待排序元素中選擇關(guān)鍵字最?。ɑ蜃畲螅┑脑?，經(jīng)過(guò)不斷交換，重復(fù)執(zhí)行以上操作，最后形成一個(gè)有序的序列。,7.4 選擇排序,【例7_5】編寫算法，對(duì)關(guān)鍵字序列(76,20,99,32,60,53,11,8,42)進(jìn)行選擇排序，要求使用鏈表實(shí)現(xiàn)?！痉治觥恐饕疾爝x擇排序的算法思想和鏈表的操作。具體實(shí)現(xiàn)時(shí)，設(shè)置兩個(gè)指針p和q，分別指向已排序鏈表和未排序鏈表。初始時(shí)，先創(chuàng)建一個(gè)鏈表，q指向該鏈表，p指向的鏈表為空。然后從q指向的鏈表中找到一個(gè)元素值最小的結(jié)點(diǎn)，將其取出并插入到p指向的鏈表中。重復(fù)執(zhí)行以上操作直到q指向的鏈表為空，此時(shí)p指向的鏈表就是一個(gè)有序鏈表。,7.5 歸并排序,7.5.1 2路歸并排序算法 主要思想是：假設(shè)元素的個(gè)數(shù)是n，將每個(gè)元素作為一個(gè)有序的子序列，然后將相鄰的兩個(gè)子序列兩兩歸并，得到個(gè)長(zhǎng)度為2的有序子序列。然后將相鄰的兩個(gè)有序子序列兩兩歸并，得到個(gè)長(zhǎng)度為4的有序子序列。如此重復(fù)，直至得到一個(gè)長(zhǎng)度為n的有序序列為止。 關(guān)鍵字序列(50,22,61,35,87,12,19,75)的2路歸并排序的過(guò)程如圖7.26所示。,7.5 歸并排序,void Merge(DataType s,DataType t,int low,int mid,int high)/*將有序的slow.mid和smid+1.high歸并為有序的tlow.high*/ int i,j,k;i=low,j=mid+1,k=low;while(i<=mid,7.5 歸并排序,void MergeSort(DataType s,DataType t,int low, int high)/*2路歸并排序，將slow.high歸并排序并存儲(chǔ)到tlow.high中*/ int mid;DataType t2MaxSize;if(low=high)tlow=slow;elsemid=(low+high)/2;/*將slow.high分為slow.mid和smid+1.high*/MergeSort(s,t2,low,mid);/*將slow.mid歸并為有序的t2low.mid*/MergeSort(s,t2,mid+1,high);/*將smid+1.high歸并為有序的t2mid+1.high*/Merge(t2,t,low,mid,high);/*將t2low.mid和t2mid+1.high歸并到tlow.high*/,7.5 歸并排序,7.5.2 歸并排序應(yīng)用舉例【例7_6】編寫算法，請(qǐng)使用2路歸并排序?qū)σ唤M關(guān)鍵字 (50,22,61,35,87,12,19,75)進(jìn)行排序。,7.6 基數(shù)排序,7.6.1 基數(shù)排序算法 基數(shù)排序正是借助這種思想，對(duì)不同類的元素進(jìn)行分類，然后對(duì)同一類中的元素進(jìn)行排序，通過(guò)這樣的一種過(guò)程，完成對(duì)元素序列的排序。在基數(shù)排序中，通常將對(duì)不同元素的分類稱為分配，排序的過(guò)程稱為收集。 具體算法思想：假設(shè)第i個(gè)元素ai的關(guān)鍵字keyi，keyi是由d位十進(jìn)制組成，即keyi=kidkid-1ki1，其中ki1為最低位，kid為最高位。關(guān)鍵字的每一位數(shù)字都可作為一個(gè)子關(guān)鍵字。首先將元素序列按照最低的關(guān)鍵字進(jìn)行排序，然后從低位到高位直到最高位依次進(jìn)行排序，這樣就完成了排序過(guò)程。,7.6 基數(shù)排序,例如，一組元素的關(guān)鍵字序列為(236,128,34,567,321,793,317,106)。 對(duì)最低位進(jìn)行分配和收集的過(guò)程如圖7.28所示。其中，數(shù)組fi保存第i個(gè)鏈表的頭指針，數(shù)組ri保存第i個(gè)鏈表的尾指針。,7.6 基數(shù)排序,對(duì)十位數(shù)字分配和收集的過(guò)程如圖7.29所示。對(duì)百位數(shù)字分配和收集的過(guò)程如圖7.30所示。,7.6 基數(shù)排序,基數(shù)排序的算法主要包括分配和收集。靜態(tài)鏈表類型定義描述如下：#define MaxNumKey 6 /*關(guān)鍵字項(xiàng)數(shù)的最大值*/#define Radix 10/*關(guān)鍵字基數(shù)，此時(shí)是十進(jìn)制整數(shù)的基數(shù)*/#define MaxSize 1000typedef int KeyType;typedef structKeyType keyMaxNumKey; /*關(guān)鍵字*/int next;SListCell;/*靜態(tài)鏈表的結(jié)點(diǎn)類型*/typedef structSListCell dataMaxSize;/*存儲(chǔ)元素，data0為頭結(jié)點(diǎn)*/int keynum;/*每個(gè)元素的當(dāng)前關(guān)鍵字個(gè)數(shù)*/int length;/*靜態(tài)鏈表的當(dāng)前長(zhǎng)度*/SList;/*靜態(tài)鏈表類型*/typedef int addrRadix; /*指針數(shù)組類型*/,7.6 基數(shù)排序,基數(shù)排序的分配算法實(shí)現(xiàn)如下所示。void Distribute(SListCell data,int i,addr f,addr r) /*為data中的第i個(gè)關(guān)鍵字keyi建立Radix個(gè)子表，使同一子表中元素的keyi相同*/*f0.Radix-1和r0.Radix-1分別指向各個(gè)子表中第一個(gè)和最后一個(gè)元素*/ int j,p;for(j=0;j<Radix;j+)/*將各個(gè)子表初始化為空表*/fj=0;for(p=data0.next;p;p=datap.next)j=trans(datap.keyi);/*將關(guān)鍵字字符轉(zhuǎn)化為整數(shù)類型*/if(!fj)/*fj是空表，則fj指示第一個(gè)元素*/fj=p;elsedatarj.next=p;rj=p;/*將p所指的結(jié)點(diǎn)插入第j個(gè)子表中*/,7.6 基數(shù)排序,其中，數(shù)組fj和數(shù)組rj分別存放第j個(gè)子表的第一個(gè)元素的位置和最后一個(gè)元素的位置?；鶖?shù)排序的收集算法實(shí)現(xiàn)如下所示。void Collect(SListCell data,addr f,addr r)/*按keyi將f0.Radix-1所指各子表依次鏈接成一個(gè)靜態(tài)鏈表*/ int j,t;for(j=0;!fj;j+);/*找第一個(gè)非空子表，succ為求后繼函數(shù)*/data0.next=fj;t=rj;/*r0.next指向第一個(gè)非空子表中第一個(gè)結(jié)點(diǎn)*/while(j<Radix-1)for(j=j+1;j<Radix-1/*t指向最后一個(gè)非空子表中的最后一個(gè)結(jié)點(diǎn)*/,7.6 基數(shù)排序,基數(shù)排序通過(guò)多次調(diào)用分配算法和收集算法，從而實(shí)現(xiàn)排序，其算法實(shí)現(xiàn)如下所示。 void RadixSort(SList *L) /*對(duì)L進(jìn)行基數(shù)排序，使得L成為按關(guān)鍵字非遞減的靜態(tài)鏈表，L.r0為頭結(jié)點(diǎn)*/ int i; addr f,r; for(i=0;i<(*L).keynum;i+)/*由低位到高位依次對(duì)各關(guān)鍵字進(jìn)行分配和收集*/ Distribute(*L).data,i,f,r);/*第i趟分配*/Collect(*L).data,f,r);/*第i趟收集*/ ,7.7 小結(jié),排序可分為插入排序、選擇排序、交換排序、歸并排序和基數(shù)排序。 直接插入排序算法實(shí)現(xiàn)最為簡(jiǎn)單，時(shí)間復(fù)雜度在最好、最壞和平均情況下都為(n2)。 簡(jiǎn)單選擇排序算法的時(shí)間復(fù)雜度在最好、最壞和平均情況下都是O(n2)，而堆排序的時(shí)間復(fù)雜度在最好、最壞和平均情況下都是O(nlog2n)。 冒泡排序的平均時(shí)間復(fù)雜度為O(n2)，快速排序在最好和平均情況下時(shí)間復(fù)雜度為O(nlog2n)，最壞情況下時(shí)間復(fù)雜度為O(n2)。 歸并排序時(shí)間復(fù)雜度在最好、最壞和平均情況下都為O(nlog2n)。 基數(shù)排序是一種不需要對(duì)關(guān)鍵字進(jìn)行比較的一種排序算法。在任何情況下，基數(shù)排序的時(shí)間復(fù)雜度均為O(d(n+rd)。 從穩(wěn)定性來(lái)看，直接插入排序、冒泡排序、歸并排序和基數(shù)排序?qū)儆诜€(wěn)定的排序算法，希爾排序、快速排序、簡(jiǎn)單選擇排序、堆排序?qū)儆诓环€(wěn)定的排序算法。,