1、第9章排序靜態(tài)數(shù)據(jù)表類定義#include const int DefaultSize = 100;template classdataListtemplate classElement friend class dataList ;private:Type key;field otherdata;public:Type getKey ( ) return key; void setKey ( const Type x ) key = x; Element& operator = ( Element& x ) key = x- key; otherdata = x- otherdata; in

2、t operator = ( Type& x ) return key = x- key; int operator = ( Type& x ) return key key; int operator ( Type& x ) return key x- key; int operator x- key; 數(shù)據(jù)表的前視聲明數(shù)據(jù)表元素類的定義排序碼其它數(shù)據(jù)成員取當(dāng)前結(jié)點(diǎn)的排序碼將當(dāng)前結(jié)點(diǎn)的排序碼修改為x/結(jié)點(diǎn)x的值賦給this判this與x相等判this小于或等于x判this大于x判this小于xtemplate classdataList 用順序表來存儲(chǔ)待排序的元素，這些元素的類型是Typep

3、rivate:Element * Vector;存儲(chǔ)待排序元素的向量int MaxSize, CurrentSize;最大元素個(gè)數(shù)與當(dāng)前元素個(gè)數(shù)int Partition ( const int low, const int high )用于快速排序的一次劃分算法public:datalist ( int MaxSz = DefaultSize ) : MaxSize ( Maxsz ), CurrentSize (0) Vector = new Element MaxSize ; 構(gòu)造函數(shù)int length ( ) return CurrentSize; Element& operator

4、 ( int i ) return Vectori ; void swap ( Element & x, Element & y ) 交換 x, y Element temp = x; x = y; y = temp; void Sort ();排序靜態(tài)鏈表類的前視聲明靜態(tài)鏈表元素類的定義排序碼，其它信息略結(jié)點(diǎn)的鏈接指針靜態(tài)鏈表類定義template classstaticlinkList ;template classElement friend class staticlinkList ;private:Type key;int link;public:第9章排序Type getKey (

5、 ) return key; void setKey ( const Type x ) key = x; int getLink ( ) return link; void setLink ( const int ptr ) link = ptr ;靜態(tài)鏈表的類定義存儲(chǔ)待排序元素的向量向量中最大元素個(gè)數(shù)和當(dāng)前元素個(gè)數(shù) 【解答】直接插入排序 快速排序 堆排序(2)(8)希爾排序(增量為 直接選擇排序 二路歸并排序5,2,1)(3)起泡排序(6)錦標(biāo)賽排序(9)基數(shù)排序取當(dāng)前結(jié)點(diǎn)的排序碼將當(dāng)前結(jié)點(diǎn)的排序碼修改為x取當(dāng)前結(jié)點(diǎn)的鏈接指針將當(dāng)前結(jié)點(diǎn)的鏈接指針置為ptrtemplate classstat

6、iclinkList private:Element *Vector;int MaxSize, CurrentSize;public:dstaticlinkList ( int Maxsz = DefaultSize ) : MaxSize ( Maxsz ), CurrentSize (0) Vector = new Element Maxsz; 9-1什么是內(nèi)排序？什么是外排序？什么排序方法是穩(wěn)定的？什么排序方法是不穩(wěn)定的 ？ 【解答】?jī)?nèi)排序是排序過程中參與排序的數(shù)據(jù)全部在內(nèi)存中所做的排序，排序過程中無需進(jìn)行內(nèi)外存數(shù)據(jù)傳送，決定排序方法時(shí)間性能的主要是數(shù)據(jù)排序碼的比較次數(shù)和數(shù)據(jù)對(duì)象的移 動(dòng)

7、次數(shù)。外排序是在排序的過程中參與排序的數(shù)據(jù)太多，在內(nèi)存中容納不下，因此在排序過程中需要不斷進(jìn)行內(nèi)外存的信息傳送的排序。決定外排序時(shí)間性能的主要是讀寫磁盤次數(shù)和在內(nèi)存中總的記錄對(duì)象的歸并次數(shù)。不穩(wěn)定的排序方法主要有希爾排序、直接選擇排序、堆排序、快速排序。不穩(wěn)定的排序方法往往是按一定的間隔移動(dòng)或交換記錄對(duì)象的位置，從而可能導(dǎo)致具有相等排序碼的不同對(duì)象的前后相對(duì)位置在排序前后顛倒過來。其他排序方法中如果有數(shù)據(jù)交換，只是在相鄰的數(shù)據(jù)對(duì)象間比較排序碼， 如果發(fā)生逆序(與最終排序的順序相反的次序 )才交換，因此具有相 等排序碼的不同對(duì)象的前后相對(duì)位置在排序前后不會(huì)顛倒，是穩(wěn)定的排序方法。但如果把算法中判

8、斷逆序的比較 (或)”改寫成(或W)”，也可能造成不穩(wěn)定。9-2設(shè)待排序的排序碼序列為12, 2, 16, 30, 28, 10, 16*, 20, 6, 18 ),試分別寫出使用以下排序 方法每趟排序后的結(jié)果。并說明做了多少次排序碼比較。(1)直接插入排序23456789排序碼比較次數(shù)初始排列01i = 112 216302810*16206181、*i = 2212 1630281016206181i = 321216 | 302810*16206181i = 42121630 | 2810*16206182、*i = 5212162830 1016206185、*i = 62101216

9、2830 16206183*、i = 72101216162830 |206183*、i = 8210121616202830 6183、*、i = 92610121616202830 188*、261012161618202830 第9章排序(2)希爾排序(增量為5,2,1)初始排列排序碼比較次數(shù)4789+1+1) = 956012310216616*12182030281+1+3+1+3+1+1+1+2 = 142610121616*18202830希爾(shell)本人采取的增量序列為少/2/22/222，1。一般地，增量序列可米用Ja _, _n a jk _, _n a ，1。大量實(shí)

