靜態(tài)數(shù)據(jù)表類定義

1、第9章 排序靜態(tài)數(shù)據(jù)表類定義#include <iostream.h>const int DefaultSize = 100;template <class Type> class dataList/數(shù)據(jù)表的前視聲明 template <class Type> class Element /數(shù)據(jù)表元素類的定義friend class dataList <Type>private: Type key;/排序碼 field otherdata;/其它數(shù)據(jù)成員public: Type getKey ( ) return key; /取當(dāng)前結(jié)點(diǎn)的排序碼

2、void setKey ( const Type x ) key = x; /將當(dāng)前結(jié)點(diǎn)的排序碼修改為x Element<Type>& operator = ( Element<Type>& x )/結(jié)點(diǎn)x的值賦給this key = x->key; otherdata = x->otherdata; int operator = ( Type& x ) return key = x->key; /判this與x相等 int operator <= ( Type& x ) return key <= x-&g

3、t;key; /判this小于或等于x int operator > ( Type& x ) return key > x->key; /判this大于x int operator < ( Type& x ) return key > x->key; /判this小于x template <class Type> class dataList /用順序表來存儲(chǔ)待排序的元素，這些元素的類型是Typeprivate: Element <Type> * Vector;/存儲(chǔ)待排序元素的向量 int MaxSize, Curr

4、entSize; /最大元素個(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 <Type> MaxSize; /構(gòu)造函數(shù) int length ( ) return CurrentSize; Element<Type>& operator ( int i ) retur

5、n Vectori; void swap ( Element <Type>& x, Element <Type>& y )/交換x, y Element <Type> temp = x; x = y; y = temp; void Sort ( );/排序靜態(tài)鏈表類定義template <class Type> class staticlinkList;/靜態(tài)鏈表類的前視聲明 template <class Type> class Element /靜態(tài)鏈表元素類的定義friend class staticlinkLi

6、st<Type>private: Type key;/排序碼，其它信息略 int link;/結(jié)點(diǎn)的鏈接指針public: Type getKey ( ) return key; /取當(dāng)前結(jié)點(diǎn)的排序碼 void setKey ( const Type x ) key = x; /將當(dāng)前結(jié)點(diǎn)的排序碼修改為x int getLink ( ) return link; /取當(dāng)前結(jié)點(diǎn)的鏈接指針 void setLink ( const int ptr ) link = ptr; /將當(dāng)前結(jié)點(diǎn)的鏈接指針置為ptrtemplate <class Type> class static

7、linkList /靜態(tài)鏈表的類定義private: Element <Type> *Vector;/存儲(chǔ)待排序元素的向量 int MaxSize, CurrentSize;/向量中最大元素個(gè)數(shù)和當(dāng)前元素個(gè)數(shù)public: dstaticlinkList ( int Maxsz = DefaultSize ) : MaxSize ( Maxsz ), CurrentSize (0) Vector = new Element <Type> Maxsz; 9-1 什么是內(nèi)排序? 什么是外排序? 什么排序方法是穩(wěn)定的? 什么排序方法是不穩(wěn)定的? 【解答】內(nèi)排序是排序過程中參與

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

9、排序的順序相反的次序)才交換，因此具有相等排序碼的不同對象的前后相對位置在排序前后不會(huì)顛倒，是穩(wěn)定的排序方法。但如果把算法中判斷逆序的比較“>(或<)”改寫成“(或)”，也可能造成不穩(wěn)定。9-2 設(shè)待排序的排序碼序列為12, 2, 16, 30, 28, 10, 16*, 20, 6, 18, 試分別寫出使用以下排序方法每趟排序后的結(jié)果。并說明做了多少次排序碼比較。(1) 直接插入排序(2) 希爾排序(增量為5,2,1)(3) 起泡排序(4) 快速排序(5) 直接選擇排序(6) 錦標(biāo)賽排序(7) 堆排序(8) 二路歸并排序(9) 基數(shù)排序【解答】(1) 直接插入排序 初始排列 0

