排序教學(xué)講解課件

算法與數(shù)據(jù)結(jié)構(gòu)

教師：算法與數(shù)據(jù)結(jié)構(gòu)

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

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

341234’0896081234

34’96

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

341234’0896081234’

3496

不穩(wěn)定！排序的基本概念穩(wěn)定性不穩(wěn)定！排序的基本概念排序算法的衡量標(biāo)準(zhǔn)時(shí)間代價(jià)

記錄的比較和移動(dòng)次數(shù)空間代價(jià)算法本身的繁雜程度排序算法的衡量標(biāo)準(zhǔn)時(shí)間代價(jià)第12章排序12.1排序的基本概念12.2插入排序12.2.1直接插入排序12.2.2折半插入排序12.2.3希爾排序12.3交換排序12.4選擇排序12.5歸并排序*12.6基數(shù)排序12.7

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

直接插入排序直接插入排序（StraightInsertio直接插入排序算法與數(shù)據(jù)結(jié)構(gòu)直接插入排序算法與數(shù)據(jù)結(jié)構(gòu)直接插入排序1234’322964453478

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

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

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

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

比較次數(shù)為移動(dòng)次數(shù)為平均情況：O(n2)

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

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

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

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

low=0;high=pos-1;//設(shè)置折半查找的范圍while(low<=high){ //折半查找插入位置mid=(low+high)/2; //計(jì)算中間位置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折半插入排序比直接插入排序明顯地減少了關(guān)鍵字間的“比較”次數(shù)，但記錄“移動(dòng)”的次數(shù)不變，故其時(shí)間復(fù)雜度仍為O（n2）。算法與數(shù)據(jù)結(jié)構(gòu)算法分析折半插入排序比直接插入排序明顯地減少了關(guān)鍵字間的“比較”次數(shù)自測(cè)題1．對(duì)同一待排序列分別進(jìn)行折半插入排序和直接插入排序，兩者之間可能的不同之處是（

）。A．排序的總趟數(shù)

B．元素的移動(dòng)次數(shù)C．使用輔助空間的數(shù)量

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

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

算法與數(shù)據(jù)結(jié)構(gòu)Gap的選取

算法與數(shù)據(jù)結(jié)構(gòu)希爾排序算法與數(shù)據(jù)結(jié)構(gòu)希爾排序算法與數(shù)據(jù)結(jié)構(gòu)希爾排序的實(shí)現(xiàn)若以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; //將待插入記錄放到合適位置}}}希爾排序的實(shí)現(xiàn)若以Shell提出的分組方法，則Shell排性能分析不同的增量序列有不同的時(shí)間性能。希爾排序適用于待排序的記錄數(shù)目較大的情況。希爾排序存在大跨度的元素移動(dòng)，是一種不穩(wěn)定的排序方法。希爾排序的時(shí)間性能與其選定的增量序列有關(guān)，有人在大量實(shí)驗(yàn)的基礎(chǔ)上推導(dǎo)出，希爾排序的時(shí)間復(fù)雜度約為O（n1.3）?？臻g復(fù)雜度為O(1)。性能分析不同的增量序列有不同的時(shí)間性能。自測(cè)題2．用希爾排序方法對(duì)一個(gè)數(shù)據(jù)序列進(jìn)行排序時(shí)，若第1趟排序結(jié)果為9，1，4，13，7，8，20，23，15，則該趟排序采用的增量（間隔）可能是（

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

）。A．直接插入排序

B．折半插入排序

C．快速排序

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

33285152629687三趟排序結(jié)果：1017283351／

5152628796

初始關(guān)鍵字序列：5133629687172851／

5210

一趟排序結(jié)果：172851／

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