10、驗(yàn)表明，取 a =0.45454的增量序列比取其他的增量序列的優(yōu)越性更顯著。計(jì)算0.45454nJ的一個(gè)簡(jiǎn)單方法是用整數(shù)算術(shù)計(jì)算需要加以判斷和調(diào)整。(5*n-1)/11。需要注意，當(dāng)a| 16 5 | 30 28| 10 g| 16* 卜 | 20 仆|6 18 按最低位分配r0r1r2r3r4r5f0f1f2f3f4f5r6r7r8r96|*16181628+111f6f7f8f9收集 | 30 | 10 1 | 20 F | 12 | 2 i | 16 一 16* 6 )281 | 18 |按最高位分配r4r5r6r0r1r2r3f0f1f2f3f4f5f6r7r8r9收集 | 2 6 |

11、 * 10 * 121 16 * 16* 18 4 20 .28.亙9-3在起泡排序過程中，什么情況下排序碼會(huì)朝向與排序相反的方向移動(dòng)，試舉例說明。在快速排序過程中有這種現(xiàn)象嗎？【解答】如果在待排序序列的后面的若干排序碼比前面的排序碼小，則在起泡排序的過程中，排序碼可能向與最終它應(yīng)移向的位置相反的方向移動(dòng)。例如，第9章排序57. 40,38、 11.1334. 48,75 .6 19.9、765740 3811X 、X13 3448 7571996、7* 、 57 4038、 、11 13、X34 48 759、19679 5740、38 11、13 34 4875.19679 11、5740

12、 3813 19 34、4875679 1113、57 40、38. 19 344875679 111319 5740、38 . 344875679 1113、19 34、57 40 384875如9向相反方向移動(dòng)如19向相反方向移動(dòng)如9向最終方向移動(dòng)如13向相反方向移動(dòng)如13向最終方向移動(dòng)如34向相反方向移動(dòng)9-4試修改起泡排序算法， 在正反兩個(gè)方向交替進(jìn)行掃描，即第一趟把排序碼最大的對(duì)象放到序列的最后，第二趟把排序碼最小的對(duì)象放到序列的最前面。如此反復(fù)進(jìn)行?！窘獯?】template void dataList : shaker_ Sort ( ) /奇數(shù)趟對(duì)表Vector從前向后，比較相

13、鄰的排序碼，遇到逆序即交換，直到把參加比較排序碼序列中最大的排序碼移到序列尾部。偶數(shù)趟從后向前，比較相鄰的排序碼，遇到逆序即交換，直到把參加比較排序碼序列中最小的排序碼移到序列前端。int i = 1, j; int exchangewhile ( i = i; j -)if ( Vectorj -1 Vectorj ) Swap ( Vectorj-1, Vectorj); exchange = 1;if ( exchange = 0 ) break;for ( j = i; j Vectorj+1 ) Swap ( Vectorj, Vectorj+1); exchange = 1;if

14、( exchange = 0 ) break;起泡排序趟數(shù)不超過 n-1假定元素未交換逆向起泡發(fā)生逆序交換，最小排序碼放在 Vectori-1處做“發(fā)生了交換”標(biāo)志當(dāng)exchange為0則停止排序正向起泡發(fā)生逆序交換，最大排序碼放在 Vectorn-i處做“發(fā)生了交換”標(biāo)志當(dāng)exchange為0則停止排序int low = 1, high = CurrentSize -1, i, j;while ( low high ) j = low;for ( i = low ; i Vectori+1 ) Swap ( Vectori, Vectori+1); j = i; high = j;i+;【解

15、答2】template void dataList : shaker_ Sort ( ) int exchange;當(dāng)比較范圍多于一個(gè)對(duì)象時(shí)排序記憶元素交換位置正向起泡發(fā)生逆序交換記憶右邊最后發(fā)生交換的位置j比較范圍上界縮小到j(luò)第9章排序反向起泡發(fā)生逆序交換記憶左邊最后發(fā)生交換的位置 j比較范圍下界縮小到j(luò)for ( i = high ; i low ; i-)if ( Vectori -1 Vectori ) Swap ( Vectori-1, Vectori);j = i ；)low = j;)9-5如果待排序的排序碼序列已經(jīng)按非遞減次序有序排列，試證明函數(shù)QuickSort()的計(jì)算時(shí)間

16、將下降到O(n2)?！咀C明】若待排序的n個(gè)對(duì)象的序列已經(jīng)按排序碼非遞減次序有序排列，且設(shè)排序的時(shí)間代價(jià)為T(n)。當(dāng)以第一個(gè)對(duì)象作為基準(zhǔn)對(duì)象時(shí)，應(yīng)用一次劃分算法Partition ,通過n-1次排序碼比較，把只能把整個(gè)序列劃分為： 基準(zhǔn)對(duì)象的左子序列為空序列， 右子序列為有n-1個(gè)對(duì)象的 非遞減有序序列。對(duì)于這樣的遞歸 QuickSort()算法，其時(shí)間代價(jià)為T(n) = (n-1) + T(n-1)=(n-1) + ( n -2) + T(n-2) =(n-1) + (n-2) + (n-3) + T(n - 3) =,=(n-1) + (n-2) + (n-3) + , + 2 + T(1

17、) =(n-1) + (n-2) + (n-3) + , + 2 + 1=n(n-1)/2 = O(n 2)9- 6在實(shí)現(xiàn)快速排序的非遞歸算法時(shí)，可根據(jù)基準(zhǔn)對(duì)象，將待排序排序碼序列劃分為兩個(gè)子序列。若下一趟首先對(duì)較短的子序列進(jìn)行排序，試證明在此做法下，快速排序所需要的棧的深度為O(log 2n)o【解答】由快速排序的算法可知，所需遞歸工作棧的深度取決于所需劃分的最大次數(shù)。如果在排 序過程中每次劃分都能把整個(gè)待排序序列根據(jù)基準(zhǔn)對(duì)象劃分為左、右兩個(gè)子序列。假定這兩個(gè)子序列的長(zhǎng)度相等，則所需棧的深度為S(n) = 1 + S(n/2)=1 + 1 + S(n/4) = 2 + S(n/4)=2 +