10、1 2 3 4 5 6 7 8 9 排序碼比較次數(shù) i = 1 12 21630281016*20 618 1 i = 2 212 1630281016*20 618 1 i = 3 212 16 30281016*20 618 1 i = 4 212 16 30 281016*20 618 2 i = 5 212 16 2830 1016*20 618 5 i = 6 21012162830 16*20 618 3 i = 7 210121616*2830 20 618 3 i = 8 210121616*202830 618 3 i = 9 2 610121616*202830 18 8

11、2 610121616*18202830 (2) 希爾排序(增量為5,2,1)初始排列 0 1 2 3 4 5 6 7 8 9排序碼比較次數(shù) 12 21630281016*20 618 1+1+1+1+1 = 5 d = 5 10 216 6181216*203028 (1+1+2+1) + (1+1 d = 2+1+1) = 9 10 216 616*1218203028 1+1+3+1+3+1+1 d = 1+1+2 = 14 2 6 10 121616*18202830 希爾(shell)本人采取的增量序列為 ën/2û, ëën/2û/

12、2û, ëën/2û/2û/2û, ,1。一般地，增量序列可采用ënû, ëënûû, ëënûûû, , 1。大量實(shí)驗(yàn)表明，取=0.45454的增量序列比取其他的增量序列的優(yōu)越性更顯著。計(jì)算 ë0.45454nû 的一個(gè)簡單方法是用整數(shù)算術(shù)計(jì)算(5*n-1)/11。需要注意，當(dāng)a< 1/2時(shí)，增量序列可能不以1結(jié)束，需要加以判斷和調(diào)整。(3) 起泡排序初始排列 0 1 2 3 4 5 6 7 8 9

13、 排序碼比較次數(shù) i = 0 12 21630281016*20 618 9 i = 1 2 12 61630281016*2018 8 i = 2 2 6 121016302816*1820 7 i = 3 2 6 10 121616*30281820 6 i = 4 2 6 10 12 1616*18302820 5 i = 5 2 6 10 1216 16*18203028 4 i = 6 2 6 10 121616* 18202830 3 2 6 10 121616*18202830 (4) 快速排序PivotPvtpos 0 1 2 3 4 5 6 7 8 9 排序碼比較次數(shù)posp

14、ospospos 120,1,2,3 12 2 1630281016*20 618 9pospos 60,1 6 2 10 12 281616*203018 2pospospospospos 284,5,6,7,8 2 6 10 12 281616*203018 5pospospos 18 4,5,6 2 6 10 12 181616*20 28 30 3pos 16*4 2 6 10 12 16*16 18 20 2830 1 2 6 10 1216* 16 18202830 左子序列遞歸深度為1，右子序列遞歸深度為3。(5) 直接選擇排序初始排列 0 1 2 3 4 5 6 7 8 9 排

15、序碼比較次數(shù) i = 0 12 2 16 30 28 10 16* 20 618 9 i = 1 2 12 16 30 28 10 16* 20 618 8 i = 2 2 6 16 30 28 10 16* 20 1218 7 i = 3 2 6 10 30 28 16 16* 20 1218 6 i = 4 2 6 10 12 28 16 16* 20 3018 5 i = 5 2 6 10 12 16 28 16* 20 3018 4 i = 6 2 6 10 12 16 16* 28 20 3018 3 i = 7 2 6 10 12 16 16* 18 20 3028 2 i = 8

16、 2 6 10 12 16 16* 16 20 3028 1 2 6 10 12 16 16* 16 20 28 30 (6) 錦標(biāo)賽排序輸出2，調(diào)整勝者樹262106216*1016621862016*10281630212當(dāng)參加排序的數(shù)據(jù)對象個(gè)數(shù)n不足2的某次冪時(shí)，將其補(bǔ)足到2的某次冪。本題的n = 10，將葉結(jié)點(diǎn)個(gè)數(shù)補(bǔ)足到24 = 16個(gè)。排序碼比較次數(shù) = 9。輸出6，調(diào)整勝者樹661010612616*1016121862016*1028301621210輸出10，調(diào)整勝者樹排序碼比較 次數(shù) = 1。1010181812101816*1612121862016*102830162當(dāng)某

