第9章 排序

1、第9章排序1第9章排序靜態(tài)數(shù)據(jù)表類定義#includeconstintDefaultSize=100templateclassdataList數(shù)據(jù)表的前視聲明templateclassElement數(shù)據(jù)表元素類的定義friendclassdataListprivate:Typekey排序碼fieldotherdata其它數(shù)據(jù)成員public:TypegetKey()returnkey取當前結(jié)點的排序碼voidsetKey(constTy

2、pex)key=x將當前結(jié)點的排序碼修改為xElementotherdata=xotherdataintoperat==(Type判this與x相等intoperatkey判this小于或等于xintoperat(Type判this大于xintoperatxkey判this小于xtemplateclassdataList用順序表來存儲待排序的元素，這些元素的類型是Typeprivate:ElementVect存儲待排序元素的向量intM

3、axSizeCurrentSize最大元素個數(shù)與當前元素個數(shù)intPartition(constintlowconstinthigh)用于快速排序的一次劃分算法public:datalist(intMaxSz=DefaultSize):MaxSize(Maxsz)CurrentSize(0)Vect=newElement[MaxSize]構(gòu)造函數(shù)intlength()returnCurrentSizeElementvoidswap(El

4、ementx=yy=tempvoidSt()排序靜態(tài)鏈表類定義templateclassstaticlinkList靜態(tài)鏈表類的前視聲明templateclassElement靜態(tài)鏈表元素類的定義friendclassstaticlinkListprivate:第9章排序3i=9[2610121616202830]188[261012161618202830](2)希爾排序(增量為521)初始排列0123456789排序碼比較次數(shù)122

5、16302810162061811111=5d=5102166181216203028(1121)(11d=211)=91021661612182030281131311d=112=14261012161618202830希爾(shell)本人采取的增量序列為?n2???n2?2???n2?2?2?…1。一般地，增量序列可采用?nα???nα?α???nα?α?α?…1。大量實驗表明，取α=0.45454的增量序列比取其他的增量序列的優(yōu)

6、越性更顯著。計算?0.45454n?的一個簡單方法是用整數(shù)算術(shù)計算(5n1)11。需要注意，當?12時，增量序列可能不以1結(jié)束，需要加以判斷和調(diào)整。(3)起泡排序初始排列0123456789排序碼比較次數(shù)i=0[122163028101620618]9i=12[12616302810162018]8i=226[1210163028161820]7i=32610[12161630281820]6i=4261012[161618302820

7、]5i=526101216[1618203028]4i=62610121616[18202830]3261012161618202830(4)快速排序PivotPvtpos0123456789排序碼比較次數(shù)120123[122163028101620618]9601[6210]12[281616203018]22845678[2]6[10]12[281616203018]518456261012[18161620]28[30]31642