18、1 + S(n/8) = 3 + S(n/8)=,=log 2n + S(1) = log 2n(假設(shè)1個(gè)對(duì)象的序列所用遞歸棧的深度為0)如果每次遞歸左、右子序列的長(zhǎng)度不等，并且先將較長(zhǎng)的子序列的左、右端點(diǎn)保存在遞歸棧中，再對(duì)較短的子序列進(jìn)行排序，可用表示最壞情況的大O表示法表示。此時(shí)其遞歸棧的深度不一定正好是log 2n,其最壞情況為 O(log2n)。9-7在實(shí)現(xiàn)快速排序算法時(shí)，可先檢查位于兩端及中點(diǎn)的排序碼，取三者之中的數(shù)值不是最大也不是最小的排序碼作為基準(zhǔn)對(duì)象。試編寫基于這種思想的快速排序算法，并證明對(duì)于已排序的排序碼序列，該算法的計(jì)算時(shí)間為O(nlog2n)?！窘獯稹繀⒖唇炭茣?-8

19、在使用非遞歸方法實(shí)現(xiàn)快速排序時(shí)，通常要利用一個(gè)棧記憶待排序區(qū)間的兩個(gè)端點(diǎn)。那 么能否用隊(duì)列來代替這個(gè)棧 ？為什么？【解答】可以用隊(duì)列來代替棧。在快速排序的過程中，通過一趟劃分，可以把一個(gè)待排序區(qū)間分 為兩個(gè)子區(qū)間，然后分別對(duì)這兩個(gè)子區(qū)間施行同樣的劃分。棧的作用是在處理一個(gè)子區(qū)間時(shí)，保存另一個(gè)子區(qū)間的上界和下界，待該區(qū)間處理完成后再從棧中取出另一子區(qū)間的邊界，對(duì)10第9章排序其進(jìn)行處理。這個(gè)功能利用隊(duì)列也可以實(shí)現(xiàn)，只不過是處理子區(qū)間的順序有所變動(dòng)而已。9-9試設(shè)計(jì)一個(gè)算法，使得在O(n)的時(shí)間內(nèi)重排數(shù)組，將所有取負(fù)值的排序碼排在所有取正 值(非負(fù)值)的排序碼之前。【解答】template voi

20、d reArrange ( dataList& L ) /數(shù)組元素類型Type只可能取int或floatint i = 0, j = L.length ()1;while ( i != j ) while ( Li.getKey( ) = 0 ) j -;swap ( Li, Lj);i+; j-;9-10奇偶交換排序是另一種交換排序。它的第一趟對(duì)序列中的所有奇數(shù)項(xiàng) i掃描，第二趟 對(duì)序列中的所有偶數(shù)項(xiàng)i掃描。若Ai Ai+1,則交換它們。第三趟有對(duì)所有的奇數(shù)項(xiàng)，第四趟對(duì)所有的偶數(shù)項(xiàng)，如此反復(fù)，直到整個(gè)序列全部排好序?yàn)橹埂?1)這種排序方法結(jié)束的條件是什么？(2)寫出奇偶交換排序的算法。(3)

21、當(dāng)待排序排序碼序列的初始排列是從小到大有序，或從大到小有序時(shí)，在奇偶交換 排序過程中的排序碼比較次數(shù)是多少？【解答】(1)設(shè)有一個(gè)布爾變量 exchanges,判斷在每一次做過一趟奇數(shù)項(xiàng)掃描和一趟偶數(shù)項(xiàng)掃描 后是否有過交換。若 exchange = 1,表示剛才有過交換，還需繼續(xù)做下一趟奇數(shù)項(xiàng)掃描和一 趟偶數(shù)項(xiàng)掃描；若 exchange = 0,表示剛才沒有交換，可以結(jié)束排序。(2)奇偶排序的算法template void dataList : odd-evenSort ( ) int i, exchange;do exchange = 0;掃描所有奇數(shù)項(xiàng)相鄰兩項(xiàng)比較，發(fā)生逆序作交換標(biāo)記交換掃

22、描所有偶數(shù)項(xiàng)相鄰兩項(xiàng)比較，發(fā)生逆序作交換標(biāo)記交換序列中各個(gè)對(duì)象的序號(hào)從 0開始。則當(dāng)所有for ( i = 1; i Vectori+1 ) exchange = 1;swap ( Vectori, Vectori+1);for ( i = 0; i Vectori+1 ) exchange = 1;swap ( Vectori, Vectori+1); while ( exchange != 0 );(3)設(shè)待排序?qū)ο笮蛄兄锌偣灿?n個(gè)對(duì)象。11第9章排序待排序?qū)ο笮蛄兄械膶?duì)象按排序碼從大到小初始排列時(shí)，執(zhí)行m = Jn+1)/2趟奇偶排序。當(dāng)所有待排序?qū)ο笮蛄兄械膶?duì)象按排序碼從小到大初始排

23、列時(shí)，執(zhí)行1趟奇偶排序。在一趟奇偶排序過程中，對(duì)所有奇數(shù)項(xiàng)掃描一遍，排序碼比較_(n-1)/2次；對(duì)所有偶數(shù)項(xiàng)掃描一遍，排序碼比較 _n/2次。所以每趟奇偶排序兩遍掃描的結(jié)果， 排序碼總比較次 數(shù)為 Jn-1)/2 _+1/2 _= n-1。9-11請(qǐng)編寫一個(gè)算法，在基于單鏈表表示的待排序排序碼序列上進(jìn)行簡(jiǎn)單選擇排序。【解答】采用靜態(tài)單鏈表作為存儲(chǔ)表示。用Vector0作為表頭結(jié)點(diǎn)，各待排序數(shù)據(jù)對(duì)象從 Vector1 開始存放。算法的思想是每趟在原始鏈表中摘下排序碼最大的結(jié)點(diǎn)(幾個(gè)排序碼相等時(shí)為最前面的結(jié)點(diǎn))，把它插入到結(jié)果鏈表的最前端。由于在原始鏈表中摘下的排序碼越來越小， 在結(jié)果鏈表前端插