17、結(jié)點(diǎn)的比較對手的參選標(biāo)志為“不再參選”，該結(jié)點(diǎn)自動(dòng)升入雙親結(jié)點(diǎn)，此動(dòng)作不計(jì)入排序碼比較次數(shù)。12輸出12，調(diào)整勝者樹排序碼比較 次數(shù) = 3。181216*181216*281618121862016*10283016212排序碼比較次數(shù)=3。某對象輸出后，對手自動(dòng)升到雙親，不計(jì)入排序碼比較次數(shù)。輸出16，調(diào)整勝者樹16排序碼比較 次數(shù) = 2。1618161816*2816181216*62016*102830162121816*輸出16*，調(diào)整勝者樹16*18排序碼比較 次數(shù) = 2。16*30181816*12302862016*102830162121818輸出18，調(diào)整勝者樹排序碼比

18、較 次數(shù) = 3。20182030182030181228182016*1028301621262020排序碼比較 次數(shù) = 0。2018302018123018輸出20，調(diào)整勝者樹2862016*102830162121828輸出28，調(diào)整勝者樹28排序碼比較 次數(shù) = 2。18281830202830181220616*102830162121830輸出30，排序完成30排序碼比較 次數(shù) = 0。182818302018283012182016*102830162126(7) 堆排序第一步，形成初始的最大堆 (略)，第二步，做堆排序。 630121628162816216*18201018

19、16*102016*10283030122212618620 初始排列，不是最大堆 形成初始最大堆 交換0# 與9# 對象2028281816201616206101216*181816*1210101216*3028263023062 從0# 到8# 重新形成堆 交換0# 與8# 對象 從0# 到 7# 重新形成堆 16*28282121616121618182216*101066121016*61830203020282030 交換0# 與7# 對象 從0# 到6# 重新形成堆 交換0# 與6# 對象1616*1010121612121661816*216*1818626210302820

20、282030282030 從0# 到5# 重新形成堆 交換0# 與5# 對象 從0# 到4# 重新形成堆 2 126610610101212181616*1616*1821618216*282030282030283020 交換0# 與4# 對象 從0# 到3# 重新形成堆 交換0# 與3# 對象 6 2 101026102618161216*16*121618121816*16282030282030302820 從0# 到2# 重新形成堆 交換0# 與2# 對象 從0# 到1# 重新形成堆 2 261010616*16121818161216*282030302028 交換0# 與1# 對

21、象 從0# 到1# 重新形成堆，得到結(jié)果 (8) 二路歸并排序采用迭代的方法進(jìn)行歸并排序。設(shè)待排序的數(shù)據(jù)對象有n個(gè)。首先把每一個(gè)待排序的數(shù)據(jù)對象看作是長度為的初始?xì)w并項(xiàng)，然后進(jìn)行兩兩歸并，形成長度為2的歸并項(xiàng)，再對它們兩兩歸并，形成長度為4的歸并項(xiàng)，如此一趟一趟做下去，最后得到長度為n的歸并結(jié)果。排序碼比較5次182016*2163028106126 1816* 20 1210 2816 302 12排序碼比較6次6 1810 16* 20 282 12 16 30排序碼比較7次排序碼比較9次2 10 12 16 16* 20 28 306 182 6 10 12 16 16* 18 20 2

22、8 30(9) 基數(shù)排序 621630102816*201812按最低位分配r0 r1 r2 r3 r4 r5 r6 r7 r8 r962021816*1028163012f0 f1 f2 f3 f4 f5 f6 f7 f8 f92862101816*16122030收集按最高位分配18r0 r1 r2 r3 r4 r5 r6 r7 r8 r916*16286f0 f1 f2 f3 f4 f5 f6 f7 f8 f9123020210302820181610126216*收集 9-3 在起泡排序過程中，什么情況下排序碼會(huì)朝向與排序相反的方向移動(dòng)，試舉例說明。在快速排序過程中有這種現(xiàn)象嗎？【解答

