排序教學講解課件

算法與數據結構

教師：算法與數據結構

第四部分集合結構集合中的元素互相之間沒有關系集合的存儲：借用其他容器集合的操作：查找和排序這一部分將介紹查找表(靜態(tài)查找表、動態(tài)查找表)散列表排序算法第四部分集合結構集合中的元素互相之間沒有關系第12章排序12.1排序的基本概念12.2插入排序12.3交換排序12.4選擇排序12.5歸并排序*12.6基數排序12.7

各種內部排序方法的比較*12.8外部排序*內容可不講第12章排序12.1排序的基本概念排序問題Google等搜索引擎返回結果排級圖書館員書目編號、上架各種排名大學排名考試成績排名《福布斯》富豪榜Windows資源管理器，文件查看……排序問題Google等搜索引擎返回結果排級所謂排序就是把集合中的數據元素按照它們的關鍵字的非遞減或非遞增序排成一個序列。內排序與外排序：內排序是指被排序的數據元素全部存放在計算機的內存之中，并且在內存中調整數據元素的相對位置。外排序是指在排序的過程中，數據元素主要存放在外存儲器中，借助于內存儲器逐步調整數據元素之間的相對位置。排序的基本概念所謂排序就是把集合中的數據元素按照它們的關鍵字的非遞減或非遞穩(wěn)定排序存在多個具有相同排序碼的記錄排序后這些記錄的相對次序保持不變穩(wěn)定性例1

341234’0896081234

34’96

穩(wěn)定！排序的基本概念穩(wěn)定排序穩(wěn)定！排序的基本概念穩(wěn)定性存在多個具有相同排序碼的記錄排序后這些記錄的相對次序保持不變穩(wěn)定性例2

341234’0896081234’

3496

不穩(wěn)定！排序的基本概念穩(wěn)定性不穩(wěn)定！排序的基本概念排序算法的衡量標準時間代價

記錄的比較和移動次數空間代價算法本身的繁雜程度排序算法的衡量標準時間代價第12章排序12.1排序的基本概念12.2插入排序12.2.1直接插入排序12.2.2折半插入排序12.2.3希爾排序12.3交換排序12.4選擇排序12.5歸并排序*12.6基數排序12.7

各種內部排序方法的比較*12.8外部排序第12章排序12.1排序的基本概念直接插入排序直接插入排序（StraightInsertionSort）：假設在排序過程中，記錄序列為R[0..n-1]，首先將第一個記錄R[0]看做一個有序子序列，然后依次將記錄R[i]（1≤i≤n-1）插入到有序子序列R[0..i-1]中，使記錄的有序子序列從R[0..i-1]變?yōu)镽[0..i]。

直接插入排序直接插入排序（StraightInsertio直接插入排序算法與數據結構直接插入排序算法與數據結構直接插入排序1234’322964453478

發(fā)現逆序對，交換嗎？直接插入排序1234’322964453478發(fā)現逆序對，[代碼12.1]template<classType>voidstraightInsertSort(TypeR[],intsize){intpos,j; //pos為待插入記錄位置Typetmp;for(pos=1;pos<size;pos++){tmp=R[pos]; //將待插入記錄放進臨時變量

//從后向前查找插入位置for(j=pos-1;tmp<R[j]&&j>=0;j--)

R[j+1]=R[j];

//將大于待插入記錄的記錄向后移動R[j+1]=tmp; //將待插入記錄放到合適位置}}算法與數據結構直接插入排序[代碼12.1]算法與數據結構直接插入排序算法分析穩(wěn)定空間代價：O(1)時間代價：最佳情況：n-1次比較，2(n-1)次移動，Θ(n)最差情況：O(n2)

比較次數為移動次數為平均情況：O(n2)

適用情況：排序元數較少，且?guī)缀跏且雅判虻乃惴ǚ治龇€(wěn)定2022/11/2215直接插入排序的優(yōu)缺點直接插入排序算法簡單,當待排序記錄數量n很小時,局部有序時,較為適用。當n很大時,其效率不高。若對直接插入排序算法進行改進,可從減少“比較”和“移動”次數這兩方面著手。折半存入排序、二路插入排序、表插入排序、希爾排序都是對直接插入排序的改進。2022/10/1115直接插入排序的優(yōu)缺點直接插入排序算法第12章排序12.1排序的基本概念12.2插入排序12.2.1直接插入排序12.2.2折半插入排序12.2.3希爾排序12.3交換排序12.4選擇排序12.5歸并排序*12.6基數排序12.7

各種內部排序方法的比較*12.8外部排序第12章排序12.1排序的基本概念