24、入的排序碼也越來越小，最后形成的結(jié)果鏈表中的結(jié)點(diǎn)將按排序碼非遞減的順序有序鏈接。Template void staticlinkList : selectSort ( ) int h = Vector0.link, p, q, r, s ;Vector0.link = 0;while ( h != 0 ) p = s = h; q = r = 0;while ( p != 0 ) if ( Vectorp.data Vectors.data ) s = p;r = q; q = p; p = Vectorp.link ;if ( s = h ) h = Vectorh;else Vectorr

25、.link = Vectors.link ;Vectors.link = Vector0.link ;Vector0.link = s ;原始鏈表未掃描完掃描原始鏈表，尋找排序碼最大的結(jié)點(diǎn) s/記憶當(dāng)前找到的排序碼最大結(jié)點(diǎn)排序碼最大的結(jié)點(diǎn)是原始鏈表前端結(jié)點(diǎn)，摘下 排序碼最大的結(jié)點(diǎn)是原始鏈表表中結(jié)點(diǎn)，摘下 /結(jié)點(diǎn)s插入到結(jié)果鏈表的前端9-12若參加錦標(biāo)賽排序的排序碼有11個(gè)，為了完成排序，至少需要多少次排序碼比較？【解答】對(duì)于有n(n0)個(gè)數(shù)據(jù)的序列，錦標(biāo)賽排序選最小數(shù)據(jù)需進(jìn)行n-1次數(shù)據(jù)比較，以后每選一個(gè)數(shù)據(jù)，進(jìn)行數(shù)據(jù)比較的次數(shù)，均需og2n-1次(在外結(jié)點(diǎn)層無比較)。對(duì)于有11個(gè)排序碼的序列

26、，第一次選具最小排序碼的數(shù)據(jù)，需進(jìn)行 10次排序碼比較，以后在剩下的序 列中每選一個(gè)具最小排序碼的數(shù)據(jù)，都需進(jìn)行og211-1 = 2次排序碼比較，因此，為了完成排序，需要10 + 2*10 = 30次排序碼比較。n個(gè)參加排序的對(duì)9-13試給出適用于錦標(biāo)賽排序的勝者樹的類型聲明。并寫一個(gè)函數(shù)，對(duì)象，構(gòu)造勝者樹。設(shè) n是2的哥?！窘獯稹窟m用于錦標(biāo)賽排序的月4者樹的類型聲明.template classDataNode 勝者樹結(jié)點(diǎn)的類定義public:Type data;/ 數(shù)據(jù)值12第9章排序int index;int active;)樹中的結(jié)點(diǎn)號(hào)，即在完全二叉樹順序存儲(chǔ)中的下標(biāo)是否參選的標(biāo)志，

27、=1,參選；=0,不再參選template void TournamentSort ( Type a , int n ) 建立樹的順序存儲(chǔ)數(shù)組tree,將數(shù)組a中的元素復(fù)制到勝者樹中，對(duì)它們進(jìn)行排序，并把結(jié)果返送回?cái)?shù)組中，n是待排序元素個(gè)數(shù)。DataNode *tree;勝者樹結(jié)點(diǎn)數(shù)組DataNode item;int bottomRowSize = PowerOfTwo ( n );/計(jì)算滿足=n的2的最小次嘉的數(shù)：樹的底彳f大小n=7時(shí)它為8int TreeSize = 2 * bottomRowSize - 1;int loadindex = bottomRowSize - 1;tree

28、 = new DataNode TreeSize;int j = 0;for ( int i = loadindex; i TreeSize; i+ ) treei.index = i ;if ( j n ) treei.active = 1 ; treei.data elsetreei.active = 0 ;計(jì)算勝者樹的大小：內(nèi)結(jié)點(diǎn)+外結(jié)點(diǎn)數(shù)外結(jié)點(diǎn)開始位置動(dòng)態(tài)分配勝者樹結(jié)點(diǎn)數(shù)組空間/在數(shù)組a中取數(shù)據(jù)指針復(fù)制數(shù)組數(shù)據(jù)到樹的外結(jié)點(diǎn)中/下標(biāo)=aj+ ; 復(fù)制數(shù)據(jù)后面的結(jié)點(diǎn)為空的外結(jié)點(diǎn)i = loadindex ;/進(jìn)行初始比較尋找最小的項(xiàng)while ( i ) j = i;while ( j 2

29、*i ) 處理各對(duì)比賽者if ( !treej+1.active | treej.data = treej+1.data )tree(j -1)/2 = treej;勝者送入雙親elsetree(j -1)/2 = treej+1;j += 2;i = (i-1)/2;for ( i=0; in-1; i+) ai = tree0.data ;treetree0.index.active = 0 ;UpdateTree ( tree, tree0.index );下一對(duì)參加比較的項(xiàng)/i退到雙親，直到i=0為止處理其它n-1元素當(dāng)前最小元素送數(shù)組 a該元素相應(yīng)外結(jié)點(diǎn)不再比賽從該處向上修改an-1

30、 = tree0.data;template void UpdateTree ( DataNode *tree, int i ) 錦標(biāo)賽排序中的調(diào)整算法：i是表中當(dāng)前最小元素的下標(biāo)，即勝者。從它開始向上調(diào)整if ( i %2 = 0 ) tree(i -1)/2 = treei-1;/ i 為偶數(shù)，對(duì)手為左結(jié)點(diǎn)else tree(i -1)/2 = treei+1 ;/ i 為奇數(shù)，對(duì)手為右結(jié)點(diǎn)最小元素輸出之后，它的對(duì)手上升到父結(jié)點(diǎn)位置i = (i - 1) / 2;/ i上升到雙親結(jié)點(diǎn)位置while ( i ) if ( i %2 = 0) j = i - 1;elsej = i + 1 ;