23、】如果在待排序序列的后面的若干排序碼比前面的排序碼小，則在起泡排序的過程中，排序碼可能向與最終它應(yīng)移向的位置相反的方向移動(dòng)。例如， 57 40 38 11 13 34 48 75 6 19 9 7 如9向相反方向移動(dòng) 6 57 40 38 11 13 34 48 75 7 19 9 如19向相反方向移動(dòng) 6 7 57 40 38 11 13 34 48 75 9 19 如9向最終方向移動(dòng) 6 7 9 57 40 38 11 13 34 48 75 19 如13向相反方向移動(dòng) 6 7 9 11 57 40 38 13 19 34 48 75 如13向最終方向移動(dòng) 6 7 9 11 13 57 4

24、0 38 19 34 48 75 如34向相反方向移動(dòng) 6 7 9 11 13 19 57 40 38 34 48 75 6 7 9 11 13 19 34 57 40 38 48 759-4 試修改起泡排序算法，在正反兩個(gè)方向交替進(jìn)行掃描，即第一趟把排序碼最大的對象放到序列的最后，第二趟把排序碼最小的對象放到序列的最前面。如此反復(fù)進(jìn)行?！窘獯?】template <class Type> void dataList<Type> : shaker_Sort ( ) /奇數(shù)趟對表Vector從前向后, 比較相鄰的排序碼, 遇到逆序即交換, 直到把參加比較排序碼序列/中最大

25、的排序碼移到序列尾部。偶數(shù)趟從后向前, 比較相鄰的排序碼, 遇到逆序即交換, 直到把/參加比較排序碼序列中最小的排序碼移到序列前端。 int i = 1, j; int exchange; while ( i < CurrentSize ) /起泡排序趟數(shù)不超過n-1 exchange = 0;/假定元素未交換 for ( j = CurrentSize-i; j >= i; j- )/逆向起泡 if ( Vectorj-1 > Vectorj ) /發(fā)生逆序 Swap ( Vectorj-1, Vectorj ); /交換, 最小排序碼放在Vectori-1處 exchan

26、ge = 1;/做“發(fā)生了交換”標(biāo)志 if ( exchange = 0 ) break;/當(dāng)exchange為0則停止排序 for ( j = i; j <= CurrentSize-i-1; j+ )/正向起泡 if ( Vectorj > Vectorj+1 ) /發(fā)生逆序 Swap ( Vectorj, Vectorj+1 ); /交換, 最大排序碼放在Vectorn-i處 exchange = 1;/做“發(fā)生了交換”標(biāo)志 if ( exchange = 0 ) break;/當(dāng)exchange為0則停止排序i+; 【解答2】template <class Type&

27、gt; void dataList<Type> : shaker_Sort ( ) int low = 1, high = CurrentSize-1, i, j; int exchange; while ( low < high ) /當(dāng)比較范圍多于一個(gè)對象時(shí)排序 j = low;/記憶元素交換位置 for ( i = low; i < high; i+ )/正向起泡 if ( Vectori > Vectori+1 ) /發(fā)生逆序 Swap ( Vectori, Vectori+1 ); /交換 j = i;/記憶右邊最后發(fā)生交換的位置j high = j;/

28、比較范圍上界縮小到j(luò) for ( i = high; i > low; i- )/反向起泡 if ( Vectori-1 > Vectori ) /發(fā)生逆序 Swap ( Vectori-1, Vectori ); /交換 j = i;/記憶左邊最后發(fā)生交換的位置j low = j;/比較范圍下界縮小到j(luò) 9-5 如果待排序的排序碼序列已經(jīng)按非遞減次序有序排列，試證明函數(shù)QuickSort( )的計(jì)算時(shí)間將下降到O(n2)?！咀C明】若待排序的n個(gè)對象的序列已經(jīng)按排序碼非遞減次序有序排列，且設(shè)排序的時(shí)間代價(jià)為T(n)。當(dāng)以第一個(gè)對象作為基準(zhǔn)對象時(shí)，應(yīng)用一次劃分算法Partition，

