《第9章內(nèi)部排序》習(xí)題解答

1、第9章 內(nèi)部排序第9章內(nèi)部排序本章學(xué)習(xí)要點熟悉并掌握本章中各種內(nèi)部排序方法的基本思想及其實現(xiàn)過程掌握各種內(nèi)部排序算法的時間復(fù)雜度和空間復(fù)雜度的計算和分析方法了解各種內(nèi)部排序方法的優(yōu)缺點以及其不同的應(yīng)用場合要求能夠針對實際問題的特點選擇合理的排序算法并通過編程實現(xiàn)排序（Sorting）是計算機程序設(shè)計中的一種重要運算，它的功能是將一組數(shù)據(jù)元素按照其關(guān)鍵字的某種規(guī)定順序（遞增或遞減）進(jìn)行排列。對數(shù)據(jù)元素進(jìn)行排序的目的是為了便于查找，在關(guān)鍵字有序的一組數(shù)據(jù)中的查找要比無序時更容易，速度也更快。本章主要介紹幾種常用的內(nèi)部排序方法，主要有：插入排序、交換排序、選擇排序、歸并排序和基數(shù)排序。最后對各種排序

2、算法的時間復(fù)雜度和空間復(fù)雜度進(jìn)行了分析和比較，并且討論了如何針對實際問題合理選擇排序算法等內(nèi)容。9.1排序的有關(guān)概念和數(shù)組的輸入與輸出9.1.1排序的概念1排序?qū)⒁粋€數(shù)據(jù)元素的任意序列，重新排列成一個按關(guān)鍵字有序（遞增有序或遞減有序）的序列的過程叫排序。2排序方法的穩(wěn)定性若在排序過程中，序列的兩個關(guān)鍵字值相同的記錄的相對位置不發(fā)生改變，則稱所用的排序方法為穩(wěn)定的；反之，若在某個序列的排序過程中關(guān)鍵字值相同的記錄的相對位置發(fā)生了改變，則稱所用的排序方法是不穩(wěn)定的。3內(nèi)部排序和外部排序在排序過程中，如果待排序列全部讀入計算機存儲器中，則稱此為內(nèi)部排序；反之，若待排序列僅有部分記錄在內(nèi)存中，在排序過

3、程中還要對外存中的紀(jì)錄進(jìn)行訪問，這樣的排序過程叫外部排序。4排序方法的性能分析對于所選用的排序方法的好壞主要是基于其算法的時間復(fù)雜度和空間復(fù)雜度兩方面進(jìn)行分析。5數(shù)據(jù)元素類型說明數(shù)據(jù)元素可以是任意一個結(jié)構(gòu)類型，排序過程是按元素中的某個關(guān)鍵字（數(shù)據(jù)項）進(jìn)行排序。不失一般性，我們在本章的所有例題中總是假定待排序列中的數(shù)據(jù)元素中只含有關(guān)鍵字項，且其數(shù)據(jù)類型為整型。9.1.2一維數(shù)組的輸入與輸出1數(shù)組輸入操作函數(shù)void Input(int *A,int n)的功能是，從鍵盤輸入n個整數(shù)到數(shù)組A中。#includeiostream.hvoid Input(int *A,int n)int i;cout