31、if ( !treei.active | !treej.active )/確定i的對(duì)手是左結(jié)點(diǎn)還是右結(jié)點(diǎn)比賽對(duì)手中間有一個(gè)為空13第9章排序if ( treei.active ) tree(i -1)/2 = treei;elsetree(i -1)/2 = treej;非空者上升到雙親結(jié)點(diǎn)else比賽對(duì)手都不為空if ( treei.data treej.data ) tree(i -1)/2 = treei; elsetree(i -1)/2 = treej;勝者上升到雙親結(jié)點(diǎn)i = (i - 1) / 2;/ i上升到雙親結(jié)點(diǎn)) )9-14手工跟蹤對(duì)以下各序列進(jìn)行堆排序的過程。給出形成初

32、始堆及每選出一個(gè)排序碼后堆 的變化。(1)按字母順序排序：Tim, Dot, Eva, Rom, Kim, Guy, Ann, Jim, Kay, Ron, Jan(2)按數(shù)值遞增順序排序： 26, 33, 35, 29, 19, 12, 22(3)同樣7個(gè)數(shù)字，氏-個(gè)初始排列，再按數(shù)值的遞增順序排序：12, 19, 33, 26, 29, 35, 22【解答】為節(jié)省篇幅，將用數(shù)組方式給出形成初始堆和進(jìn)行堆排序的變化結(jié)果。陰影部分表, f- rJ，美二-山人t X4P it?, 丁丁7 、誹、+ TV -UA 口力產(chǎn)f 人 -山2t 用H /、+/ 一 t f t | 公_ 山2tttX 一一

33、 不考三 入牧口，刑廳的。師母后攸忠兀至一(1)按字母順序排序形成初始堆(按最大堆)一乂儲(chǔ)口”怏廳仔帕衣小由，比口沙網(wǎng)形衣小。012345678910TimDotEvaRomKimGuyAnnJimKayRonJani=4TimDotEvaRomRonGuyAnnJimKayKimJan i=3TimDotEvaRomRonGuyAnnJimKayKimJan i=2TimDotGuyRomRonEvaAnnJimKayKimJan i=1TimRonGuyRomKimEvaAnnJimKayDotJan i=0TimRonGuyRomKimEvaAnnJimKayDotJan 堆排序0123

34、45678910j=10Jan +RonGuyRomKimEvaAnnJimKayDot .Tim 交換RonRomGuyKayKimEvaAnnJimJanDot Tim調(diào)整j=9Dot .RomGuyKayKimEvaAnnJimJan*RonTim交換RomKimGuyKayDotEvaAnnJimJan RonTim調(diào)整j=8Jan KimGuyKayDotEvaAnnJim+ Rom RonTim交換KimKayGuyJimDotEvaAnnJan RomRonTim調(diào)整j=7Jan -KayGuyJimDotEvaAnn+ Kim RomRonTim交換KayJimGuyJanDo

35、tEvaAnn KimRomRonTim調(diào)整j=6Ann +JimGuyJanDotEva- Kay KimRomRonTim交換JimJanGuyAnnDotEva KayKimRomRonTim調(diào)整j=5Eva JanGuyAnnDot. Jim KayKimRomRonTim交換JanEvaGuyAnnDot JimKayKimRomRonTim調(diào)整j=4Dot .EvaGuyAnn.JanJimKayKimRomRonTim交換GuyEvaDotAnn JanJimKayKimRomRonTim調(diào)整j=3Ann .EvaDot.Guy JanJimKayKimRomRonTim交換Ev

36、aAnnDot GuyJanJimKayKimRomRonTim調(diào)整j=2Dot -Annva GuyJanJimKayKimRomRonTim交換14第9章排序DotAnn EvaGuyJanJimKayKimRomRonTim調(diào)整j=1DotAnn EvaGuyJanJimKayKimRomRonTim交換Ann DotEvaGuyJanJimKayKimRomRonTim調(diào)整(2)按數(shù)值遞增順序排序 形成初始堆(按最大堆)012263335i=2263335i=0263335i=1353326345629191222291912|22 29191222 291912|22 堆排序0123

37、456j=6 22 .332629191235 交換332926221912 35 調(diào)整為堆j=5 12 .29262219.33 35 交換2922261219 3335 調(diào)整為堆j=4 19 _222612,29 3335 交換26221912 293335 調(diào)整為堆j=3 12 .2226 293335 交換221219 26293335 調(diào)整為堆j=2 191222 26293335 交換*-19122226293335 調(diào)整為堆j=1 1219 2226293335 交換12 192226293335 調(diào)整為堆(3)同樣7個(gè)數(shù)字，換一個(gè)初始排列，再按數(shù)值的遞增順序排序 形成初始堆(按

38、最大堆)012345612193326293522i=212193526293322 i=012293526193322 i=135293326191222 堆排序0123456j=622 .2933261912 ,u 35 交換332922261912 35調(diào)整為堆j=512 .29222619 33 35交換2926221219 3335調(diào)整為堆j=419 .262212一 29 3335交換26192212 293335調(diào)整為堆j=312 192226 293335交換15第9章排序221912 26293335調(diào)整為堆j=2121922 26293335交換1912 222629333

39、5調(diào)整為堆j=11219 2226293335交換12 192226293335調(diào)整為堆9-15如果只想在一個(gè)有 n個(gè)元素的任意序列中得到其中最小的第k (kn)個(gè)元素之前的部分排序序列,那么最好采用什么排序方法？為什么？例如有這樣一個(gè)序列：503, 017, 512, 908, 170, 897, 275, 653, 612, 154, 509, 612*, 677, 765, 094 ,要得到其第 4 個(gè)元素之前的部分 有序序列：017, 094, 154, 170 ,用所選擇的算法實(shí)現(xiàn)時(shí)，要執(zhí)行多少次比較？【解答】一般來講，當(dāng)n比較大且要選的數(shù)據(jù)k 0)個(gè)數(shù)據(jù)的序列，選最小數(shù)據(jù)需進(jìn)行 n