29、通過n-1次排序碼比較，把只能把整個(gè)序列劃分為：基準(zhǔn)對象的左子序列為空序列，右子序列為有n-1個(gè)對象的非遞減有序序列。對于這樣的遞歸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) = (n-1) + (n-2) + (n-3) + + 2 + 1= n(n-1)/2 = O(n2)9-6 在實(shí)現(xiàn)快速排序的非遞歸算法時(shí)，可根據(jù)基準(zhǔn)對象，將待排序排序碼序列劃分為兩個(gè)子序

30、列。若下一趟首先對較短的子序列進(jìn)行排序，試證明在此做法下，快速排序所需要的棧的深度為O(log2n)?！窘獯稹坑煽焖倥判虻乃惴芍?所需遞歸工作棧的深度取決于所需劃分的最大次數(shù)。如果在排序過程中每次劃分都能把整個(gè)待排序序列根據(jù)基準(zhǔn)對象劃分為左、右兩個(gè)子序列。假定這兩個(gè)子序列的長度相等，則所需棧的深度為S(n) = 1 + S(n/2) = 1 + 1 + S(n/4) = 2 + S(n/4)= 2 + 1 + S(n/8) = 3 + S(n/8)= = log2n + S(1) = log2n (假設(shè)1個(gè)對象的序列所用遞歸棧的深度為0) 如果每次遞歸左、右子序列的長度不等，并且先將較長的子

31、序列的左、右端點(diǎn)保存在遞歸棧中，再對較短的子序列進(jìn)行排序，可用表示最壞情況的大O表示法表示。此時(shí)其遞歸棧的深度不一定正好是log2n，其最壞情況為O(log2n)。 9-7 在實(shí)現(xiàn)快速排序算法時(shí)，可先檢查位于兩端及中點(diǎn)的排序碼，取三者之中的數(shù)值不是最大也不是最小的排序碼作為基準(zhǔn)對象。試編寫基于這種思想的快速排序算法，并證明對于已排序的排序碼序列，該算法的計(jì)算時(shí)間為O(nlog2n)?！窘獯稹繀⒖唇炭茣?-8在使用非遞歸方法實(shí)現(xiàn)快速排序時(shí), 通常要利用一個(gè)棧記憶待排序區(qū)間的兩個(gè)端點(diǎn)。那么能否用隊(duì)列來代替這個(gè)棧? 為什么?【解答】可以用隊(duì)列來代替棧。在快速排序的過程中，通過一趟劃分，可以把一個(gè)待排

32、序區(qū)間分為兩個(gè)子區(qū)間，然后分別對這兩個(gè)子區(qū)間施行同樣的劃分。棧的作用是在處理一個(gè)子區(qū)間時(shí)，保存另一個(gè)子區(qū)間的上界和下界，待該區(qū)間處理完成后再從棧中取出另一子區(qū)間的邊界，對其進(jìn)行處理。這個(gè)功能利用隊(duì)列也可以實(shí)現(xiàn)，只不過是處理子區(qū)間的順序有所變動(dòng)而已。9-9 試設(shè)計(jì)一個(gè)算法, 使得在O(n)的時(shí)間內(nèi)重排數(shù)組, 將所有取負(fù)值的排序碼排在所有取正值(非負(fù)值)的排序碼之前?！窘獯稹縯emplate<class Type> void reArrange ( dataList<Type>& L ) /數(shù)組元素類型Type只可能取int或float int i = 0, j =