4、請輸入n個整數(shù):n;for(i=0;iAi;2數(shù)組輸出操作函數(shù)void Output(int A,int n)的功能是，依次顯示輸出數(shù)組A中的n個整數(shù)。void Output(int A,int n)int i;cout結(jié)果為:n;for(i=0;in;i+)coutAi ;coutendl;3數(shù)組排序操作函數(shù)void MainSort(void(*sort)(int*,int)的功能是，首先通過函數(shù)調(diào)用Input(A,n)輸入n個整數(shù)到數(shù)組A中，再通過函數(shù)調(diào)用sort(A,n)對A中的n個整數(shù)排序，最后通過函數(shù)調(diào)用Out(A,n)顯示輸出數(shù)組A中的n個整數(shù)。void MainSort(voi

5、d(*sort)(int*,int)int *A,n;coutn;A=new intn;Input(A,n);cout原順序;Output(A,n);sort(A,n); /調(diào)用sort對數(shù)組A進(jìn)行處理cout排序后的順序;Out(A,n);deleteA;9.2插入排序法9.2.1直接插入排序(Straight Insertion Sort)1算法思想對于任意排列的序列(a0,a1,a2,an-1)，先將第一個記錄看成是一個有序序列L1=(a0)，再將第2個記錄插入到L1中得到有序序列L2=(a0,a1)一般的，將第k+1個記錄插入到有序序列Lk中得到有序序列Lk+1，如此重復(fù)插入n-1次即

6、可得到有序序列Ln=(a0,a1,a2,an-1)。2舉例說明設(shè)原始序列為：8、3、5、2、9、7、*5、4-.294.-第1輪：(8) 3,5,2,9,7,*5,4第2輪：(3,8) 5,2,9,7,*5,4第3輪：(3,5,8) 2,9,7,*5,4第4輪：(2,3,5,8) 9,7,*5,4第5輪：(2,3,5,8,9) 7,*5,4第6輪：(2,3,5,7,8,9) *5,4第7輪：(2,3,5,*5,7,8,9) 4第8輪：(2,3,4,5,*5,7,8,9) 3算法實現(xiàn)void InsertSort(int A,int n)int temp,i,j;for(i=0;i0;j-)if

7、(temp=Aj-1)break;Aj=Aj-1;Aj=temp; /將temp插入到相應(yīng)的位置4算法分析從排序過程可知該算法是穩(wěn)定的；算法的比較次數(shù)為f(n)=1+2+3+n-1，所以該算法的時間復(fù)雜度為T(n)=O(n2)；由于在排序過程中僅有一個輔助變量（temp），所以該算法的空間復(fù)雜度為S(n)=O(1)。說明：（1）從算法的基本操作部分可以看出，當(dāng)待排序數(shù)組An基本有序時可以大大減少其比較的執(zhí)行次數(shù)，所以該算法適用于序列為基本有序的場合。（2）使用直接插入排序算法排序時可能出現(xiàn)下列情況：在最后一趟開始之前，所有的元素都不在其最終的位置上。比如，初始序列的最后一個元素為最小元素時就會

8、出現(xiàn)以上情況。*9.2.2折半插入排序折半插入排序是直接插入排序的一個改進(jìn)算法，該算法在排序過程中，通過折半查找法來實現(xiàn)尋找插入位置的操作，從而減少了數(shù)據(jù)元素中關(guān)鍵字的比較次數(shù)。1折半插入排序函數(shù)void InertSort1(int a,int n)int i,j,k,t,l,h;for(i=1;in;i+)if(aiai-1)l=0;h=i-1;while(l=h) /用二分法查找插入位置t=(l+h)/2;if(at=ai)break;else if(atai)l=t+1;else h=t-1;if(ht;j-)aj=aj-1;aj=k;2分步實現(xiàn)折半查找插入排序(1) 函數(shù)int Fo

9、und(int A,int n,int x)通過折半查找法求元素x在數(shù)組An中的插入下標(biāo)。int Found(int A,int n,int x)int t,l,h;l=0;h=n-1;if(x=Ah)t=n;else if(x=A0)t=0;elsewhile(l=h)t=(l+h)/2;if(At=x)break;else if(Atx)l=t+1;else h=t-1;if(hl)t=l;return t;(2) 調(diào)用函數(shù)Found()實現(xiàn)插入排序。void InertSort2(int a,int n)int i,j,x,t;for(i=1;it;j-)aj=aj-1;at=x;9.2

10、.3 希爾排序法(Shell Sort)1算法思想先將整個待排的n個記錄序列按照某個間隔值d1（通常取n/2）分割成為若干個子序列，再對其分別進(jìn)行直接插入排序，下一步取間隔值d2d1（通常取di+1=di/2）重復(fù)前面的過程直到間隔值為1時對整體序列進(jìn)行最后一次直接插入排序。2舉例說明設(shè)原始序列為：7、5、9、13、10、2、3、*5、8、1，其長度為n=10。第1輪：取間隔值d=10/2=5，先將序列看成如圖9.1(a)所示的5個子序列：(7,2)(5,3)(9,*5)(13,8)(10,1)。再分別對每個子序列進(jìn)行插入排序，其結(jié)果為如圖9.1(b)所示的子序列：(2,7)(3,5)(*5,

11、9)(8,13)(1,10)。第1輪排序結(jié)果為：2,3,*5,8,1,7,5,9,13,10（注意：在對各子序列排序時，子序列在主序列中的相對位置不變）。第2輪：取間隔值d=5/2=2，先將序列分成如圖9.2(a)所示的2個子序列：(2,*5,1,5,13)(3,8,7,9,10)。再分別進(jìn)行插入排序，其結(jié)果為如圖9.2(b)所示的子序列：(1,2,*5,5,13)(3,7,8,9,10)。第2輪排序結(jié)果為：1,3,2,7,*5,8,5,9,13,10。第3輪：取d=2/2=1，此時將整體序列進(jìn)行一次直接插入排序。第3輪排序結(jié)果為：1，2，3，*5，5，7，8，9，10，13。3算法實現(xiàn)(1)

12、 算法Insert(A,k,n)的功能是，對數(shù)組An按間隔k進(jìn)行分組插入排序void Insert(int A,int k,int n)int i,j,temp;for(i=k-1;i=0;j-=k) /在相應(yīng)的子序列中尋找插入位置。if(temp=Aj-k)break;Aj=Aj-k; Aj=temp; /將temp插入到相應(yīng)的位置(2) 希爾排序函數(shù)void ShellSort(int A,int n)int k=n;while(k=k/2)Insert(A,k,n);4算法分析該算法是不穩(wěn)定的；希爾排序算法的時間復(fù)雜度與間隔值d的取法有關(guān)，當(dāng)取d1=n， di+1=di/2(i=1,2,

13、3,)時，該算法的時間復(fù)雜度為T(n)=O(nlog2n)，空間復(fù)雜度為S(n)=O(1)。9.3交換排序法交換排序是借助于交換操作來完成的排序方法。它的基本思想是：在待排序的序列中，找到不滿足序性的兩個關(guān)鍵字，交換相應(yīng)元素的相對位置，以滿足序性；重復(fù)該過程，直到序列中所有元素的關(guān)鍵字都有序為止。本節(jié)主要介紹最為常見的兩個交換排序算法：起泡排序法和快速排序法。9.3.1起泡排序法(Bubble Sort)1算法思想(大數(shù)沉底法)起泡排序算法的基本思想是：先將第1個與第2個記錄的關(guān)鍵字比較，如果關(guān)鍵字逆序，則交換這兩個記錄，否則不交換；再將第2個與第3個記錄的關(guān)鍵字比較，如果關(guān)鍵字逆序，則交換第

14、2個與第3個記錄，否則不交換，以此類推，最后將第n-1個與第n個記錄的關(guān)鍵字比較，如果關(guān)鍵字逆序，則交換，否則不交換。上述過程稱為一趟起泡排序，其結(jié)果是使關(guān)鍵字值最大的記錄移到第n個記錄的位置。然后對前n-1個記錄進(jìn)行同樣的操作，第2趟起泡排序的結(jié)果是使關(guān)鍵字值次大的記錄移到第n-1個記錄的位置。一般地，第i趟起泡排序的結(jié)果是從前n-i個記錄中將關(guān)鍵字最大的記錄移到第n-i+1個記錄的位置上。如果在某一趟排序中沒有發(fā)生交換操作，則整個排序提前結(jié)束，否則最后排到僅剩一個記錄為止。2舉例說明設(shè)原始記錄序列為：8、3、5、2、9、7、*5、4第1趟排序結(jié)果：3,5,2,8,7,*5,4,(9)第2趟

15、排序結(jié)果：3,2,5,7,*5,4,(8,9)第3趟排序結(jié)果：2,3,5,*5,4,(7,8,9)第4趟排序結(jié)果：2,3,5,4,(*5,7,8,9)第5趟排序結(jié)果：2,3,4,(5,*5,7,8,9)第6趟排序結(jié)果：2,3,(4,5,*5,7,8,9)由于沒有發(fā)生交換操作，排序提前結(jié)束。3算法實現(xiàn)void BubbleSort(int A,int n)int i,j,t,f; /f=1時表示發(fā)生了交換操作for(f=1,i=n-1;i0&f;i-)for(f=0,j=0;jAj+1) /如果產(chǎn)生逆序f=1;t=Aj;Aj=Aj+1;Aj+1=t; /交換Aj與Aj+1的值4算法分析起泡排序算

16、法是穩(wěn)定的。容易算出，該算法的時間復(fù)雜度為T(n)=O(n2)，空間復(fù)雜度為S(n)=O(1)。算法的基本操作是交換操作，如果待排序的數(shù)組基本有序，那么可以大量地減少排序過程中的交換操作。所以，起泡排序算法適用于序列為基本有序的場合。9.3.2快速排序法(Quick Sort)1算法思想快速排序算法的基本思想是：通過一趟排序?qū)⒋庞涗浄指畛瑟毩⒌膬刹糠?，其中一部分的關(guān)鍵字均比另一部分的關(guān)鍵字小。接著對獨立的每一組記錄再分別進(jìn)行排序和分割，直到每一組中都只有一個記錄為止。2一趟快速排序的具體做法附設(shè)兩個指針low,high,其初值分別指向首個記錄和最后一個記錄，另設(shè)關(guān)鍵字為Key的樞軸記錄變量（

17、初始值為Low所指記錄）。首先從High所指記錄開始起向前搜索，找到第1個關(guān)鍵字小于Key的記錄同時將該記錄存儲到Low所指記錄中，然后從Low所指記錄開始向后搜索，找到第1個關(guān)鍵字大于Key的記錄存于High所指記錄中，再重復(fù)以上步驟，直到Low=High為止。最后將Key中記錄存儲到Low所指記錄中。3舉例說明設(shè)原始記錄序列為：38,13,27,76,65,49,49,97，其初始狀態(tài)如圖9.3所示。第1趟排序：27,13,(38),76,65,49,49,97第2趟排序：13,(27),(38),76,65,49,49,97第3趟排序：13,(27),(38),49,65,49,(76)

18、,97第4趟排序：13,(27),(38),(49),65,49,(76),97第5趟排序：13,(27),(38),(49),49,(65),(76),974快速排序的算法實現(xiàn)(1) 算法int Part(int* H,int low,int high)返回下標(biāo)值i，使得在數(shù)組元素Hlow到Hhigh中,Hi前面的元素均小于等于Hi，Hi后面的元素均大于等于Hi。int Part(int* H,int low,int high)int key=Hlow;while(lowhigh)while(low=key) high-;Hlow=Hhigh;while(lowhigh&Hlow=key)

19、low+;Hhigh=Hlow;Hlow=key;return(low); /返回Hlow到Hhigh中的樞軸變量下標(biāo)(2) 函數(shù)void Qsort(int* H,int low,int high)功能是，通過遞歸算法對數(shù)組H中從Hlow到Hhigh的元素進(jìn)行快速排序。void Qsort(int* H,int low,int high) /對數(shù)組元素Hlow到Hhigh進(jìn)行快速排序int p; /p為樞軸變量下標(biāo)if(lowAj則i=j，最后，如果i!=0時執(zhí)行A0與Ai的交換操作；第二趟，取下標(biāo)值i=1,下標(biāo)值j從2到n-1逐個由Ai與Aj進(jìn)行比較，如果AiAj則i=j，最后，如果i!=

20、1時執(zhí)行A1與Ai的交換操作；重復(fù)以上過程n-1次后，對數(shù)組An的排序過程結(jié)束。2舉例說明設(shè)原始記錄序列為：8、3、5、2、9、7、*5、4第1趟排序結(jié)果：(2),3,5,8,9,7,*5,4第2趟排序結(jié)果：(2,3),5,8,9,7,*5,4第3趟排序結(jié)果：(2,3,4),8,9,7,*5,5第4趟排序結(jié)果：(2,3,4,*5),9,7,8,5第5趟排序結(jié)果：(2,3,4,*5,5),7,8,9第6趟排序結(jié)果：(2,3,4,*5,5,7),8,9第7趟排序結(jié)果：(2,3,4,*5,5,7,8),93選擇排序的算法實現(xiàn)void SelectSort(int A,int n)int i,j,k,

21、t;for(i=0;in-1;i+)for(k=i,j=i+1;jn;j+)if(Aj=(8)49;(3)65=(6)13和(7)27;自然滿足；如圖9.4(a)所示。第2步：(2)38=(4)97和(5)76不滿足，執(zhí)行操作：先38與97互換，再38與49互換。調(diào)整后到結(jié)果如圖9.4(b)所示，其結(jié)果為：(1)49,(2)97,(3)65,(4)49,(5)76,(6)13,(7)27,(8)38第3步：(1)49=(2)97和(3)65不滿足，先執(zhí)行操作49與97互換，再49與76互換，調(diào)整結(jié)果如圖9.4(c)所示。最終結(jié)果為：(1)97,(2)76,(3)65,(4)49,(5)49,(

22、6)13,(7)27,(8)38(2) 通過對序列的重復(fù)調(diào)整進(jìn)行排序第1步：將(1),(8)互換，并將(1)到(7)的元素調(diào)整成為大頂堆，其結(jié)果如圖9.5(a)所示。第1步調(diào)整的結(jié)果為：(1)76,(2)49,(3)65,(4)49,(5)38,(6)13,(7)27,97第2步：將(1),(7)互換，并將(1)到(6)的元素調(diào)整成為大頂堆，其結(jié)果如圖9.5(b)所示。第2步調(diào)整的結(jié)果為：(1)65,(2)49,(3)27,(4)49,(5)38,(6)13,76,97第3步：將(1),(6)互換，并將(1)到(5)的元素調(diào)整成為大頂堆，其結(jié)果如圖9.5(c)所示。第3步調(diào)整的結(jié)果為：(1)4

23、9,(2)49,(3)27,(4)13,(5)38,65,76,97第4步：將(1),(5)互換，并將(1)到(4)的元素調(diào)整成為大頂堆，其結(jié)果如圖9.5(d)所示。第4步調(diào)整的結(jié)果如為：(1)49,(2)38,(3)27,(4)13,49,65,76,97依此類推，第5步為：(1)38,(2)13,(3)27,49,49,65,76,97；第6步為：(1)27,(2)13,38,49,49,65,76,97；第7步為：13,27,38,49,49,65,76,97。3堆排序的算法實現(xiàn)(1) 調(diào)整為大頂堆算法void HeapAdjust(int* H,int s,int m)的功能是，調(diào)整序

24、列H中元素，使序列中第s個到第m個元素成為大頂堆。void HeapAdjust(int* H,int s,int m)int j,t;t=Hs-1; j=s*2;while(j=m) /循環(huán)中s-1為雙親結(jié)點下標(biāo)，j-1為孩子結(jié)點下標(biāo)，t為要調(diào)整的值 if(jm&Hj-1=Hj-1)break; Hs-1=Hj-1;s=j; j=j*2;Hs-1=t;(2) 堆排序程序void HeapSort(int* H,int n)int i,t;for(i=n/2;i0;i-) /從最后一個分支結(jié)點開始通過循環(huán)調(diào)用HeapAdjust()構(gòu)造初始堆HeapAdjust(H,i,n);cout0;i-

25、) /對初始堆H進(jìn)行調(diào)整的排序過程t=H0;H0=Hi;Hi=t; HeapAdjust(H,1,i); /調(diào)整H中H0到Hi-1為堆4算法分析堆排序算法是不穩(wěn)定的；堆排序在最壞的情況下，其時間復(fù)雜度也是T(n)=O(nlog2n)，相對于快速排序而言這是他的最大優(yōu)點。由于實現(xiàn)堆排序時必須先構(gòu)造初始堆，所以該算法在待排序數(shù)組的數(shù)據(jù)元素較多時其優(yōu)勢更為明顯。9.5歸并排序(Merging Sort)9.5.1歸并的有關(guān)概念1n-路歸并的概念將n個有序序列進(jìn)行歸并，生成一個新的有序序列的過程稱為n-路歸并。22-路歸并排序的算法思想假設(shè)初始序列含有n個記錄，可以將其看成是長度為1的n個有序子序列，

26、然后兩兩歸并生成n/2個長度為2或1的有序子序列；下一步，再兩兩歸并成n/4個長度為4或2或1的有序子序列；如此進(jìn)行重復(fù)操作，直到最后得到一個長度為n的有序序列為止，這種排序方法稱為2-路歸并排序算法。3舉例說明設(shè)原始記錄序列為：38,13,49,76,65,27,49,97,33，其長度為n=9。先將其看成9個長度為1的有序序列為：(38),(13),(49),(76),(65),(27),(49),(97),(33)完成第1趟2路歸并排序后得到9/2=5個有序序列，它們是：(13,38),(49,76),(27,65),(49,97),(33)完成第2趟2路歸并排序后得到5/2=3個有序序

27、列，它們是：(13,38,49,76),(27,49,65,97),(33)完成第3趟2路歸并排序后得到3/2=2個有序序列，它們是：(13,27,38,49,49,65,76,97),(33)完成第4趟歸并排序后的結(jié)果為：(13,27,33,38,49,49,65,76,97)9.5.2 2-路歸并排序的算法實現(xiàn)1兩個有序序列的歸并算法函數(shù)void Merge(int A,int s,int t,int n)的作用是將兩個有序序列As,t, 和At+1,n歸并到As,n。void Merge(int A,int s,int t,int n)int* C=new intn-s+1; /定義臨時

28、存儲空間Cint i,j,k;i=s,j=t+1,k=0;while(i=t&j=n)if(Ai=Aj) Ck+=Ai+;else Ck+=Aj+;while(i=t)Ck+=Ai+;while(j=n)Ck+=Aj+;for(k=0,i=s;i=n;i+)Ai=Ck+; /將C中的歸并結(jié)果復(fù)制到A中deleteC;2歸并排序算法的實現(xiàn)程序函數(shù)void MSort(int SR,int s,int t)的作用是，通過遞歸調(diào)用實現(xiàn)對數(shù)據(jù)元素SRs,t的排序過程。void MSort(int SR,int s,int t)int m=(s+t)/2;if(s=t)return;MSort(SR,s

29、,m);MSort(SR,m+1,t);Merge(SR,s,m,t);void MergeSort(int A,int n)MSort(A,0,n-1); 3算法分析歸并排序算法是穩(wěn)定的；該算法的時間復(fù)雜度是T(n)=O(nlog2n)，空間復(fù)雜度為S(n)=O(n)。歸并排序算法的最大特點是該算法是穩(wěn)定的；但是，該算法需要有存放n個元素大小的輔助空間。9.6基數(shù)排序(Radix Sort)算法9.6.1基數(shù)排序的有關(guān)概念1最低位基數(shù)優(yōu)先(LSD)排序法假定序列中每個記錄的關(guān)鍵字從高（左）到低（右）排列為：K1,K2,Kd,共有d個關(guān)鍵字。先按關(guān)鍵字Kd起對序列進(jìn)行排序，然后再對序列按Kd-

30、1進(jìn)行排序，依次重復(fù)，直到對K1進(jìn)行排序后便成為一個有序序列。2舉例說明設(shè)原始記錄序列為：278,109,063,930,589,184,505,269,008,083(1) 從前往后按個位數(shù)排序(k3)：(930),(k3=1),(k3=2),(063,083),(184),(505),(k3=6),(k3=7),(278,008),(109,589,269)(2) 從前往后按十位排序(k2)：(505,008,109),(k2=1),(k2=2),(930),(k2=4),(k2=5),(063,269),(278),(083,184,589),(k2=9)(3) 從前往后按百位排序(k1

31、)：(008,063,083),(109,184),(269,278),(k1=3),(k1=4),(505,589),(k1=6),(k1=7),(k1=8),(930)排序結(jié)果為：8,63,83,109,184,269,278,505,589,9309.6.2基數(shù)排序法(LSD)的算法實現(xiàn)以下給出對n個整數(shù)的基數(shù)排序算法1函數(shù)Get(m,k)為取m的第k位數(shù)的值int Get(int m,int k)int i,n=m;for(i=1;ik;i+)n=n/10;n=n%10;return n;2按數(shù)組An中的第k位排序的操作void LSD(int A,int n,int k)int* p

32、10,i,j,s; /pi為關(guān)鍵字的值為i的所有元素int m10=0,e; /mi為pi中元素的最大下標(biāo)。for(i=0;i10;i+)pi=new intn;for(i=0;in;i+) /根據(jù)數(shù)組An中第i個元素的第k位的值e將Ai分配到數(shù)組pe中；e=Get(Ai,k);peme+=Ai;for(i=0,j=0;j10;j+) /收集數(shù)組p0,p1,.,p9中的元素到數(shù)組An中；for(s=0;smj;s+)Ai+=pjs;deletepj;3低位優(yōu)先(LSD)基數(shù)排序法的算法實現(xiàn)void RdSort(int A,int n)int m=A0,k,i;for(i=1;im)m=Ai;

33、 /求最大元素到變量m中k=1;while(m=m/10)k+; /求最大元素m的位數(shù)（寬度）kfor(i=1;i=k;i+)LSD(A,n,i); /按低位優(yōu)先對數(shù)組A排序4算法分析基數(shù)排序法是穩(wěn)定的，時間復(fù)雜度T(n)=O(d(n+rd),空間復(fù)雜度為S(n)=O(n)。其中d為關(guān)鍵字的個數(shù)，rd為關(guān)鍵字的取值個數(shù)。從基數(shù)排序算法的實現(xiàn)過程可知：該算法適用于n很大而且d比較小的情況。9.6.3調(diào)用各種排序算法進(jìn)行排序的演示程序void main()int num;while(1)cout1-直接插入排序法,2-希爾排序法,3-冒泡排序法n;cout4-快速排序法,5-直接選擇排序法,6-堆

34、排序法n;coutnum;switch(num)case 1:MainSort(InsertSort);break; case 2:MainSort(ShellSort);break;case 3:MainSort(BubbleSort);break;case 4:MainSort(QuickSort);break;case 5:MainSort(SelectSort);break;case 6:MainSort(HeapSort);break; case 7:MainSort(MergeSort);break;case 8:MainSort(RdSort);break;case 9:retu

35、rn;default: cout選擇出錯請重新選擇:n;（運行過程略）9.7各種內(nèi)部排序方法的比較內(nèi)部排序在計算機程序設(shè)計中非常重要，本章中討論的幾種排序方法各有其優(yōu)缺點，適用場合也不同。從排序方法的時間復(fù)雜度和空間復(fù)雜度以及排序方法的穩(wěn)定性方面進(jìn)行比較，歸納結(jié)果如表9.1所示。從表中數(shù)據(jù)可以得出如下結(jié)論：(1) 如果待排序記錄的初始狀態(tài)已經(jīng)按關(guān)鍵字基本有序，則可選擇起泡排序法或直接插入排序法。(2) 選擇排序、起泡排序和插入排序僅適用于記錄數(shù)n較小的情況。選擇排序的時間性能與待排記錄的初始狀態(tài)無關(guān)，且該排序方法不穩(wěn)定。插入排序在排序過程中無法知道部分連續(xù)位置上的最終元素。(3) 從平均時間復(fù)

36、雜度而言，快速排序法最佳。但快速排序在最壞的情況下（序列基本有序）時將蛻化為冒泡排序法，此時時間性能不如堆排序和歸并排序。(4) 當(dāng)記錄數(shù)n較大時，歸并排序比堆排序的速度快，且歸并排序是穩(wěn)定的而堆排序不穩(wěn)定。但是，歸并排序的輔助空間比堆排序多。(5) 基數(shù)排序可以在時間內(nèi)完成對n個記錄的排序。其中，d是指記錄中所含邏輯關(guān)鍵字的最大個數(shù)，rd是指邏輯關(guān)鍵字的取值范圍，即基數(shù)個數(shù)?；鶖?shù)排序法適用于字符串或整數(shù)等具有明顯結(jié)構(gòu)特征的關(guān)鍵字；如果n很大，d較小時，用基數(shù)排序較好。本章討論的排序算法，都是在向量存儲結(jié)構(gòu)上實現(xiàn)的。當(dāng)記錄本身信息量很大時，為了避免大量時間用在移動數(shù)據(jù)上，可以利用鏈表作為存儲結(jié)

37、構(gòu)。插入排序和歸并排序都容易在鏈表上實現(xiàn)，但是有的排序方法比如堆排序和快速排序方法就不易在鏈表上實現(xiàn)。9.8 習(xí) 題一、問答題1什么是內(nèi)部排序？什么是排序方法的穩(wěn)定性？2在本章介紹的內(nèi)部排序方法中，穩(wěn)定的排序方法有哪些？不穩(wěn)定的排序方法有哪些？對于不穩(wěn)定的排序方法試舉例說明。3對于給定的一組記錄的關(guān)鍵字：23,13,17,21,30,60,58,28試分別寫出用下列排序方法對其進(jìn)行排序時，每一趟排序后的結(jié)果：（1）直接插入排序； （2）希爾排序；（3）起泡排序； （4）直接選擇排序；（5）快速排序； （6）堆排序；（7）歸并排序。4對長度為n的記錄序列進(jìn)行快速排序時，所需要的比較次數(shù)依賴于序列

38、中n個元素的初始排列順序。（1）n=8時，在最好的情況下需要進(jìn)行多少次比較？試說明理由。（2）給出n=8時的一個最好情況的初始排列實例。5試為下列各種情況選擇合適的排序方法：（1）n=30，要求在最壞的情況下，排序速度最快；（2）n=30，要求排序速度最快，又要排序穩(wěn)定。6判別以下序列是否為堆（包括大頂堆和小頂堆），如果不是，則把它調(diào)整成為堆。（1）（100,86,48,73,35,39,42,57,66,21）；（2）（12,70,33,65,24,56,48,92,86,33）；（3）（103,97,56,38,66,23,42,12,30,52,6,20）；（4）（5,56,20,3,2

39、3,40,38,29,61,5,76,28,100）。7一組待排序記錄的關(guān)鍵字是：986,321,123,432,500,654,018,765,987,210按照LSD方法寫出基數(shù)排序的過程和結(jié)果。8試構(gòu)造對5個整數(shù)元素進(jìn)行排序，最多只用7次比較的算法思想。9有n個不同的英文單詞，它們的長度相等，均為m，如果n50,且m5,試問采取什么排序方法時間復(fù)雜度最佳？為什么？10如果想得到一個序列中第k個最小元素的部分排序序列，最好采用什么排序方法？為什么？如果有這樣的一個序列：（57,40,38,11,13,34,48,57,25,6,19,9,7）得到其第4個最小元素之前的部分序列（6,7,9,

40、11），使用所選擇的算法實現(xiàn)時，要執(zhí)行多少次比較？二、填空題1在所學(xué)的排序方法中，關(guān)鍵字比較次數(shù)與記錄的初始排列次序無關(guān)的是（ ）。2設(shè)有1000個無序元素，希望用最快的速度挑選出其中的前10個最大的元素，最好選用（ ）排序法。3在待排序的元素序列基本有序的情況下，效率最高的排序方法是（ ）。4一組記錄的關(guān)鍵字為（46,79,56,38,40,84），則利用堆排序的方法建立的初始堆是（ ）。5一組記錄的關(guān)鍵字值是（46,82,40,52,67,31,21,73），則利用快速排序的方法，以第一個記錄為基準(zhǔn)得到的一次劃分結(jié)果為（ ）。6排序方法中，從未排序序列中依次取出元素，與已排序序列（初始為空

41、）中的元素進(jìn)行比較，將其插入已排序序列的正確位置上的方法，稱為（ ）。7排序方法中，從未排序序列中依次取出元素，并將其依次放入已排序序列（初始為空）的一端的方法，稱為（ ）。8用某種排序方法，對元素序列（25,84,21,47,15,27,68,35,20）進(jìn)行排序，每一趟排序后元素序列的變化情況如下：（1）25，84，21，47，15，27，68，35，20（2）20，15，21，25，47，27，68，35，84（3）15，20，21，25，35，27，47，68，84（4）15，20，21，25，27，35，47，68，84則采用的排序方法是（ ）。9快速排序方法在（ ）情況下最不利于發(fā)揮其長處。10在插入排序、選擇排序、快速排序和歸并排序中（ ）方法要求其內(nèi)存量最大。11在插入排序、選擇排序、快速排序和歸并排序中，平均查找時間最短的是（ ）。12使用直接插入排序法對一組記錄（54,38,96,23,15,72,60,54,83）進(jìn)行排序，當(dāng)把第7個記錄60插入到有序表時，為尋找插入位置需要比較（ ）次