40、-1次數(shù)據(jù) 比較，以后每選一個(gè)數(shù)據(jù)，進(jìn)行數(shù)據(jù)比較的次數(shù)，均需og2n-1次。例如，同樣12個(gè)數(shù)據(jù)，第一次選最小的數(shù)據(jù) 6,需進(jìn)行11次數(shù)據(jù)比較，以后選 7、9、11時(shí)，都是 og212-1 =2次數(shù)據(jù)比較。9-16希爾排序、簡(jiǎn)單選擇排序、快速排序和堆排序是不穩(wěn)定的排序方法，試舉例說明。【解答】希爾排序 512 275* 061275061275*275*512275061 275 512 21(2)直接選擇排序 275275*512061 i = 1 061275*512275 i = 2 061275*512275 i = 3 061275*275512 快速排序 512275275* 27

41、5*275512 堆排序 275275*061170 已經(jīng)是最大堆，交換 275與170 170275*061275對(duì)前3個(gè)調(diào)整 275*170061275 前3個(gè)最大堆，交換 275*與061 061170275*275 對(duì)前2個(gè)調(diào)整 170061275*275 前2個(gè)最大堆，交換 170與061 061170275*275 16第9章排序9-17設(shè)有n個(gè)待排序元素存放在一個(gè)不帶表頭結(jié)點(diǎn)的單鏈表中，每個(gè)鏈表結(jié)點(diǎn)只存放一個(gè)元素，頭指針為r。試設(shè)計(jì)一個(gè)算法，對(duì)其進(jìn)行二路歸并排序，要求不移動(dòng)結(jié)點(diǎn)中的元素，只 改各鏈結(jié)點(diǎn)中的指針，排序后r仍指示結(jié)果鏈表的第一個(gè)結(jié)點(diǎn)。(提示：先對(duì)待排序的單鏈表進(jìn)行一次

42、掃描，將它劃分為若干有序的子鏈表，其表頭指針存放在一個(gè)指針隊(duì)列中。當(dāng)隊(duì)列不空時(shí)重復(fù)執(zhí)行，從隊(duì)列中退出兩個(gè)有序子鏈表，對(duì)它們進(jìn)行二路歸并，結(jié)果鏈表的表頭 指針存放到隊(duì)列中。如果隊(duì)列中退出一個(gè)有序子鏈表后變成空隊(duì)列，則算法結(jié)束。這個(gè)有序子鏈表即為所求。)【解答】(1)兩路歸并算法 template void staticlinkList : merge ( int ha; int hb; int& hc ) /合并兩個(gè)以ha和hb為表頭指針的有序鏈表，結(jié)果鏈表的表頭由hc返回int pa, pb, pc; if ( Vectorha.data = Vectorhb.data )確定結(jié)果鏈的表頭 h

43、c = ha; pa = Vectorha.link; pb = hb;else hc = hb; pb = Vectorhb.link ; pa = ha; pc = hc;結(jié)果鏈的鏈尾指針while ( pa != 0 ) and ( pb != 0 )兩兩比較，小者進(jìn)結(jié)果鏈if (Vectorpa.data = Vectorpb.data ) Vectorpc.link = pa ; pc = pa; pa = Vectorpa.link ; else Vectorpc.link = pb ; pc = pb; pb = Vectorpb.link ;if ( pa != 0 ) Vec

44、torpc.link = pa ;/ pb 鏈處理完，pa 鏈鏈入結(jié)果鏈else Vectorpc.link = pb ;/ pa鏈處理完，pb鏈鏈入結(jié)果鏈(2)歸并排序主程序template void staticlinkList : merge_sort ( ) int r, s, t; Queue Q;if ( Vector0.link = 0 ) return;s = Vector0.link ; Q.Enqueue( s );/鏈表第一個(gè)結(jié)點(diǎn)進(jìn)隊(duì)列 while ( 1 ) t = Vectors.link ;結(jié)點(diǎn)t是結(jié)點(diǎn)s的下一個(gè)鏈中結(jié)點(diǎn)while ( t != 0 & Vector

45、s.data = Vectort.data ) s = t; t = Vectort.link ; Vectors.link = 0 ; s = t;if (t != 0 ) Q.EnQueue( s );else break;while ( ! Q.IsEmpty() ) r = Q.getFront( ); Q.DlQueue();if ( Q.IsEmpty( ) ) break;s = Q.getFront( ); Q.DlQueue(); merge( r, s, t ); Q.EnQueue( t );Vector0.link = r ;/在鏈表中尋找一段有序鏈表存在一段有序鏈表，

46、截取下來進(jìn)隊(duì)列到鏈尾從隊(duì)列退出一個(gè)有序鏈表的表頭 r隊(duì)列空，表示排序處理完成，退出從隊(duì)列再退出一個(gè)有序鏈表的表頭 s歸并兩個(gè)有序鏈表后結(jié)果鏈表進(jìn)隊(duì)列17第9章排序9-18若設(shè)待排序排序碼序列有n個(gè)排序碼，n是一個(gè)完全平方數(shù)。將它們劃分為K塊，每塊有 戶個(gè)排序碼。這些塊分屬于兩個(gè)有序表。下面給出一種0(1)空間的非遞歸歸并算法：stepl:在兩個(gè)待歸并的有序表中從右向左總共選出而個(gè)具有最大值的排序碼；step2:若設(shè)在stepl選出白第2個(gè)有序表中的排序碼有s個(gè)，則從第1個(gè)有序表選出的排序碼有 新- s個(gè)。將第2個(gè)有序表選出的s個(gè)排序碼與第1個(gè)有序表選出的排序碼左邊的 同樣數(shù)目的排序碼對(duì)調(diào)；st