33、 L.length () 1; while ( i != j ) while ( Li.getKey( ) < 0 ) i+; while ( Lj.getKey( ) >= 0 ) j-; swap ( Li, Lj ); i+; j-; 9-10 奇偶交換排序是另一種交換排序。它的第一趟對序列中的所有奇數(shù)項(xiàng)i掃描，第二趟對序列中的所有偶數(shù)項(xiàng)i掃描。若Ai > Ai+1，則交換它們。第三趟有對所有的奇數(shù)項(xiàng)，第四趟對所有的偶數(shù)項(xiàng)，如此反復(fù)，直到整個(gè)序列全部排好序?yàn)橹埂?1) 這種排序方法結(jié)束的條件是什么？ (2) 寫出奇偶交換排序的算法。(3) 當(dāng)待排序排序碼序列的初始排列是

34、從小到大有序，或從大到小有序時(shí)，在奇偶交換排序過程中的排序碼比較次數(shù)是多少？【解答】(1) 設(shè)有一個(gè)布爾變量exchange，判斷在每一次做過一趟奇數(shù)項(xiàng)掃描和一趟偶數(shù)項(xiàng)掃描后是否有過交換。若exchange = 1，表示剛才有過交換，還需繼續(xù)做下一趟奇數(shù)項(xiàng)掃描和一趟偶數(shù)項(xiàng)掃描；若exchange = 0，表示剛才沒有交換，可以結(jié)束排序。(2) 奇偶排序的算法template<Type> void dataList<Type> : odd-evenSort ( ) int i, exchange; do exchange = 0; for ( i = 1; i <

35、CurrentSize; i += 2 )/掃描所有奇數(shù)項(xiàng) if ( Vectori > Vectori+1 ) /相鄰兩項(xiàng)比較, 發(fā)生逆序 exchange = 1;/作交換標(biāo)記 swap ( Vectori, Vectori+1 );/交換 for ( i = 0; i < CurrentSize; i += 2 ) /掃描所有偶數(shù)項(xiàng) if ( Vectori > Vectori+1 ) /相鄰兩項(xiàng)比較, 發(fā)生逆序 exchange = 1; /作交換標(biāo)記 swap ( Vectori, Vectori+1 ); /交換 while ( exchange != 0 );(

36、3) 設(shè)待排序?qū)ο笮蛄兄锌偣灿衝個(gè)對象。序列中各個(gè)對象的序號(hào)從0開始。則當(dāng)所有待排序?qū)ο笮蛄兄械膶ο蟀磁判虼a從大到小初始排列時(shí)，執(zhí)行m = ë(n+1)/2û 趟奇偶排序。當(dāng)所有待排序?qū)ο笮蛄兄械膶ο蟀磁判虼a從小到大初始排列時(shí)，執(zhí)行1趟奇偶排序。在一趟奇偶排序過程中，對所有奇數(shù)項(xiàng)掃描一遍，排序碼比較 ë(n-1)/2û 次；對所有偶數(shù)項(xiàng)掃描一遍，排序碼比較 ën/2û 次。所以每趟奇偶排序兩遍掃描的結(jié)果，排序碼總比較次數(shù)為 ë(n-1)/2û + ën/2û = n-1。9-11 請編寫一個(gè)算法

37、，在基于單鏈表表示的待排序排序碼序列上進(jìn)行簡單選擇排序?！窘獯稹坎捎渺o態(tài)單鏈表作為存儲(chǔ)表示。用Vector0作為表頭結(jié)點(diǎn)，各待排序數(shù)據(jù)對象從Vector1開始存放。算法的思想是每趟在原始鏈表中摘下排序碼最大的結(jié)點(diǎn)(幾個(gè)排序碼相等時(shí)為最前面的結(jié)點(diǎn))，把它插入到結(jié)果鏈表的最前端。由于在原始鏈表中摘下的排序碼越來越小，在結(jié)果鏈表前端插入的排序碼也越來越小，最后形成的結(jié)果鏈表中的結(jié)點(diǎn)將按排序碼非遞減的順序有序鏈接。Template<class Type> void staticlinkList<Type> : selectSort ( ) int h = Vector0.lin

