第9章習(xí)題答案

1、習(xí)題91.在各種排序方法中，哪些是穩(wěn)定的？哪些是不穩(wěn)定的？對不穩(wěn)定的排序方法舉出一個不穩(wěn)定的例子。解：排序方法平均時間最壞情況輔助空間穩(wěn)定性不穩(wěn)定排序舉例直接插入排序折半插入排序二路插入排序表插入排序起泡排序直接選擇排序希爾排序快速排序堆排序2-路歸并排序基數(shù)排序穩(wěn)定穩(wěn)定穩(wěn)定穩(wěn)定穩(wěn)定不穩(wěn)定不穩(wěn)定不穩(wěn)定不穩(wěn)定穩(wěn)定穩(wěn)定2,2,13,2,2,1(d=2，d=1)2,2,12,1,1(大頂堆)2.若不考慮基數(shù)排序，則排序的兩種基本操作是什么？解：關(guān)鍵字的比較和記錄的移動。3.外排序的基本操作是什么？解：生成有序歸并段，歸并。4.分別采用堆排序、快速排序、起泡排序和歸并排序，對初始狀態(tài)為有序的表，則最省

2、時間的是哪種排序方法？最費時間的是哪種排序方法？解：起泡排序，快速排序。5.不受待排序初始序列的影響的排序算法是哪種？其時間復(fù)雜度是多少？解：簡單選擇排序，時間復(fù)雜度是。6.直接插入排序設(shè)置監(jiān)視哨的作用是什么？解：免去查找過程中每一步都要檢測整個表是否查找完畢，提高了查找效率。7.從平均時間性能而言，哪種排序方法最佳？解：快速排序。8.設(shè)待排序的記錄有10個，其關(guān)鍵字分別為75，23，98，44，57，12，29，64，38，82。手工執(zhí)行以下排序算法(按字典序比較關(guān)鍵字的大小)，寫出每一堂排序結(jié)束時的關(guān)鍵字的狀態(tài)：(1)直接插入排序(2)折半插入排序(3)起泡排序(4)簡單選擇排序(5)快速

3、排序(6)希爾排序(7)2-路歸并排序(8)基數(shù)排序解：略9.已知記錄序列R1.n中的關(guān)鍵字各不相同，可按如下所述實現(xiàn)計數(shù)排序：另設(shè)數(shù)組C1.n，對每個記錄Ri，統(tǒng)計序列中關(guān)鍵字比它小的記錄個數(shù)存于Ci，則Ci=0的記錄必為關(guān)鍵字最小的記錄，然后依Ci值的大小對R中記錄進行重新排列，試編寫實現(xiàn)上述排序的算法。解：void Count_Sort(int R,int n)/計數(shù)排序算法 int CMAX; for(i=0;i<n;i+)/對每一個元素 for(j=i,count=0;j<n;j+) /統(tǒng)計關(guān)鍵字比它小的元素個數(shù) if(Rj<Ri)count+; Ci=count;

4、 for(i=0;i<n;i+)/依次求出關(guān)鍵字最小,第二小,.,最大的記錄 min=i; for(j=i+1;j<n;j+) if(Cj<Cmin) min=j; /求出最小記錄的下標(biāo)min temp=Ri;Ri=Rmin; Rmin=temp; /與第i個記錄交換 Cmin=Ci; /Count_Sort10.已知奇偶交換算法如下描述：第一趟對所有奇數(shù)的i，將Ri和Ri+1進行比較，第二趟對所有偶數(shù)的i，將Ri和Ri+1進行比較，每次比較時若Ri>Ri+1，則將兩者交換，以后重復(fù)上述二趟過程，直到整個數(shù)組有序。(1)試問排序結(jié)束的條件是什么？(2)編寫一個實現(xiàn)上述排

5、序過程的算法。解：void OE_Sort(int R ,int n)/奇偶交換排序的算法 change=1; while(change) change=0; for(i=1;i<n-1;i+=2) /對所有奇數(shù)進行一趟比較 if(Ri>Ri+1) temp=Ri; Ri=Ri+1; Ri+1=temp; change=1; for(i=0;i<n-1;i+=2) /對所有偶數(shù)進行一趟比較 if(Ri>Ri+1) temp=Ri; Ri=Ri+1; Ri+1=temp; change=1; /while/OE_Sort 本算法的結(jié)束條件是連續(xù)兩趟比較無交換發(fā)生。11.編

6、寫算法，對n個關(guān)鍵字取整數(shù)值的記錄進行整理，使得所有關(guān)鍵字為負(fù)值的記錄排在關(guān)鍵字為非負(fù)值的記錄之前，要求：(1)采用順序存儲結(jié)構(gòu)，至多使用一個記錄的輔助存儲空間。(2)算法的時間復(fù)雜度為。(3)討論算法中記錄的最大移動次數(shù)。解：void Divide(int R,int n)/把數(shù)組R中所有值為負(fù)的記錄調(diào)到非負(fù)的記錄之前 low=0;high=n-1;while(low<high) while(low<high&&Rhigh>=0) high-; /以0作為虛擬的樞軸記錄 temp=Rlow; Rlow=Rhigh; Rhigh=temp; while(low

7、<high&&Rlow<0) low+; temp=Rlow; Rlow=Rhigh; Rhigh=temp; /Divide12.序列的“中值記錄”指的是：如果將此序列排序后，它是第n/2個記錄。試編寫一個求中值記錄的算法。解：typedef struct int gt; /大于該記錄的個數(shù) int lt; /小于該記錄的個數(shù)pl; /整個序列中比某個關(guān)鍵字大或小的記錄個數(shù)KeyType MidElement(SqList &L)if(!L.length)return 0;pl bMAX;RcdType temp;int i,j,min,t;for(i=1

8、; i<=L.length; i+)/對每一個元素統(tǒng)計比它大和比它小的元素個數(shù)gt和lt for(bi.gt=0, bi.lt=0,j=1;j<=L.length; j+)if(L.rj.key>L.ri.key)bi.gt+;else if(L.rj.key<L.ri.key)bi.lt+;for(i=1; i<=L.length; i+)min=i;for(j=i+1;j<=L.length;j+)if(bj.lt<bmin.lt)min=j;/求出最小記錄的下標(biāo)mintemp=L.ri;L.ri=L.rmin;L.rmin=temp;/與第i個記

9、錄交換t=bi.gt+;bi.gt=bmin.gt+;bi.gt+;bmin.gt=t;bmin.gt+;t=bi.lt+;bi.lt=bmin.lt+;bi.lt+;bmin.lt=t;bmin.lt+;int mid=(L.length+1)/2;return L.rmid.key;13.有序數(shù)組是堆嗎？解：有序數(shù)組是堆。因為有序數(shù)組中的關(guān)鍵字序列滿足堆的性質(zhì)。若數(shù)組為降序，則此堆為大頂堆，反之為小頂堆。14.在高度為h的堆中，最多有多少個記錄？最少有多少個記錄？在大頂堆中，關(guān)鍵字最小的記錄可能存放在堆的哪些位置？解：高度為h的堆實際上為一棵高度為h的完全二叉樹，因此根據(jù)二叉樹的性質(zhì)可以算出，它最少應(yīng)有2h-1個元素；最多可有2h-1個元素(注意一個有括號，一個沒有)。在大頂堆中，關(guān)鍵字最小的元素可能存放在堆的任一葉子結(jié)點上。15.若關(guān)鍵字是非負(fù)整數(shù)，快速排序、歸并