47、ep3:交換具有最大、，不個(gè)排序碼的塊與最左塊(除非最左塊就是具有最大而個(gè)排序碼 的塊)。對(duì)最右塊進(jìn)行排序；step4:除去具有最大 J7個(gè)排序碼的塊以外，對(duì)其它的塊根據(jù)其最后的排序碼按非遞減 順序排序；step5:設(shè)置3個(gè)指針，分別位于第1塊、第2塊和第3塊的起始位置，執(zhí)行多次substep, 直到3個(gè)指針都走到第 疝塊為止。此時(shí)前塊已經(jīng)排好序。subStep所做的工作是比較第 2個(gè)指針與第3個(gè)指針?biāo)概判虼a，將值小的與第1個(gè)指針?biāo)概判虼a對(duì)調(diào)，相應(yīng)指針前進(jìn)1個(gè)排序碼位置。step6:對(duì)最后第 1塊中最大的 而個(gè)排序碼進(jìn)行排序。(1)設(shè)有16個(gè)排序碼，分別存放于兩個(gè)有序表 10, 12, 1

48、4, 16, 18, 20, 22, 25和11, 13, 15, 17,19, 21,23, 24中，試根據(jù)上面的描述，寫出排序的全過程，并說明它具有時(shí)間復(fù)雜度 0(n) 和空間復(fù)雜度0(1)。(2)編寫相應(yīng)的算法。要求兩個(gè)待排序有序表的長(zhǎng)度可以不同，但每一個(gè)表的長(zhǎng)度都是 R的倍數(shù)。(3)假設(shè)兩個(gè)有序表分別為(X1, , , Xm)和(Xm+1, , , Xn),編寫一個(gè)算法歸并這兩個(gè)有序 表，得到(X1, , , Xn)。設(shè)S=而。9-19試編寫一個(gè)算法，將對(duì)象序列(X1, X2, , , Xn)循環(huán)右移p個(gè)位置，0 p n。要求該算法 的時(shí)間復(fù)雜度為 O(n)而空間復(fù)雜度為O(1)?！窘?/p>

49、答】略9-20在什么條件下，MSD基數(shù)排序比LSD基數(shù)排序效率更高？【解答】由于高位優(yōu)先的 MSD方法是遞歸的方法，就一般情況來說，不像低位優(yōu)先的LSD方法那樣直觀自然，而且實(shí)現(xiàn)的效率較低。但如果待排序的排序碼的大小只取決于高位的少 數(shù)幾位而與大多數(shù)低位無關(guān)時(shí)，采用 MSD方法比LSD方法的效率要高。9-21在已排好序的序列中，一個(gè)對(duì)象所處的位置取決于具有更小排序碼的對(duì)象的個(gè)數(shù)?；?于這個(gè)思想，可得計(jì)數(shù)排序方法。該方法在聲明對(duì)象時(shí)為每個(gè)對(duì)象增加一個(gè)計(jì)數(shù)域count,用于存放在已排好序的序列中該對(duì)象前面的對(duì)象數(shù)目，最后依count域的值，將序列重新排列，就可完成排序。試編寫一個(gè)算法，實(shí)現(xiàn)計(jì)數(shù)排序

50、。并說明對(duì)于一個(gè)有n個(gè)對(duì)象的序列，35661428為確定所有對(duì)象的 count值，最多需要做n(n-1)/2次排序碼比較。 【解答】存放結(jié)果的表180000初始狀態(tài)2100第1趟排序結(jié)果300第2趟排序結(jié)果01第3趟排序結(jié)果35661428待排序的表第9章排序template void datalist : count_sort ( ) IIinitList是待排序表，resultList是結(jié)果表II c是存放計(jì)數(shù)排序結(jié)果的臨時(shí)表 初始化，計(jì)數(shù)值都為0int i,j;int *c = new datalist ;for ( i = 0; i CurrentSize; i+ ) Vectori.

51、count = 0 ;for ( i = 0; i CurrentSize -1; i+ )for (j = i+1 ; j CurrentSize ; j+ )if ( Vectorj.key Vector中各就各位結(jié)果復(fù)制回當(dāng)前表對(duì)象中else Vectorj.count+ ;統(tǒng)計(jì)for ( i = 0; i Vector Vectori.count = Vectori;for ( i = 0; i Vectori;delete c;)9-22試證明對(duì)一個(gè)有n個(gè)對(duì)象的序列進(jìn)行基于比較白排序，最少需要執(zhí)行nlog2n次排序碼比較?！窘獯稹炕诒容^的排序方法中，采用分治法進(jìn)行排序是平均性能最好

52、的方法。方法描述如下： Sort ( List ) if ( List的長(zhǎng)度大于1) 將序列List劃分為兩個(gè)子序列 LeftList和Right List ;Sort ( LeftList ) ; Sort ( RightList );分別對(duì)兩個(gè)子序列施行排序?qū)蓚€(gè)子序列 LeftList和RightList合并為一個(gè)序列 List;) )典型的例子就是快速排序和歸并排序。若設(shè) T(n)是對(duì)n個(gè)對(duì)象的序列進(jìn)行排序所需的 時(shí)間，而且把序列劃分為長(zhǎng)度相等的兩個(gè)子序列后，對(duì)每個(gè)子序列進(jìn)行排序所需的時(shí)間為 T(n/2),最后合并兩個(gè)已排好序的子序列所需時(shí)間為cn (c是一個(gè)常數(shù))。此時(shí)，總的計(jì)算時(shí)間