38、k, p, q, r, s; Vector0.link = 0; while ( h != 0 ) /原始鏈表未掃描完 p = s = h; q = r = 0; while ( p != 0 ) /掃描原始鏈表, 尋找排序碼最大的結(jié)點(diǎn)s if ( Vectorp.data > Vectors.data ) /記憶當(dāng)前找到的排序碼最大結(jié)點(diǎn) s = p; r = q; q = p; p = Vectorp.link; if ( s = h ) h = Vectorh;/排序碼最大的結(jié)點(diǎn)是原始鏈表前端結(jié)點(diǎn), 摘下 else Vectorr.link = Vectors.link; /排序碼最

39、大的結(jié)點(diǎn)是原始鏈表表中結(jié)點(diǎn), 摘下 Vectors.link = Vector0.link;/結(jié)點(diǎn)s插入到結(jié)果鏈表的前端 Vector0.link = s; 9-12 若參加錦標(biāo)賽排序的排序碼有11個(gè)，為了完成排序，至少需要多少次排序碼比較？【解答】對于有n(n>0)個(gè)數(shù)據(jù)的序列，錦標(biāo)賽排序選最小數(shù)據(jù)需進(jìn)行n-1次數(shù)據(jù)比較，以后每選一個(gè)數(shù)據(jù)，進(jìn)行數(shù)據(jù)比較的次數(shù)，均需 ëlog2nû -1次（在外結(jié)點(diǎn)層無比較）。對于有11個(gè)排序碼的序列，第一次選具最小排序碼的數(shù)據(jù)，需進(jìn)行10次排序碼比較，以后在剩下的序列中每選一個(gè)具最小排序碼的數(shù)據(jù)，都需進(jìn)行 ëlog211&

40、#251; -1 = 2次排序碼比較，因此，為了完成排序，需要10 + 2*10 = 30次排序碼比較。9-13 試給出適用于錦標(biāo)賽排序的勝者樹的類型聲明。并寫一個(gè)函數(shù)，對n個(gè)參加排序的對象，構(gòu)造勝者樹。設(shè)n是2的冪?！窘獯稹窟m用于錦標(biāo)賽排序的勝者樹的類型聲明. template <class Type> class DataNode /勝者樹結(jié)點(diǎn)的類定義public: Type data;/數(shù)據(jù)值 int index; /樹中的結(jié)點(diǎn)號(hào), 即在完全二叉樹順序存儲(chǔ)中的下標(biāo) int active;/是否參選的標(biāo)志， =1, 參選; =0, 不再參選template <class

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

42、內(nèi)結(jié)點(diǎn)+外結(jié)點(diǎn)數(shù) int loadindex = bottomRowSize - 1;/外結(jié)點(diǎn)開始位置 tree = new DataNode<Type>TreeSize;/動(dòng)態(tài)分配勝者樹結(jié)點(diǎn)數(shù)組空間 int j = 0;/在數(shù)組a中取數(shù)據(jù)指針 for ( int i = loadindex; i < TreeSize; i+ ) /復(fù)制數(shù)組數(shù)據(jù)到樹的外結(jié)點(diǎn)中 treei.index = i;/下標(biāo) if ( j < n ) treei.active = 1; treei.data = aj+; /復(fù)制數(shù)據(jù) else treei.active = 0;/后面的結(jié)點(diǎn)為空的外結(jié)點(diǎn) i = loadindex;/進(jìn)行初始比較尋找最小的項(xiàng) while ( i ) j = i; while ( j < 2*i ) /處理各對比賽者 if ( !treej+1.active| treej.data <= treej+1.data ) tree(j-1)/2 = treej;/勝者送入雙親 else tree(j-1)/2 = treej+1; j += 2;/下一對參加比較的項(xiàng) i = (i-1)/2;/i退到雙親, 直到i=0為止 for ( i=0; i<n-1; i+) /處理其它n-1元素