課后答案網(wǎng) 10 章 排序 一、 基礎(chǔ)知識題 本概念：內(nèi)排序，外排序，穩(wěn)定排序，不穩(wěn)定排序，順串，敗者樹，最佳歸并樹。 【解答】內(nèi)排序和外排序 若整個排序過程不需要訪問外存便能完成，則稱此類排序問題為 內(nèi)部排序 ；反之，若參加排序的記錄數(shù)量很大，整個序列的排序過程不可能在內(nèi)存中完成，則稱此類排序問題為 外部排序 。內(nèi)部排序適用于記錄個數(shù)不多的文件，不需要訪問外存，而外部排序適用于記錄很多的大文件，整個排序過程需要在內(nèi)外存之間多次交換數(shù)據(jù)才能得到排序的結(jié)果。 穩(wěn)定排序和不穩(wěn)定排序 假 設(shè)待排序記錄中有關(guān)鍵字 j（ i j），且在排序前的序列中 先于 過排序后， 相對次序保持不變（即領(lǐng)先于 則稱這種排序方法是 穩(wěn)定的 ，否則稱之為 不穩(wěn)定的 。 順串 外部排序通 常 經(jīng)過兩個獨立的階段完成。第一階段，根據(jù)內(nèi)存大小，每次把文件中一部分記錄讀入內(nèi)存，用有效的內(nèi)部排序方法（如快速排序、堆排序等）將其排成 有序段， 這有序段又稱 順串 或 歸并段 。 敗者樹 敗者樹為提高外部排序的效率而采用的，是由參加比賽的 個非葉（雙親）結(jié)點中存放的是兩個子 結(jié)點中的敗者數(shù)據(jù) ,而讓勝者去參加更高一級的比賽。另外 ,還需增加一個結(jié)點 ,即結(jié)點 0,存放比賽的全局獲勝者。 最佳歸并樹 在外部排序的多路平衡歸并的 了提高效率減少對外存的讀寫次數(shù)，按哈夫曼樹構(gòu)造的 k 叉樹稱 最佳歸并樹。這棵樹中只有度為0和度為 用 m 表示 歸并段個數(shù)，用 示度為 k 的個數(shù)，若(0，則不需增加虛段，否則應(yīng)附加 k-(1 個虛段（即第一個 k 路歸并使用 (1 個歸并段）。 待排序的關(guān)鍵字序列為 (15， 21， 6， 30， 23， 6， 20， 17)， 試分別寫出使用以下排序方法每趟排序后的結(jié)果。并說明做了多少次比較。(1) 直接插入排序 (2) 希爾排序 (增量為 5， 2， 1) (3) 起泡排序(4) 快速排序 (5) 直接選擇排序 (6) 錦標賽排序(7) 堆排序 (8) 二路歸并排序 (9) 基數(shù)排序 【解答】 (1) 直接插入排序 初始關(guān)鍵字序列： 15， 21， 6， 30， 23， 6， 20， 17 第一趟直接插入排序：【 15， 21】 第二趟直接 插入排序：【 6， 15， 21】 第三趟直接插入排序：【 6， 15， 21， 30】 第四趟直接插入排序：【 6， 15， 21， 23， 30】 第五趟直接插入排序：【 6， 6， 15， 21， 23， 30】 第六趟直接插入排序：【 6， 6， 15， 20， 21， 23， 30】 課后答案網(wǎng) 七趟直接插入排序：【 6， 6， 15， 17， 20， 21， 23， 30】 (2) 希爾排序 (增量為 5， 2， 1) 初始關(guān)鍵字序列： 15， 21， 6， 30， 23， 6， 20， 17 第一趟希爾排序： 6， 20， 6， 30， 23， 15， 21， 17 第二 趟希爾排序： 6， 15， 6， 17， 21， 20， 23， 30 第三趟希爾排序： 6， 6， 15， 17， 20， 21， 23， 30 (3) 起泡排序 初始關(guān)鍵字序列： 15， 21， 6， 30， 23， 6， 20， 17 第一趟起泡排序： 15， 6， 21， 23， 6， 20， 17， 30 第二趟起泡排序： 6， 15， 21， 6， 20， 17， 23， 30 第三趟起泡排序： 6， 15， 6， 20， 17， 21， 23， 30 第四趟起泡排序： 6， 6， 15， 17， 20， 21， 30， 23 第五趟起泡排序： 6， 6， 15， 17， 20， 21， 30， 23 (4) 快速排序 初始關(guān)鍵字序列： 15， 21， 6， 30， 23， 6， 20， 17 第一趟快速排序： 【 6， 6】 15【 30， 23， 21， 20， 17】 第二趟快速排序： 6， 6， 15【 17， 23， 21， 20】 30 第三趟快速排序： 6， 6， 15， 17【 23， 21， 20】 30 第四趟快速排序： 6， 6， 15， 17，【 20， 21】 23， 30 第五趟快速排序： 6， 6， 15， 17， 20， 21， 30， 23 (5) 直接選擇排序 初始關(guān)鍵字序列： 15， 21， 6， 30， 23， 6， 20， 17 第一趟直接選擇排序： 6， 21， 15， 30， 23， 6， 20， 17 第二趟直接選擇排序： 6， 6， 15， 30， 23， 21， 20， 17 第三趟直接選擇排序： 6， 6， 15， 30， 23， 21， 20， 17 第四趟直接選擇排序： 6， 6， 15， 17， 23， 21， 20， 30 第五趟直接選擇排序： 6， 6， 15， 17， 20， 21， 23， 30 第六趟直接選擇排序： 6， 6， 15， 17， 20， 21， 23， 30 第七趟直接選擇排序： 6， 6， 15， 17， 20， 21， 23， 30 (6) 錦標賽排序 初始關(guān)鍵字序列： 15， 21， 6， 30， 23， 6， 20， 17 6 6 6 15 6 6 17 15 21 6 課后答案網(wǎng) 0 23 6 20 17 6 15 6 15 30 6 17 15 21 30 23 6 20 17 課后答案網(wǎng) 5 15 23 15 30 23 17 15 21 30 23 20 17 錦標賽排序 的基本思想是：首先對 中選出 n/2 個較小者再兩兩比較，直到選出關(guān)鍵字最小的記錄為止，此為一趟排序。我們將一趟選出的關(guān)鍵字最小的記錄稱為“冠軍”，而“亞軍”是從與“冠軍”比較失敗的記錄中找出，具體做法為：輸出“冠軍”后，將（冠軍）葉子結(jié)點關(guān)鍵字改為最大，繼續(xù)進行錦標賽排序，直到選出關(guān)鍵字次小的記錄為止， 如此循環(huán)直到輸出全部有序序列。上面給出了排在前三個的記錄，詳細過程略。 (7) 堆排序 初始關(guān)鍵字序列： 15， 21， 6， 30， 23， 6， 20， 17 初始堆： 6， 17， 6， 21， 23， 15， 20， 30 課后答案網(wǎng) 一次調(diào)堆： 6， 17， 15， 21， 23， 30， 20，【 6】 第二次調(diào)堆： 15， 17， 20， 21， 23， 30，【 6， 6】 第三次調(diào)堆： 17， 21， 20， 30， 23，【 15， 6， 6】 第四次調(diào)堆： 20， 21， 23， 30，【 17， 15， 6， 6】 第五次調(diào)堆： 21， 30， 23，【 20， 17， 15， 6， 6】 第六次調(diào)堆： 23， 30，【 21， 20， 17， 15， 6， 6】 第七次調(diào)堆： 30，【 23， 21， 20， 17， 15， 6， 6】 堆排序結(jié)果 調(diào)堆：【 30， 23， 21， 20， 17， 15， 6， 6】 (8) 二路歸并排序 初始關(guān)鍵字序列： 15， 21， 6， 30， 23， 6， 20， 17 二路歸并排序結(jié)果 ： 15， 17， 20， 21， 23， 30， 6， 6 9) 基數(shù)排序 初始關(guān)鍵字序列： p 15 21 6 30 23 6 20 17 第一次分配得到 : B030 20 B0121 B1323 B3515 B566 6 B6717 B7一次收集得到 : p 30 20 21 23 15 6 6 17 第二次分配得到 B06 6 B0115 17 B1220 21 23 B5330 B3二次收集得到 p 6 6 15 17 20 21 23 30 基數(shù)排序結(jié)果 ： 6， 6， 15， 17， 20， 21， 23， 30 各種排序方法中，哪些是穩(wěn)定的？哪些是不穩(wěn)定的？并為每一種不穩(wěn)定的排序方法舉出一個不穩(wěn)定的實例。 【解答】見下表： 排序方法 平均時間 最壞情況 輔助空間 穩(wěn)定性 不穩(wěn)定排序舉例 直接插入排序 O(O(O(1) 穩(wěn)定 折半插入排序 O(O(O(1) 穩(wěn)定 二路插入排序 O(O(O(n) 穩(wěn)定 表插入排序 O(O(O(1) 穩(wěn)定 起泡排序 O(O(O(1) 穩(wěn)定 課后答案網(wǎng) 接選擇排序 O(O(O(1) 不穩(wěn)定 2,2 ,1 希爾排序 O(O(O(1) 不穩(wěn)定 3,2,2 ,1(d=2,d=1) 快速排序 O(O(O(不穩(wěn)定 2,2 ,1 堆排序 O(O(O(1) 不穩(wěn)定 2,1,1 (極大堆 ) 2O(O(O(n) 穩(wěn)定 基數(shù)排序 O(d*(rd+n) O(d*(rd+n) O ( 穩(wěn)定 執(zhí)行某種排序算法的過程中出現(xiàn)了排序碼朝著最終排序序列相反的方向移動，從而認為該排序算法是不穩(wěn)定的，這種說法對嗎？為什么？ 【解答】 這種說法不對。因為排序的不穩(wěn)定性是指兩個關(guān)鍵字值相同的元素的相對次序在排序前、后發(fā)生了變化，而題中敘述和排序中穩(wěn)定性的定義無關(guān)，所以此說法不對。對 4， 3， 2， 1起泡排序就可否定本題結(jié) 論。 堆排序、快速排序和歸并排序方法中： (1)若只從存儲空間考慮，則應(yīng)首先選取哪種排序，其次選取哪種排序，最后選取哪種排序？ (2)若只從排序結(jié)果的穩(wěn)定性考慮，則應(yīng)選取哪種排序方法？ (3)若只從平均情況下排序最快考慮，則應(yīng)選取哪種排序方法？ (4)若只從最壞情況下排序最快并且要節(jié)省內(nèi)存考慮，則應(yīng)選取哪種排序方法？ 【解答】 (1)堆排序，快速排序，歸并排序 (2)歸并排序 (3)快速排序 (4)堆排序 設(shè)要求從大到小排序。問在什么情況下冒泡排 序算法關(guān)鍵字交換的次數(shù)為最多。 【解答】 對冒泡算法而言，初始序列為反序時交換次數(shù)最多。若要求從大到小排序，則表現(xiàn)為初始是上升序時 關(guān)鍵字交換的次數(shù)為最多。 速排序的最大遞歸深度是多少？最小遞歸深度是多少？ 【解答】 設(shè)待排序記錄的個數(shù)為 n,則快速排序的最小遞歸深度為 1,最大遞歸深度 n。 們知道，對于 n 個元素組成的順序表進行快速排序時，所需進行的比較次數(shù)與這 n 個元素的初始排序有關(guān)。問： (1) 當 n=7 時，在最好情況下需進行多少次比較？請說明理由。 (2) 當 n=7 時，給出一個最好情況的初始排序的實例。 (3) 當 n=7 時，在最壞情況下需進行多少次比較？請說明理由。 (4) 當 n=7 時，給出一個最壞情況的初始排序的實例。 【解答】 課后答案網(wǎng) 1) 在最好情況下 ,每次劃分能得到兩個長度相等的子文件。假設(shè)文件的長度n=2么第一遍劃分得到兩個長度均為 n/2 的子文件 ,第二遍劃分得到 4 個長度均為 n/4的子文件 ,以此類推 ,總共進行 k=n+1)遍劃分 ,各子文件的長度均為 1,排序完畢。當 n=7 時 ,k=3,在最好情況下 ,第一遍需比較 6次 ,第二遍分別對兩個子文件（長度 均為 3,k=2）進行排序 ,各需 2 次 ,共 10 次即可。 (2) 在最好情況下快速排序的原始序列實例 ： 4,1,3,2,6,5,7。 (3) 在最壞情況下 ,若每次用來 劃分的記錄的關(guān)鍵字具有最大 (或最小 )值 ,那么只能得到左 (或右 )子文件 ,其長度比原長度少 1。因此 ,若原文件中的記錄按關(guān)鍵字遞減次序排列 ,而要求排序后按遞增次序排列時 ,快速排序的效率與冒泡排序相同 ,其時間復(fù)雜度為 O(所以當 n=7 時 ,最壞情況下的比較次數(shù)為 21次。 (4) 在最壞情況下快速排序的初始序列實例 ： 7,6,5,4,3,2,1,要求按遞增排序。 斷下面的每個結(jié)點序列是否表示一個堆，如果不是堆，請把它調(diào)整成堆。 (1) 100， 90， 80， 60， 85， 75， 20， 25， 10， 70， 65， 50 (2) 100， 70， 50， 20， 90， 75， 60， 25， 10， 85， 65， 80 【解答】 (1) 是堆 (2) 不是堆。 調(diào)成大堆： 100,90,80,25,85,75,60,20,10,70,65,50 在多關(guān)鍵字排序時， 種方法的特點是什么？ 【解答】 最高位優(yōu)先 （ ：先對最高位關(guān)鍵字 將序列分成若干子序列 ,每個子序列中的記錄都具有相同的 然后 ,分別就每個子序列對關(guān)鍵字按 ,依次重復(fù) ,直至最后對最低位關(guān)鍵字排序完成 ,將所有子序列依次連接在一起 ,成為一個有序子序列。 最低位優(yōu)先（ ：先對最低位關(guān)鍵字 然后對高一級關(guān)鍵字 依次重復(fù) ,直至對最高位關(guān)鍵字 行排序時 ,不必分成子序列 ,對每個關(guān)鍵字都是整個序列參加排序 ,但對 0Ai+1，則將兩者交換；第二趟對所有偶數(shù) i(2Ai+1，則將兩者交換；第三趟對所有奇數(shù) i(1 p) 課后答案網(wǎng) q=p- r=p; 設(shè) r 是指向關(guān)鍵字最小的結(jié)點的指針 q!=if(q-r=q; q=q- r!=p) r-p=p- 設(shè)單鏈表頭結(jié)點指針為 L，結(jié)點數(shù)據(jù)為整型。試寫出對鏈表 L 按“直接插入方法”排序的算法。 ) /本算法對單 鏈表 接插入方法”進行排序 p=L- /鏈表至少一個結(jié)點 ,p 初始指向鏈表中第二結(jié)點（若存在） L-(p!= q=p- /q 指向 p 的后繼結(jié)點 s=L; s-& s-s=s- /向后找插入位置 p-s-s-p;/插入結(jié)點 p=q; /恢復(fù) 試設(shè)計一個雙向冒泡排序算法，即在排序過程中交替改變掃描方向。 a,n) 相鄰兩趟向相反方向起泡的冒泡排序算法 ; 冒泡的上下界 i+1)aiai+1; 有交換 ,修改標志 修改上界 i=i 氣泡下沉 ,小元素上?。ㄏ蜃螅?if(aia; 課后答案網(wǎng) ; 修改下界 寫出快速排序的非遞歸算法。 rn+1; n) 對 r1.行快速排序的非遞歸算法 sn+1；棧 ,容量足夠大 r, 函數(shù)聲明 ; s; sn; ) ss=stt=s if(s+s if() s+k+1; s 算法結(jié)束 r;s,t) i=s; j=t; rp=ri; x=ri i=rji+; if(k=r,ss, if( 一趟排序后分割成左右兩部分 if() 左部子序列長度大于右部 ,左部進棧 課后答案網(wǎng) s+s if() ss=k+1; 右部短的直接處理 右部處理完 ,需退棧 if() 右部子序列長度大于左部 ,右部進棧 s+k+1; s if() tt= 左部短的直接處理 左部處理完 ,需退棧 & ) 退棧 ss=stt=s of | ) 算法結(jié)束 r;s,t) 用“三者取中法” 進行快速排序的一次劃分 i=s, j=t, s+t)/2; if(rirri;ri=rr if(rrjrj;rj=r if(ri) rrri;ri= ri;ri=rr 三者取中：最佳 2次比較 3 次賦值；最差 3次比較 10 次賦值 rp=ri; x=ri i=rji+; if(irj; i+;j+; if(rj=2) j+