各種內(nèi)部排序方法的比較*12.8外部排序第12章排序12.1排序的基本概念冒泡排序冒泡排序(BubbleSort，也稱為起泡排序)是一種比較簡(jiǎn)單的交換排序方法。它的基本思想是對(duì)所有相鄰記錄的關(guān)鍵字值進(jìn)行比較，如果不滿足排序要求（即逆序），則將其交換，最終直到所有記錄排好序?yàn)橹?。冒泡排序冒泡排?BubbleSort，也稱為起泡排序)冒泡排序?qū)τ谟蒼個(gè)記錄序列的非遞減序冒泡排序的步驟如下：(1)將整個(gè)待排序的記錄序列劃分成有序區(qū)和無(wú)序區(qū)，初始狀態(tài)有序區(qū)為空，無(wú)序區(qū)包括所有待排序的記錄；(2)每一趟冒泡排序，對(duì)無(wú)序區(qū)從頭到尾比較相鄰記錄的關(guān)鍵字，若逆序，則交換。一趟排序后無(wú)序區(qū)中關(guān)鍵字值最大的記錄進(jìn)入到有序區(qū)；(3)重復(fù)執(zhí)行步驟(2)，若在某一趟排序中沒有發(fā)生交換操作，說(shuō)明待排序記錄已全部有序，排序提前結(jié)束。否則，最多需要經(jīng)過n－1趟冒泡排序，才能將這n個(gè)記錄重新按關(guān)鍵字排好序。算法與數(shù)據(jù)結(jié)構(gòu)冒泡排序?qū)τ谟蒼個(gè)記錄序列的非遞減序冒泡排序的步驟如下：算法算法與數(shù)據(jù)結(jié)構(gòu)冒泡排序算法與數(shù)據(jù)結(jié)構(gòu)冒泡排序冒泡排序的實(shí)現(xià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]); //調(diào)用STL中的swap進(jìn)行交換flag=true;}}}冒泡排序的實(shí)現(xiàn)冒泡排序算法如下。性能分析穩(wěn)定空間代價(jià)：O(1)時(shí)間代價(jià)分析：比較次數(shù)：最少：O(n)最多：交換次數(shù)最多為O(n2)，最少為0，平均為O(n2)。時(shí)間代價(jià)結(jié)論最大，平均時(shí)間代價(jià)均為O(n2)。最小時(shí)間代價(jià)為O(n)：最佳情況下只運(yùn)行第一輪循環(huán)性能分析穩(wěn)定第12章排序12.1排序的基本概念12.2插入排序12.3交換排序12.3.1冒泡排序12.3.2快速排序12.4選擇排序12.5歸并排序*12.6基數(shù)排序12.7

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

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

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

//該記錄移動(dòng)到大下標(biāo)端}S[low]=tmp; //把軸值回填到分界位置上returnlow; //返回樞軸位置}一次劃分[代碼12.5]一趟快速排序（或一次劃分）。參數(shù)為待排序序列快速排序的接口函數(shù)快速排序的函數(shù)原型和其它的排序算法的函數(shù)原型都不同，它包含了兩個(gè)用于控制遞歸終止的參數(shù)。為了和其它的排序算法一致起來(lái)，我們?cè)谒饷嬖偌右粋€(gè)接口函數(shù)，該函數(shù)調(diào)用了遞歸的quickSort函數(shù)。

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

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

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

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

）。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年全國(guó)碩士研究生入學(xué)統(tǒng)一考試計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合】【參考答案】C【題目解析】每趟快速排序后，至少一個(gè)記錄找到最終位置。自測(cè)題

下列選項(xiàng)中，不可能是快速排序第2趟排序結(jié)果的是（）。自2022/11/2254一組記錄的關(guān)鍵字為{46、79、56、38、40、84},則利用快速排序的方法,以第一個(gè)記錄為樞軸得到的一次劃分結(jié)果是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【北京交通大學(xué)2005一.8(2分)】C（要注意交換位置）自測(cè)題

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

例如：給定無(wú)序關(guān)鍵字{7,5,1,6,2,8,9,3},當(dāng)j=4時(shí),找到的關(guān)鍵字應(yīng)是5。

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

【武漢理工大學(xué)2002四.3(35/3分)】算法舉例2022/10/1155對(duì)給定關(guān)鍵字序號(hào)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ù)進(jìn)行劃分

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

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