折半插入排序折半插入排序（BinaryInsertionSort）：當第i個記錄要插入前i－1個有序記錄序列時，可利用折半查找（在查找章節(jié)已介紹）方式確定插入位置，以減少比較次數。從而達到減少比較次數的目的[代碼12.2]template<classType>voidbinaryInsertSort(TypeR[],intsize){intpos,j,low,high,mid;Typetmp;折半插入排序折半插入排序（BinaryInsertionfor(pos=1;pos<size;pos++){//假定第一個記錄有序

tmp=R[pos]; //將待排記錄R[pos]暫存到tmp

low=0;high=pos-1;//設置折半查找的范圍while(low<=high){ //折半查找插入位置mid=(low+high)/2; //計算中間位置if(tmp<R[mid])high=mid-1;

elselow=mid+1; }for(j=pos-1;j>=low;j--)R[j+1]=R[j]; //記錄后移R[low]=tmp; //插入待排序記錄}}

折半插入排序for(pos=1;pos<size;pos折半插入排序比直接插入排序明顯地減少了關鍵字間的“比較”次數，但記錄“移動”的次數不變，故其時間復雜度仍為O（n2）。算法與數據結構算法分析折半插入排序比直接插入排序明顯地減少了關鍵字間的“比較”次數自測題1．對同一待排序列分別進行折半插入排序和直接插入排序，兩者之間可能的不同之處是（

）。A．排序的總趟數

B．元素的移動次數C．使用輔助空間的數量

D．元素之間的比較次數【2012年全國碩士研究生入學統(tǒng)一考試計算機學科專業(yè)基礎綜合】【參考答案】D算法與數據結構自測題1．對同一待排序列分別進行折半插入排序和直接插入排序，第12章排序12.1排序的基本概念12.2插入排序12.2.1直接插入排序12.2.2折半插入排序12.2.3希爾排序12.3交換排序12.4選擇排序12.5歸并排序*12.6基數排序12.7

各種內部排序方法的比較*12.8外部排序第12章排序12.1排序的基本概念希爾排序希爾排序（ShellSort）又稱為縮小增量排序，是由D.L.Shell在1959年提出的。Shell從“減少記錄個數”和“基本有序”兩方面對直接插入排序進行了改進。希爾排序的基本思想是：將待排序的記錄劃分成幾組，間距相同的記錄分在一組，對各組分別實施直接插入排序。當經過幾次分組排序后，記錄的排列已經基本有序，再對所有的記錄實施最后的直接插入排序。通過分組，一方面減少了參與直接插入排序的數據量；另一方面先比較那些間距較大的記錄，避免頻繁的移動相鄰記錄。當待排序記錄個數較少且待排序記錄已基本有序時，直接插入排序的效率是較高的。希爾排序希爾排序（ShellSort）又稱為縮小增量排序，希爾排序算法思想對于有n個記錄的初始序列，希爾排序的具體步驟如下：(1)首先取一個整數gap<n作為增量；(2)將全部記錄分為gap個子序列，所有間距為gap的記錄分在同一個子序列中，對每個子序列分別實施直接插入排序；(3)然后縮小增量gap，重復步驟(2)的子序列劃分和排序工作，直到最后gap等于1，將所有記錄放在一組，進行最后一次直接插入排序。希爾排序算法思想對于有n個記錄的初始序列，希爾排序的具體步驟Gap的選取

算法與數據結構Gap的選取

算法與數據結構希爾排序算法與數據結構希爾排序算法與數據結構希爾排序的實現若以Shell提出的分組方法，則Shell排序的算法如下[代碼12.3]template<classType>voidshellSort(TypeR[],intsize){intgap,pos,j; //gap為希爾增量，pos為待插入記錄位置

Typetmp;for(gap=size/2;gap>0;gap/=2){

for(pos=gap;pos<size;pos++){

tmp=R[pos];for(j=pos-gap;j>=0&&R[j]>tmp;j-=gap)R[j+gap]=R[j]; //記錄后移R[j+gap]=tmp; //將待插入記錄放到合適位置}}}希爾排序的實現若以Shell提出的分組方法，則Shell排性能分析不同的增量序列有不同的時間性能。希爾排序適用于待排序的記錄數目較大的情況。希爾排序存在大跨度的元素移動，是一種不穩(wěn)定的排序方法。希爾排序的時間性能與其選定的增量序列有關，有人在大量實驗的基礎上推導出，希爾排序的時間復雜度約為O（n1.3）?？臻g復雜度為O(1)。性能分析不同的增量序列有不同的時間性能。自測題2．用希爾排序方法對一個數據序列進行排序時，若第1趟排序結果為9，1，4，13，7，8，20，23，15，則該趟排序采用的增量（間隔）可能是（

）。A．2 B．3 C．4 D．5【2012年全國碩士研究生入學統(tǒng)一考試計算機學科專業(yè)基礎綜合】【參考答案】B算法與數據結構自測題2．用希爾排序方法對一個數據序列進行排序時，若第1趟排自測題3．希爾排序的組內排序采用的是（

）。A．直接插入排序

B．折半插入排序

C．快速排序

D．歸并排序【2015年全國碩士研究生入學統(tǒng)一考試計算機學科專業(yè)基礎綜合】【參考答案】A算法與數據結構自測題3．希爾排序的組內排序采用的是（）。算法與數據2022/11/2230*自測題：希爾排序二趟排序結果：171051／

33285152629687三趟排序結果：1017283351／

5152628796

初始關鍵字序列：5133629687172851／

5210

一趟排序結果：172851／

521051336296872022/10/1130*自測題：希爾排序二趟排序結果：2022/11/2231*自測題請給出對一組記錄（54,38,96,23,15,90,72,60,45,83）進行希爾排序（增量序列為5,3,1）時的排序過程。2022/10/1131*自測題請給出對一組記錄第12章排序12.1排序的基本概念12.2插入排序12.3交換排序12.3.1冒泡排序12.3.2快速排序12.4選擇排序12.5歸并排序*12.6基數排序12.7

各種內部排序方法的比較*12.8外部排序第12章排序12.1排序的基本概念冒泡排序冒泡排序(BubbleSort，也稱為起泡排序)是一種比較簡單的交換排序方法。它的基本思想是對所有相鄰記錄的關鍵字值進行比較，如果不滿足排序要求（即逆序），則將其交換，最終直到所有記錄排好序為止。冒泡排序冒泡排序(BubbleSort，也稱為起泡排序)冒泡排序對于由n個記錄序列的非遞減序冒泡排序的步驟如下：(1)將整個待排序的記錄序列劃分成有序區(qū)和無序區(qū)，初始狀態(tài)有序區(qū)為空，無序區(qū)包括所有待排序的記錄；(2)每一趟冒泡排序，對無序區(qū)從頭到尾比較相鄰記錄的關鍵字，若逆序，則交換。一趟排序后無序區(qū)中關鍵字值最大的記錄進入到有序區(qū)；(3)重復執(zhí)行步驟(2)，若在某一趟排序中沒有發(fā)生交換操作，說明待排序記錄已全部有序，排序提前結束。否則，最多需要經過n－1趟冒泡排序，才能將這n個記錄重新按關鍵字排好序。算法與數據結構冒泡排序對于由n個記錄序列的非遞減序冒泡排序的步驟如下：算法算法與數據結構冒泡排序算法與數據結構冒泡排序冒泡排序的實現冒泡排序算法如下。[代碼12.4]template<classType>voidbubbleSort(TypeR[],intsize){inti,j;boolflag=true; //記錄一趟排序后是否發(fā)生過交換for(i=1;i<size&&flag;++i){flag=false; //假定本趟排序沒有交換for(j=0;j<size-i;++j)if(R[j+1]<R[j]){ //逆序

swap(R[j],R[j+1]); //調用STL中的swap進行交換flag=true;}}}冒泡排序的實現冒泡排序算法如下。性能分析穩(wěn)定空間代價：O(1)時間代價分析：比較次數：最少：O(n)最多：交換次數最多為O(n2)，最少為0，平均為O(n2)。時間代價結論最大，平均時間代價均為O(n2)。最小時間代價為O(n)：最佳情況下只運行第一輪循環(huán)性能分析穩(wěn)定第12章排序12.1排序的基本概念12.2插入排序12.3交換排序12.3.1冒泡排序12.3.2快速排序12.4選擇排序12.5歸并排序*12.6基數排序12.7

各種內部排序方法的比較*12.8外部排序第12章排序12.1排序的基本概念快速排序快速排序(QuickSort)20世紀十大算法TopTenAlgorithmsoftheCentury1962London的ElliotBrothersLtd的TonyHoare提出的快速排序快速排序也稱分區(qū)交換排序，是對冒泡排序的改進。在冒泡排序中，記錄的比較和移動是在相鄰的位置進行的，記錄每次交換只能消除一個逆序，因而總的比較和移動次數較多。在快速排序中，通過分區(qū)間的一次交換能消除多個逆序。實際上，快速排序名副其實，它是目前最快的內部排序算法，被評為“20世紀十大算法”?？焖倥判蚩焖倥判?QuickSort)20世紀十大算法快速排序算法思想：選擇軸值（pivot）將序列劃分為兩個子序列L和R，使得L中所有記錄都小于或等于軸值，R中記錄都大于軸值，軸值處于子序列L和R之間，剛好在最終位置。對子序列L和R遞歸進行快速排序，直到子序列只有一個記錄為止。

基于分治法的排序：快速、歸并快速排序算法思想：選擇軸值待排序序列的第一個元素作為軸值對于隨機序列，這個選擇是可接受的。對于有序序列，這樣的軸值提供一個糟糕的劃分，所有的待排序數據都在軸值的一邊。因此，這種選擇在最壞情況下的時間復雜度是平方級的。隨機選擇一個軸值這樣很少有可能選到最差的元素。但隨機數的選擇也要花相當多的時間。取N個數的中值作為軸值對軸值的最好選擇顯然是這個中值，因為它保證對元素的均勻劃分。中值可以通過采樣來得到。選擇軸值待排序序列的第一個元素作為軸值如何劃分low、high分別用來指示左側記錄和右側記錄從右向左開始檢查。如果high的值大于軸tmp，該位置中的值位置正確，high減1，繼續(xù)往前檢查，直到遇到一個小于k的值。將小于k的這個值放入low的位置。此時high的位置又空出來了。然后從low位置開始從左向右檢查，直到遇到一個大于軸tmp的值。將low位置的值放入high位置，重復第一步，直到low和high重疊。將軸tmp放入此位置。如何劃分low、high分別用來指示左側記錄和右側記錄一趟快速排序例如，關鍵字序列S={36，80，45，66，22，9，16，36}。一趟快速排序的過程如下，首先，選取最左側的36作樞軸，暫存于臨時變量tmp中，相當于low指向空單元。(1)high從右向左掃描，遇到比36小的關鍵字16停止，置S[low]=S[high]。算法與數據結構一趟快速排序例如，關鍵字序列S={36，80，45，66，2(2)low從左向右掃描，遇到比36大的關鍵字80停止，置S[high]=S[low]。(3)high從右向左掃描，遇到比36小的關鍵字9停止，置S[low]=S[high]。算法與數據結構一趟快速排序(2)low從左向右掃描，遇到比36大的關鍵字80停止，置(4)low從左向右掃描，遇到比36大的關鍵字45停止，置S[high]=S[low]。(5)high從右向左掃描，遇到比36小的關鍵字22停止，置S[low]=S[high]。算法與數據結構一趟快速排序(4)low從左向右掃描，遇到比36大的關鍵字45停止，置(6)low從左向右掃描，遇到比36大的關鍵字66停止，置S[high]=S[low]。(7)high從右向左掃描遇到low，結束一次劃分，low=high的位置就是軸值36的最終位置，置S[low]=tmp。36左側的關鍵字均小于它，36右側的關鍵字均大于等于它。算法與數據結構一趟快速排序(6)low從左向右掃描，遇到比36大的關鍵字66停止，置遞歸快速排序如果有一個能夠完成劃分的函數partition，快速排序的實現將非常簡單?？焖倥判蚴怯眠f歸的方式實現的，它的遞歸參數就是排序的范圍[代碼12.6]遞歸快速排序。參數為待排序序列S，以及排序區(qū)間的下界low和上界high。template<classType>voidquickSort(TypeS[],intlow,inthigh){intpivot;if(low>=high)return;

pivot=partition(S,low,high);//一次劃分，返回樞軸位置quickSort(S,low,pivot-1); //對樞軸左邊一半快速排序quickSort(S,pivot+1,high); //對樞軸右邊一半快速排序}遞歸快速排序如果有一個能夠完成劃分的函數partition，[代碼12.5]一趟快速排序（或一次劃分）。參數為待排序序列S，以及排序區(qū)間的下界low和上界high。template<classType>intpartition(TypeS[],intlow,inthigh){ Typetmp=S[low]; //暫存軸值while(low!=high){ //開始進行分割while(low<high&&S[high]>=tmp)high--; //找<軸值的記錄if(low<high){S[low]=S[high];low++;}

//該記錄移動到小下標端while(low<high&&S[low]<=tmp)low++; //找>軸值的記錄if(low<high){S[high]=S[low];high--;}

//該記錄移動到大下標端}S[low]=tmp; //把軸值回填到分界位置上returnlow; //返回樞軸位置}一次劃分[代碼12.5]一趟快速排序（或一次劃分）。參數為待排序序列快速排序的接口函數快速排序的函數原型和其它的排序算法的函數原型都不同，它包含了兩個用于控制遞歸終止的參數。為了和其它的排序算法一致起來，我們在它外面再加一個接口函數，該函數調用了遞歸的quickSort函數。

[代碼12.7]快速排序的接口函數。參數為待排序序列S，以及序列大小size。template<classType>voidquickSort(TypeS[],intsize){

quickSort(S,0,size-1);}快速排序的接口函數快速排序的函數原型和其它的排序算法的函數原2022/11/2250性能分析平均時間復雜度為O（nlog2n）最差時間復雜度為O(n2)就平均時間而言，快速排序被認為是目前最好的內部排序方法。快速排序適用于記錄較多且基本無序的情況。由于排序過程中存在大跨度的數據移動，所以快速排序是一種不穩(wěn)定的排序方法。2022/10/1150性能分析平均時間復雜度為O（nlog2022/11/2251自測題

采用遞歸方式對順序表進行快速排序,下列關于遞歸次數的敘述中,正確的是A.遞歸次數與初始數據的排列次序無關B.每次劃分后,先處理較長的分區(qū)可以減少遞歸次數C.每次劃分后,先處理較短的分區(qū)可以減少遞歸次數D.遞歸次數與每次劃分后得到的分區(qū)處理順序無關【2010年全國碩士研究生入學統(tǒng)一考試計算機學科專業(yè)基礎綜合】D(若要減少遞歸深度選C)2022/10/1151自測題采用遞歸方式對順序表進行快自測題

為了實現快速排序算法，待排序序列宜采用的存儲方式是（）。A．順序存儲 B．散列存儲C．鏈式存儲 D．索引存儲【2011年全國碩士研究生入學統(tǒng)一考試計算機學科專業(yè)基礎綜合】【參考答案】A自測題為了實現快速排序算法，待排序序列宜采用的存儲方式是下列選項中，不可能是快速排序第2趟排序結果的是（

）。A．2,3,5,4,6,7,9 B．2,7,5,6,4,3,9 C．3,2,5,4,7,6,9 D．4,2,3,5,7,6,9【2014年全國碩士研究生入學統(tǒng)一考試計算機學科專業(yè)基礎綜合】【參考答案】C【題目解析】每趟快速排序后，至少一個記錄找到最終位置。自測題

下列選項中，不可能是快速排序第2趟排序結果的是（）。自2022/11/2254一組記錄的關鍵字為{46、79、56、38、40、84},則利用快速排序的方法,以第一個記錄為樞軸得到的一次劃分結果是A、38、40、46、56、79、84B、40、38、46、79、56、84C、40、38、46、56、79、84D、40、38、46、84、56、79【北京交通大學2005一.8(2分)】C（要注意交換位置）自測題

2022/10/1154一組記錄的關鍵字為{46、79、562022/11/2255對給定關鍵字序號j(1<j<n),要求在無序記錄A[1..n]中找到關鍵字從小到大排在第j位上的記錄,寫一個算法利用快速排序的劃分思想實現上述查找。(要求用最少的時間和最少的空間)

例如：給定無序關鍵字{7,5,1,6,2,8,9,3},當j=4時,找到的關鍵字應是5。

【中科院研究生院2003十二(15分)】

【武漢理工大學2002四.3(35/3分)】算法舉例2022/10/1155對給定關鍵字序號j(1<j<2022/11/2256intpartition(RecTypeA[],int1,intn){ inti=1,j=n;x=A[i].key; i=1; while(i<j)

{ while(i<j&&A[j].key>=x)j--; if(i<j)A[i++]=A[j]; while(i<j&&A[i].key<=x)i++; if(i<j)A[j--]=A[i];

} returni;}voidFind_j(RecTypeA[],intn,intj){ i=partition(A,1,n); while(i!=j) if(i<j)i=partition(A,i+1,n);∥在后半部分繼續(xù)進行劃分

elsei=partition(A,1,i-1);∥在前半部分繼續(xù)進行劃分}2022/10/1156intpartition(RecT第12章排序12.1排序的基本概念12.2插入排序12.3交換排序12.4選擇排序12.4.1直接選擇排序12.4.2堆排序*12.4.3錦標賽排序12.5歸并排序*12.6基數排序12.7

各種內部排序方法的比較*12.8外部排序第12章排序12.1排序的基本概念直接選擇排序直接選擇排序(StraightSelectionSort)是一種比較簡單的選擇排序方法，它的基本思想是：對于由n個記錄組成的記錄序列，第一趟，從n個記錄中選取關鍵字值最小的記錄與第一個記錄互換；第二趟，從剩余的n-1個記錄中選取關鍵字值最小的記錄與第二個記錄互換；一般地，第i趟，從剩余的n-i+1個記錄中選取關鍵字值最小的記錄與第i個記錄互換。重復以上過程，直到剩余記錄僅有一個為止。對k個元素而言，每次選出最小元素需要k-1次比較。因此排序一個n個元素組成的序列所需的比較次數為：

(n-1)+(n-2)+……+2+1=n(n-1)/2即O(n2)直接選擇排序直接選擇排序(StraightSelectio直接選擇排序示例1234’322964453478直接選擇排序示例1234’3229644534782022/11/22直接選擇排序示例初始關鍵字序列：5133629687172851／

↑↑第一趟排序后：[17]

33629687512851／↑↑第二趟排序后：[1728]

629687513351／↑↑第三趟排序后：[1728

33]

9687516251／第四趟排序后：[1728

3351]

87966251／第五趟排序后：[1728

3351

51／]966287第六趟排序后：[1728

3351

51／

62]

9687第七趟排序后：[1728

3351

51／

62

87

96]2022/10/11直接選擇排序示例初始關鍵字序列：5[代碼12.8]template<classType>voidstraightSelectSort(TypeR[],intsize){ intpos,min,j;//min為一趟排序中最小記錄下標//pos為待存放當前最小記錄的位置for(pos=0;pos<size-1;pos++){ min=pos;for(j=pos+1;j<size;++j)if(R[j]<R[min])min=j;//查找最小記錄//調用STL中的swap，頭文件algorithm

if(pos!=min)swap(R[pos],R[min]);

}}直接選擇排序[代碼12.8]直接選擇排序直接選擇排序性能分析不穩(wěn)定空間代價：O(1)時間代價：比較次數：O(n2)，與冒泡排序一樣交換次數：n-1總時間代價：O(n2)空間代價為O(1)

直接選擇排序性能分析不穩(wěn)定第12章排序12.1排序的基本概念12.2插入排序12.3交換排序12.4選擇排序12.4.1直接選擇排序12.4.2堆排序*12.4.3錦標賽排序12.5歸并排序*12.6基數排序12.7

各種內部排序方法的比較*12.8外部排序第12章排序12.1排序的基本概念堆排序堆排序（HeapSort）是由羅伯特·弗洛伊德(RobertW．Floyd）和威廉姆斯（J．williams）于1964年提出的一種基于堆結構的排序方法。直接選擇排序在n個記錄中選出關鍵字最?。ㄗ畲螅┑挠涗浶枰狾(n)的時間，而利用小根堆（大根堆）選出關鍵字最?。ㄗ畲螅┑挠涗浿恍枰狾(logn)的時間。排序N個元素，步驟如下：應用建堆操作對N個元素創(chuàng)建一個優(yōu)先級隊列通過調用N次出隊操作deQueue取出每個項，結果就排好序了。堆排序堆排序（HeapSort）是由羅伯特·弗洛伊德(Ro堆排序的基本思想是：(1)初始序列，建成一個大根堆（或小根堆）；(2)將堆頂的最大（或最?。┯涗浥c序列中最后一個記錄交換，則最大（或最?。┯涗洿娣旁跀到M末尾的有序段。(3)將序列中除末尾的有序段之外的剩余記錄重新調整為堆；(4)反復執(zhí)行步驟（2）、（3）共n-1次，若初始建立的是大根堆，則得到一個非遞減的序列；若初始建立的是小根堆，則得到一個非遞增的序列。算法與數據結構堆排序堆排序的基本思想是：算法與數據結構堆排序實現中的問題分析為了產生遞增排序，可以采用最大堆。在每一次deQueue后，堆縮小1。因此，在堆中的最后那個位置能被用來存儲剛被刪去的元素。實現中的問題分析最大值堆排序過程示意圖

78344534’122932最大值堆排序過程示意圖78344534’122932最大值堆排序過程示意圖

32344534’122978最大值堆排序過程示意圖32344534’122978最大值堆排序過程示意圖

453434’32122978最大值堆排序過程示意圖453434’32122978大根堆排序過程示意圖

343234’45122978大根堆排序過程示意圖343234’45122978堆排序示例關鍵字序列R={36，80，45，66，22，9，36，16}。為了產生非遞減的序列，初始建立大根堆：{80，66，45，36，22，9，36，16}，交換堆頂的最大元素80與序列中最后一個元素16之后，如圖(b)所示，有序段為：{80}；堆排序示例關鍵字序列R={36，80，45，66，22，9，剩余元素組成的子序列為：R1={16，66，45，36，22，9，36}，將該子序列重新調整為堆，如圖12.7(a)所示。交換堆頂的最大元素66與序列中最后一個元素36之后，如圖12.7(b)所示，有序段為：{66，80}算法與數據結構堆排序示例剩余元素組成的子序列為：R1={16，66，45，36，22剩余元素組成的子序列為：R2={36，36，45，16，22，9}，將該子序列重新調整為堆，如圖12.8(a)所示。交換堆頂的最大元素45與序列中最后一個元素9之后，如圖12.8(b)所示，有序段為：{45，66，80}算法與數據結構堆排序示例剩余元素組成的子序列為：R2={36，36，45，16，22剩余元素組成的子序列為：R3={9，36，16，36，22}，將該子序列重新調整為堆，如圖12.9(a)所示。交換堆頂的最大元素36與序列中最后一個元素9之后，如圖12.9(b)所示，有序段為：{36，45，66，80}算法與數據結構堆排序示例剩余元素組成的子序列為：R3={9，36，16，36，22}剩余元素組成的子序列為：R4={9，22，36，16}，將該子序列重新調整為堆，如圖12.10(a)所示。交換堆頂的最大元素36與序列中最后一個元素16之后，如圖12.10(b)所示，有序段為：{36，36，45，66，80}算法與數據結構堆排序示例剩余元素組成的子序列為：R4={9，22，36，16}，將該剩余元素組成的子序列為：R5={16，22，9}，將該子序列重新調整為堆，如圖12.11(a)所示。交換堆頂的最大元素22與序列中最后一個元素9之后，如圖12.11(b)所示，有序段為：{22，36，36，45，66，80}算法與數據結構堆排序示例剩余元素組成的子序列為：R5={16，22，9}，將該子序列剩余元素組成的子序列為：R6={9，16}，將該子序列重新調整為堆，如圖12.12(a)所示。交換堆頂的最大元素16與序列中最后一個元素9之后，如圖12.12(b)所示，有序段為：{9，16，22，36，36，45，66，80}，此時就得到了最終的有序序列算法與數據結構堆排序示例剩余元素組成的子序列為：R6={9，16}，將該子序列重新調堆排序的實現堆排序用的是最大堆為了和其他的排序函數保持一致，數據從位置0開始存儲。因此，對位置i中的結點，父結點在位置(i–1)/2，左孩子在位置2i+1，右孩子緊跟著左孩子向下過濾的函數siftDown，它有三個參數：第一個參數R[]是待排序的數組，第二個參數pos是向下過濾的起始位置，第三個參數size是目前堆的大小。

堆排序的實現堆排序用的是最大堆堆排序[代碼12.10]堆排序。參數為待排序序列S，以及序列大小size。template<classType>voidheapSort(TypeR[],intsize){ inti;//初始建堆，從最后一個非葉結點開始調堆

for(i=size/2-1;i>=0;i--) siftDown(R,i,size);//共n-1趟排序（刪除堆頂元素后反復調整堆）

for(i=size-1;i>0;i--){ swap(R[0],R[i]); //交換堆頂元素與子序列中最后一個元素siftDown(R,0,i); //將R[0..i]重新調整為大頂堆} }堆排序[代碼12.10]堆排序。參數為待排序序列S，以及序列向下調整堆siftdown[代碼12.9]向下調整成堆。參數為待排序序列R，要調整的結點編號pos以及序列大小size。template<classType>voidsiftDown(TypeR[],intpos,intsize){intchild;Typetmp=R[pos]; //暫存“根”記錄R[pos]for(;pos*2+1<size;pos=child){

child=pos*2+1;if(child!=size-1&&R[child+1]>R[child])child++; //選取兩個孩子的大者

if(R[child]>tmp)

//較大的孩子比雙親大

R[pos]=R[child]; elsebreak;}

R[pos]=tmp; //被調整結點放入正確位置}向下調整堆siftdown[代碼12.9]向下調整成堆。參數堆排序性能分析建堆：O(n)刪除堆頂:O(logi)一次建堆，n次刪除堆頂總時間代價為O(nlogn)空間代價為O(1)堆排序過程中存在大跨度的數據移動，是一種不穩(wěn)定的排序方法快速排序和堆排序經常用于在大量記錄中找出排在前面的若干最大（或最?。┯涗?。堆排序性能分析建堆：O(n)2022/11/2282自測題9.已知關鍵字序列5,8,12,19,28,20,15,22是小根堆（最小堆）,插入關鍵字3,調整后得到的小根堆是A.3,5,12,8,28,20,15,22,19B.3,5,12,19,20,15,22,8,28C.3,8,12,5,20,15,22,28,19D.3,12,5,8,28,20,15,22,19【2009年全國碩士研究生入學計算機學科專業(yè)基礎綜合試題】A2022/10/1182自測題9.已知關鍵字序列5,8,第12章排序12.1排序的基本概念12.2插入排序12.3交換排序12.4選擇排序12.4.1直接選擇排序12.4.2堆排序*12.4.3錦標賽排序12.5歸并排序*12.6基數排序12.7

各種內部排序方法的比較*12.8外部排序第12章排序12.1排序的基本概念錦標賽排序

錦標賽排序

關鍵字序列R={36，80，45，66，22，9，36，16}。錦標賽排序的示例如圖12.13(a)、12.14(a)所示：第一趟選出的最小關鍵字為9；第二趟選出的最小關鍵字為16，是從與上一趟的冠軍9比較失敗的記錄中找出的。算法與數據結構錦標賽排序關鍵字序列R={36，80，45，66，22，9，36，16圖12.13(a)中最下層的8個葉結點（外部結點）用于存儲初始序列，前三層的7個非終端結點（內部結點）用于表示其左右孩子中的“勝者”，因此這種用于排序的完全二叉樹稱為勝者樹（WinnerTree）。實際應用中，為節(jié)約存儲空間，非終端結點僅存儲其孩子中勝者的編號，如圖12.13(b)所示。算法與數據結構錦標賽排序圖12.13(a)中最下層的8個葉結點（外部結點）用于存儲初

算法與數據結構錦標賽排序性能分析

算法與數據結構錦標賽排序性能分析第12章排序12.1排序的基本概念12.2插入排序12.3交換排序12.4選擇排序12.5歸并排序*12.6基數排序12.7

各種內部排序方法的比較*12.8外部排序第12章排序12.1排序的基本概念歸并排序歸并排序（MergingSort）是利用“歸并”技術來進行的排序。所謂歸并是指將兩個或兩個以上的有序表合并成一個新的有序表。在內部排序中，通常采用的是2-路歸并排序。2-路歸并排序的基本思想是：將一個具有n個待排序記錄的序列看成是n個長度為1的有序序列，然后對相鄰的子序列進行兩兩歸并，得到n/2個長度為2的有序子序列，繼續(xù)對相鄰子序列進行兩兩歸并，得到n/4個長度為4的有序序列，重復歸并過程，直至得到一個長度為n的有序序列為止。算法與數據結構歸并排序歸并排序（MergingSort）是利用“歸并”技歸并排序示例1算法與數據結構歸并排序示例1算法與數據結構101745532233345676ApBpCp10174553223334567610ApBpCp1017455322333456761017ApBpCp歸并排序示例2101745532233345676ApBpCp101745101745532233345676101722ApBpCp10174553223334567610172233ApBpCp1017455322333456761017223334ApBpCp歸并排序示例2101745532233345676101722ApBpCp10174553223334567610172233344553ApBpCp101745532233345676101722333445535676ApBpCp101745532233345676101722333445ApBpCp歸并排序示例2101745532233345676101722333445歸并兩個有序序列[代碼12.11]歸并相鄰的兩個有序子序列。將有序序列R[low..mid-1]和R[mid..high]歸并為有序序列R[low..high]。template<classType>voidmerge(TypeR[],Typetmp[],intlow,intmid,inthigh){ inti=low,j=mid,k=0;while(i<mid&&j<=high)//R中記錄由小到大地并入tmpif(R[i]<R[j])

tmp[k++]=R[i++];//將R[i]和R[j]的小者拷貝到tmp[k]elsetmp[k++]=R[j++];while(i<mid)

//前端剩余R[i..mid-1]復制到tmp

tmp[k++]=R[i++];

while(j<=high)

//后端剩余R[j..high]復制到tmp

tmp[k++]=R[j++];for(i=0,k=low;k<=high;)

R[k++]=tmp[i++]; //排好序的記錄由tmp拷回R}歸并兩個有序序列[代碼12.11]歸并相鄰的兩個有序子序列歸并排序如果N=1，已排序否則，對前一半和后一半分別調用歸并排序歸并兩個已排序的數組歸并排序如果N=1，已排序歸并排序的實現歸并排序采用分治法，用遞歸實現。遞歸參數是排序的區(qū)間[代碼12.12]遞歸2-路歸并排序。通過遞歸調用實現對子序列R[low..high]的排序過程，將其歸并為有序段。template<classType>voidmergeSort(TypeR[],Typetmp[],intlow,inthigh){if(low==high)return;intmid=(low+high)/2; //從中間劃分為兩個子序列mergeSort(R,tmp,low,mid);//遞歸歸并子序列R[low..mid]

mergeSort(R,tmp,mid+1,high);//遞歸歸并子序列R[mid+1..high]

merge(R,tmp,low,mid+1,high); //歸并兩個子序列}歸并排序的實現歸并排序采用分治法，用遞歸實現。[代碼12.13]2-路歸并排序的接口函數。參數為待排序序列R，以及序列大小size。template<classType>voidmergeSort(TypeR[],intsize){Type*tmp=newType[size]; //輔助數組mergeSort(R,tmp,0,size-1);delete[]tmp;}歸并排序的接口函數[代碼12.13]2-路歸并排序的接口函數。參數為待排序序列歸并排序性能分析設N是2的冪，則

T(1)=1T(N)=2T(N/2)+N

兩邊除N，得歸并排序性能分析設N是2的冪，則把所有的式子相加，得：則：T(N)=NlogN+N=O(NlogN)所以，歸并排序的時間復雜度O(NlogN)?？臻g代價：O(n)不依賴于原始數組的輸入情況，最大、最小以及平均時間代價均為Θ(nlogn)

歸并排序性能分析把所有的式子相加，得：歸并排序性能分析2022/11/22100自測題：歸并排序二趟歸并排序后：[33516296]

[1728

87]

初始關鍵字序列：[51]

[33]

[62]

[96]

[87]

[17]

[28]

一趟歸并排序后：[3351]

[6296]

[1787]

[28]

三趟歸并排序后：[17

28335162

8796]2022/10/11100自測題：歸并排序二趟歸并排序后：對一組記錄（54，38，96，23，15，72，60，45，83）分別進行直接插入排序，希爾排序，冒泡排序，快速排序，直接選擇排序，堆排序，二路歸并排序，請寫出一趟排序后的結果自測題對一組記錄（54，38，96，23，15，72，60，45，第12章排序12.1排序的基本概念12.2插入排序12.3交換排序12.4選擇排序12.5歸并排序*12.6基數排序12.7

各種內部排序方法的比較*12.8外部排序第12章排序12.1排序的基本概念基數排序前面討論的排序算法都是基于關鍵字之間的比較和記錄的移動這兩種操作實現的，而基數排序則不然，它是利用關鍵字的結構，通過“分配”和“收集”的方法實現排序。基數排序（RadixSort）是一種借助“多關鍵字排序”的思想來實現“單關鍵字排序”的算法。假設待排序序列的每個記錄含有d個關鍵字，從高到低排列為：(K0，K1，…，Kd-1)，其中K0被稱為“最主”位關鍵字，Kd-1被稱為“最次”位關鍵字。實現多關鍵字排序通常有兩種方法：算法與數據結構基數排序前面討論的排序算法都是基于關鍵字之間的比較和記錄的移最高位優(yōu)先（MSD）法：先對K0進行排序，并按K0的不同值將記錄序列分成若干子序列之后，分別對K1進行排序，…，依次類推，直至最后對最次位關鍵字排序完成為止。最低位優(yōu)先（LSD）法：先對Kd-1進行排序，然后對Kd-2進行排序，依次類推，直至對最主位關鍵字K0排序完成為止。最低位優(yōu)先（LSD）法排序過程中不需要根據“前一個”關鍵字的排序結果，將記錄序列分割成若干個(“前一個”關鍵字不同的)子序列。算法與數據結構基數排序最高位優(yōu)先（MSD）法：先對K0進行排序，并按K0的不同值將基數排序示例例如：對關鍵字序列R={332，380，166，145，22，9，117，236，81，230}進行基數排序。將關鍵字分解為三部分，即個位數、十位數和百位數，關鍵字的各部分取值都在0到9之間，設0到9十個“桶”（或稱分組），首先將關鍵字按個位的值依次“分配”到各桶中。算法與數據結構第一趟排序按個位數“分配”基數排序示例例如：對關鍵字序列R={332，380，166，按從0至9的分組順序將第一次“分配”的關鍵字“收集”在一起；得到新的序列：{380，230，81，332，22，145，166，236，117，9}，顯然此時各整數已按個位數排成非遞減序。然后將第一次“收集”到的新序列按關鍵字的十位的值依次“分配”到各桶中算法與數據結構基數排序示例第二趟排序按十位數“分配”按從0至9的分組順序將第一次“分配”的關鍵字“收集”在一起；按從0至9的分組順序將第二次“分配”的關鍵字“收集”在一起；得到新的序列：{9，117，22，230，332，236，145，166，380，81}，顯然此時各整數已按十位數排成非遞減序。然后再將第二次“收集”到的新序列按關鍵字的百位的值依次“分配”到各桶中按從0至9的分組順序將第三次“分配”的關鍵字“收集”在一起，就得到有序序列：{9，22，81，117，145，166，230，236，332，380}。算法與數據結構基數排序示例第三趟排序按百位數“分配”按從0至9的分組順序將第二次“分配”的關鍵字“收集”在一起；上述排序方法相當于將一個關鍵字分解成多個“關鍵字”，然后按最低位優(yōu)先的原則采用“分配-收集”的方法進行排序?？梢钥闯?，基數排序只有當排序結束時才能確定記錄的最終位置。算法與數據結構基數排序示例上述排序方法相當于將一個關鍵字分解成多個“關鍵字”，然后按最最低位優(yōu)先基數排序最低位優(yōu)先基數排序的過程可描述如下：(1)按每個關鍵字當前位的取值統(tǒng)計各分組（桶）的容量，并依此計算各組最后一個元素的存儲位置；(2)分配時，逆序掃描記錄序列，按關鍵字當前位的取值，將記錄分配到不同的組中；(3)收集時，按分組順序將各組內容收集在一起；(4)重復上述步驟，直到處理完所有關鍵字位。為實現基數排序，我們設置一個輔助數組bucket充當“桶”，用于存儲每趟排序中各分組的記錄。那么應該如何求出記錄在“桶”中的正確位置呢？用整型數組position充當計數器，通過計算每個“桶”的容量從而確定“桶”內最后一個記錄的位置。算法與數據結構最低位優(yōu)先基數排序最低位優(yōu)先基數排序的過程可描述如下：算法與基數排序[代碼12.16]基數排序。參數為待排序序列R，以及序列大小size。template<classType>voidradixSort(TypeR[],intsize){ inti,d=1,max=R[0];for(i=1;i<size;i++)if(R[i]>max)max=R[i]; //求最大關鍵字

while(max=max/10)d++;//求關鍵字的最大寬度dfor(i=1;i<=d;i++) //從低位開始，共進行d趟基數排序LSD(R,size,i); }算法與數據結構基數排序[代碼12.16]基數排序。參數為待排序序列R，以及一趟LSD基數排序[代碼12.15]按關鍵字的第i位進行一趟基數排序。參數為待排序序列R，序列大小size以及當前位i。constintradix=10; //基數為10template<classType>voidLSD(TypeR[],intsize,inti){Type*bucket=newType[size];int*position=newint[radix]; //計數器

intj,k;for(j=0;j<radix;j++) //計數器清0position[j]=0; for(j=0;j<size;j++){k=getDigit(R[j],i); //計算每個桶的容量position[k]++;;}算法與數據結構一趟LSD基數排序[代碼12.15]按關鍵字的第i位進行一趟

//按每個桶的容量，分配bucket數組的位置

for(j=1;j<radix;j++) position[j]=position[j-1]+position[j];for(j=size-1;j>=0;j--){ //逆序一趟分配k=getDigit(R[j],i); //按關鍵字第i位的數值存入bucket中

bucket[--position[k]]=R[j];}for(j=0;j<size;j++) //順序一趟收集R[j]=bucket[j];

//將桶中記錄收集到數組Rdelete[]bucket;delete[]position;}算法與數據結構一趟基數排序//按每個桶的容量，分配bucket數組的位置取關鍵字key的第i位[代碼12.14]取關鍵字key的第i位。參數為關鍵字key以及當前位i。intgetDigit(intkey,inti){for(intj=1;j<i;j++)key=key/10;key=key%10;returnkey;}算法與數據結構取關鍵字key的第i位[代碼12.14]取關鍵字key的第i基數排序性能分析每趟排序的時間分三部分：計算每個桶內記錄數量及位置的時間是O（radix）；分配時將n個記錄裝入桶中的時間是O（n）；收集記錄的時間也是O（n）。因此，一趟排序的時間是O（radix+n），算法總時間復雜度為O(d*(radix+n))?；鶖蹬判虍攏較小d較大時并不合適，只有當n較大、d較小時，基數排序最為有效。該算法使用了兩個輔助數組，故空間復雜度為O（radix+n）基數排序是一種穩(wěn)定的排序方法。算法與數據結構基數排序性能分析每趟排序的時間分三部分：算法與數據結構對給定的關鍵字序列110，119，007，911，114，120，122進行基數排序，則第2趟分配收集后得到的關鍵字序列是（

）。A．007，110，119，114，911，120，122B．007，110，119，114，911，122，120C．007，110，911，114，119，120，122D．110，120，911，122，114，007，119【2013年全國碩士研究生入學統(tǒng)一考試計算機學科專業(yè)基礎綜合】【參考答案】C【題目解析】基于LSD的基數排序的第1趟是按照個位數分配的，第2趟是按照十位數分配的。算法與數據結構自測題

對給定的關鍵字序列110，119，007，911，114，1自測題自測題11．下列排序算法中元素的移動次數和關鍵字的初始排列次序無關的是（

）。A．直接插入排序

B．起泡排序

C．基數排序

D．快速排序【2015年全國碩士研究生入學統(tǒng)一考試計算機學科專業(yè)基礎綜合】【參考答案】C【題目解析】基數排序采用“分配-收集”的方法，其好處是不需要進行關鍵字間的比較。ABD選項，其基本操作都是關鍵字的比較和元素的移動，元素的移動次數最少的情況是初始序列剛好是正序的。算法與數據結構自測題自測題11．下列排序算法中元素的移動次數和關鍵字的初始第12章排序12.1排序的基本概念12.2插入排序12.3交換排序12.4選擇排序12.5歸并排序*12.6基數排序12.7

各種內部排序方法的比較*12.8外部排序第12章排序12.1排序的基本概念排序方法平均時間最壞情況輔助空間穩(wěn)定性直接插入排序O（n2）O（n2）O（1）穩(wěn)定冒泡排序O（n2）O（n2）O（1）穩(wěn)定直接選擇排序O（n2）O（n2）O（1）不穩(wěn)定希爾排序O（n1.3）O（n1.3）O（1）不穩(wěn)定快速排序O（nlog2n）O（n2）O（log2n）不穩(wěn)定堆排序O（nlog2n）O（nlog2n）O（1）不穩(wěn)定2-路歸并排序O（nlog2n）O（nlog2n）O（n）穩(wěn)定基數排序(課本無)O(d*(rd+n))O(d*(rd+n))