53、為：T(n) cn + 2 T(n/2 )/ c 是一個(gè)常數(shù)& cn + 2 ( cn/2 + 2T(n/4) ) = 2cn + 4T(n/4)0 2cn + 4 ( cn/4 +2T(n/8) ) = 3cn + 8T(n/8)，80o由此解得k3,即應(yīng)取的歸并路數(shù)至少為 3。(2)設(shè)多路歸并的歸并路數(shù)為 k,需要k個(gè)輸入緩沖區(qū)和1個(gè)輸出緩沖區(qū)。1個(gè)緩沖區(qū) 對(duì)應(yīng)1個(gè)文件，有k +1 = 15,因此k = 14,可做14路歸并。由S = logkm| = iog1480l = 2。 即至少需2趟歸并可完成排序。19第9章排序若限定這個(gè)趟數(shù)，由 S = 1ogk80l = 2,有80Wk2,可

54、取的最低路數(shù)為 9。即要在2趟內(nèi) 完成排序，進(jìn)行9路排序即可。9-24假設(shè)文件有4500個(gè)記錄，在磁盤上每個(gè)頁塊可放75個(gè)記錄。計(jì)算機(jī)中用于排序的內(nèi)存區(qū)可容納450個(gè)記錄。試問：(1)可建立多少個(gè)初始?xì)w并段？每個(gè)初始?xì)w并段有多少記錄？存放于多少個(gè)頁塊中？(2)應(yīng)采用幾路歸并？請(qǐng)寫出歸并過程及每趟需要讀寫磁盤的頁塊數(shù)?！窘獯稹?1)文件有4500個(gè)記錄，計(jì)算機(jī)中用于排序的內(nèi)存區(qū)可容納450個(gè)記錄，可建立的初始?xì)w并段有4500 / 450 = 10個(gè)。每個(gè)初始?xì)w并段中有450個(gè)記錄，存于450/ 75 = 6個(gè)頁塊中。(2)內(nèi)存區(qū)可容納6個(gè)頁塊，可建立 6個(gè)緩沖區(qū)，其中5個(gè)緩沖區(qū)用于輸入，1個(gè)緩沖

55、 區(qū)用于輸出，因此，可采用5路歸并。歸并過程如下：45045045045045045045045045045022509-25 設(shè)初始?xì)w并段為(10, 15, 31,8),(9, 20, ), (22, 34, 37,8)，(6, 15, 42, ), (12, 37,8),(84,95,叼,試?yán)脭≌邩溥M(jìn)行k路歸并，手工執(zhí)彳T選擇最小的5個(gè)排序碼的過程?！窘獯稹孔?路歸并排序，選擇最小的5個(gè)排序碼的敗者樹如下圖所示。37遞補(bǔ)42遞補(bǔ)2022504500共做了 2趟歸并，每趟需要讀 60個(gè)磁盤頁塊，寫出 60個(gè)磁盤頁塊。第9章排序9-26 設(shè)輸入文件包含以下記錄：14, 22, 7, 24,

56、15, 16, 11, 100, 10, 9, 20, 12, 90, 17, 13, 19, 26,38, 30, 25, 50, 28, 110, 21,40?，F(xiàn)采用置換-選擇方法生成初始?xì)w并段，并假設(shè)內(nèi)存工作區(qū)可同時(shí)容納5個(gè)記錄，請(qǐng)畫出選擇的過程?！窘獯稹吭O(shè)內(nèi)存工作區(qū)在某一時(shí)刻可以處理6個(gè)記錄，利用敗者樹生成初始?xì)w并段的過程如下。輸入文件InFile內(nèi)存工作區(qū)輸出文件OutFile動(dòng)作14, 22, 07, 24, 15, 16, 11, 100, 10, 09,20, 12, 90, 17, 13, 19, 26, 38, 30, 25,50, 28, 110, 21,40輸入6個(gè)記錄

57、11, 100, 10, 09, 20, 12, 90, 17, 13, 19,26, 38, 30, 25, 50, 28, 110, 21,4014, 22,回, 24, 15, 16選擇07,輸出07, 門檻07,置換11100, 10, 09, 20, 12, 90, 17, 13, 19, 26,38, 30, 25, 50, 28, 110, 21,4014, 22,回24, 15, 1607選擇11,輸出11,門檻11,置換10010, 09, 20, 12, 90, 17, 13, 19, 26, 38,30, 25, 50, 28, 110, 21,40回 22, 100,

58、24, 15, 1607, 100選擇14,輸出14, 門檻14,置換1009, 20, 12, 90, 17, 13, 19, 26, 38, 30,25, 50, 28, 110, 21,4010, 22, 100,24, 15, 1607, 100, 14選擇15,輸出15, 門檻15,置換0920, 12, 90, 17, 13, 19, 26, 38, 30, 25,50, 28, 110, 21,4010, 22, 100,24, 09, 1607, 100, 14, 15選擇16,輸出16, 門檻16,置換2012, 90, 17, 13, 19, 26, 38, 30, 25,

59、 50,28, 110, 21,4010, 22, 100,24, 09,國07, 100, 14, 15, 16選擇20,輸出20, 門檻20,置換1290, 17, 13, 19, 26, 38, 30, 25, 50, 28,110, 21,4010, 22, 100,24, 09, 1207, 100, 14, 15, 16, 20選擇22,輸出22, 門檻22,置換9017, 13, 19, 26, 38, 30, 25, 50, 28, 110,21,4010, 90, 100, |24|, 09, 1207, 100, 14, 15, 16, 20, 22選擇24,輸出24, 門

60、檻24,置換1713, 19, 26, 38, 30, 25, 50, 28, 110, 21,4010, 90, 100,17, 09, 1207, 100, 14, 15, 16, 20, 22,24選擇90,輸出90, 門檻90,置換1319, 26, 38, 30, 25, 50, 28, 110, 21,4010, 13,畫17, 09, 1207, 100, 14, 15, 16, 20, 22,24, 90選擇100,輸出100, 門檻100,置換1926, 38, 30, 25, 50, 28, 110, 21,4010, 13, 19,17, 09, 1207, 100, 1