(n-1)+(n-2)+……+2+1=n(n-1)/2即O(n2)直接選擇排序直接選擇排序(StraightSelectio直接選擇排序示例1234’322964453478直接選擇排序示例1234’3229644534782022/11/22直接選擇排序示例初始關(guān)鍵字序列：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直接選擇排序示例初始關(guān)鍵字序列：5[代碼12.8]template<classType>voidstraightSelectSort(TypeR[],intsize){ intpos,min,j;//min為一趟排序中最小記錄下標(biāo)//pos為待存放當(dāng)前最小記錄的位置for(pos=0;pos<size-1;pos++){ min=pos;for(j=pos+1;j<size;++j)if(R[j]<R[min])min=j;//查找最小記錄//調(diào)用STL中的swap，頭文件algorithm

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

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

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

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

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

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

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

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

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

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

for(i=size-1;i>0;i--){ swap(R[0],R[i]); //交換堆頂元素與子序列中最后一個(gè)元素siftDown(R,0,i); //將R[0..i]重新調(diào)整為大頂堆} }堆排序[代碼12.10]堆排序。參數(shù)為待排序序列S，以及序列向下調(diào)整堆siftdown[代碼12.9]向下調(diào)整成堆。參數(shù)為待排序序列R，要調(diào)整的結(jié)點(diǎn)編號(hào)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++; //選取兩個(gè)孩子的大者

if(R[child]>tmp)

//較大的孩子比雙親大

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

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

各種內(nèi)部排序方法的比較*12.8外部排序第12章排序12.1排序的基本概念錦標(biāo)賽排序

錦標(biāo)賽排序

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

算法與數(shù)據(jù)結(jié)構(gòu)錦標(biāo)賽排序性能分析

算法與數(shù)據(jù)結(jié)構(gòu)錦標(biāo)賽排序性能分析第12章排序12.1排序的基本概念12.2插入排序12.3交換排序12.4選擇排序12.5歸并排序*12.6基數(shù)排序12.7

各種內(nèi)部排序方法的比較*12.8外部排序第12章排序12.1排序的基本概念歸并排序歸并排序（MergingSort）是利用“歸并”技術(shù)來(lái)進(jìn)行的排序。所謂歸并是指將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表。在內(nèi)部排序中，通常采用的是2-路歸并排序。2-路歸并排序的基本思想是：將一個(gè)具有n個(gè)待排序記錄的序列看成是n個(gè)長(zhǎng)度為1的有序序列，然后對(duì)相鄰的子序列進(jìn)行兩兩歸并，得到n/2個(gè)長(zhǎng)度為2的有序子序列，繼續(xù)對(duì)相鄰子序列進(jìn)行兩兩歸并，得到n/4個(gè)長(zhǎng)度為4的有序序列，重復(fù)歸并過程，直至得到一個(gè)長(zhǎng)度為n的有序序列為止。算法與數(shù)據(jù)結(jié)構(gòu)歸并排序歸并排序（MergingSort）是利用“歸并”技?xì)w并排序示例1算法與數(shù)據(jù)結(jié)構(gòu)歸并排序示例1算法與數(shù)據(jù)結(jié)構(gòu)101745532233345676ApBpCp10174553223334567610ApBpCp1017455322333456761017ApBpCp歸并排序示例2101745532233345676ApBpCp101745101745532233345676101722ApBpCp10174553223334567610172233ApBpCp1017455322333456761017223334ApBpCp歸并排序示例2101745532233345676101722ApBpCp10174553223334567610172233344553ApBpCp101745532233345676101722333445535676ApBpCp101745532233345676101722333445ApBpCp歸并排序示例2101745532233345676101722333445歸并兩個(gè)有序序列[代碼12.11]歸并相鄰的兩個(gè)有序子序列。將有序序列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]復(fù)制到tmp

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

while(j<=high)

//后端剩余R[j..high]復(fù)制到tmp

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

R[k++]=tmp[i++]; //排好序的記錄由tmp拷回R}歸并兩個(gè)有序序列[代碼12.11]歸并相鄰的兩個(gè)有序子序列歸并排序如果N=1，已排序否則，對(duì)前一半和后一半分別調(diào)用歸并排序歸并兩個(gè)已排序的數(shù)組歸并排序如果N=1，已排序歸并排序的實(shí)現(xiàn)歸并排序采用分治法，用遞歸實(shí)現(xiàn)。遞歸參數(shù)是排序的區(qū)間[代碼12.12]遞歸2-路歸并排序。通過遞歸調(diào)用實(shí)現(xiàn)對(duì)子序列R[low..high]的排序過程，將其歸并為有序段。template<classType>voidmergeSort(TypeR[],Typetmp[],intlow,inthigh){if(low==high)return;intmid=(low+high)/2; //從中間劃分為兩個(gè)子序列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); //歸并兩個(gè)子序列}歸并排序的實(shí)現(xiàn)歸并排序采用分治法，用遞歸實(shí)現(xiàn)。[代碼12.13]2-路歸并排序的接口函數(shù)。參數(shù)為待排序序列R，以及序列大小size。template<classType>voidmergeSort(TypeR[],intsize){Type*tmp=newType[size]; //輔助數(shù)組mergeSort(R,tmp,0,size-1);delete[]tmp;}歸并排序的接口函數(shù)[代碼12.13]2-路歸并排序的接口函數(shù)。參數(shù)為待排序序列歸并排序性能分析設(shè)N是2的冪，則

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

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

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

[1728

87]

初始關(guān)鍵字序列：[51]

[33]

[62]

[96]

[87]

[17]

[28]

一趟歸并排序后：[3351]

[6296]

[1787]

[28]

三趟歸并排序后：[17

28335162

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

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

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

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

//按每個(gè)桶的容量，分配bucket數(shù)組的位置

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); //按關(guān)鍵字第i位的數(shù)值存入bucket中

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

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

）。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年全國(guó)碩士研究生入學(xué)統(tǒng)一考試計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合】【參考答案】C【題目解析】基于LSD的基數(shù)排序的第1趟是按照個(gè)位數(shù)分配的，第2趟是按照十位數(shù)分配的。算法與數(shù)據(jù)結(jié)構(gòu)自測(cè)題

對(duì)給定的關(guān)鍵字序列110，119，007，911，114，1自測(cè)題自測(cè)題11．下列排序算法中元素的移動(dòng)次數(shù)和關(guān)鍵字的初始排列次序無(wú)關(guān)的是（

）。A．直接插入排序

B．起泡排序

C．基數(shù)排序

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

各種內(nèi)部排序方法的比較*12.8外部排序第12章排序12.1排序的基本概念排序方法平均時(shí)間最壞情況輔助空間穩(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)定基數(shù)排序(課本無(wú))O(d*(rd+n))O(d*(rd+n))