數(shù)據(jù)結(jié)構(gòu)-jchap9.7各種排序方法綜合比較

第九排 三 52,49,80,36,14,58,61,23,97,14,23,36,49,52,58,61,75,80,假設(shè)含n個記錄的序列為R1,R2Rn其相應(yīng)的關(guān)鍵字序列為K1,K2，Kn它們之間存在著這樣一個關(guān)系：{Rp1,Rp2,…，Rpn的操作稱作排序二 排序和外部排 三 排序的方基于不同的“擴(kuò)大度的方法，排序方法大致可分類交換類選擇類歸并類其它方法#defineMAXSIZE1000typedefintKeyType;typedefstruct 關(guān)鍵字InfoTypeotherinfo;其它數(shù)據(jù) 記錄類typedefstruct r[MAXSIZE+1];//r[0]閑置 //順序表長 順序表類類個記錄“”到有序序列中，9.排序一趟直 有序序有序序列R[1..i-無序序列無無序序列有序序列 R[1..j].keyR[i].key<R[j+1..i-將R[j+1..i-1]中的所有記錄均 不同的具體實現(xiàn)方法導(dǎo)致不同的算法描直接排序（基于順序查找）折半排序（基于折半查找）表排序（基于鏈表）排序（基于逐趟縮小增量一、直 排利用“順序查找”實現(xiàn)

R[0] for(j=i-1;R[0].key<R[j].key;-- 位置為j對于在查找過找到的那些關(guān)鍵for(j=i-1;R[0].key<R[j].key;--j);R[j+1]=R[j]

i2，3，…,for(i=2;i<=n;++iif(R[i].key<R[i-{在R[1..i-1]中查找R[i]的 R[i];}voidInsertionSort(SqList&L)//對順序表L作直 排序for(i=2;i<=L.length;++iif(L.r[i].key<L.r[i-1].key)L.r[0]=L.r[i]; for(j=i-1;L.r[0].key<L.r[j].key;--j)L.r[j+1]=L.r[j]; //記錄后移L.r[j+1] }}//對于直 排序最好的情況（關(guān)鍵字在記錄序列中順序有序n

1i2

n n的情況（關(guān)鍵字在記錄序列中逆序有序nnn

ii2

(n

2)(n2

(ii2

(n

4)(n2

二、折 排R[1..i-1]實現(xiàn)“在R[1..i-1]中查找R[i]的位置”，如此實現(xiàn)的排序為折半插voidBiInsertionSort(SqList&L){for(i=2;i<=L.length;++i){L.r[0]= L.r[i]暫存到在L.r[1..i-1]中折半查 位置for(j=i-1;j>=high+1;--j)L.r[j+1]=L.r[j]; 記錄后移L.r[high+1]=L.r[0];}//}//low= high=i-while(low<=high)m //if(L.r[0].key<highm- elselowm+1; }例如

位置

三、表排為了減少在排序過進(jìn)行的采用的結(jié)構(gòu)。利用靜態(tài)鏈表靜態(tài)鏈表類型說明如下#defineSIZE100 typedefstruct{RcdTyperc; //typedefSLNoder[SIZE]; intlength； }SLinkListType；// 排序基本思列 結(jié)構(gòu)32”至“n”的分量(結(jié)點

初 i=i=i=

候j=0指k候j=0指k間 i=i=kji=i=jk結(jié)結(jié)voidLInsertionSort(ElemSL[]，int//對記錄序列SL[1..n]作 排SL[0].key=MAXINTSL[0].next=1;SL[1].next=for(i=2;i<=n;++ifor(j=0,k=SL[0].next;SL[k].key<=SL[i].key;j=k,k=SL[k].next){SL[j].next=i;SL[i].next=k;//結(jié)點 }// i=

i=

i=

voidArrange(ElemSL[],intn)p //pfor(i=1;i<n;++i)while(p<i)p=q qif(p!=i)SL[p]←→SL[i];交換記錄，使第iSL[i].next }p= p為找第i+1個記錄作準(zhǔn)備,錄}}//四 排序（又稱縮小增量排序 具體做法為序列進(jìn)行排序。例如：將n個記錄分成d個子序列{R[1]，R[1+d]，R[1+2d]，…，R[1+kd]{R[2]，R[2+d]，R[2+2d]，…，R[2+kd]…{R[d]，R[2d]，R[3d]，…，R[kd]，R[(k+1)d]其中，d稱為增量，它的值在排序過程序減為1。9 排序，設(shè)增量d9第二 排序，設(shè)增量d=9 排序，設(shè)增量d=9voidS Insert(SqList&L,intdk){for(i=dk+1;i<=n;++i)if(L.r[i].key<L.r[i-dk].key)L.r[0] //暫存在for(j=i-dk;j-L.r[j+dk]=L.r[j];//記錄后移，查 位L.r[j+dk]= 9}//

void Sort(SqList&L,intdlta[],int //增量為dlta[] for(k=0;k<t; Insert(L, }//

2t-

10

log2(n

dlta[k]13t-k-kt

(2n 2注意！最后一次增量必須為快速排序一、起泡排二、一趟快速排三、快速排四、快速排序的時間分一、起泡排假設(shè)在排序

無序序列R[1..n-比較相鄰記錄，將鍵字最大的記錄交

有序序列R[n-in-i+1的位置

R[n-1趟起泡排序的結(jié)果2趟起泡排序的結(jié)果3趟起泡排序的結(jié)果void emR[],intn)i=lastExchangeIndex=if(R[j+1].keylastExchangeIndex=if(R[j+1].key<R[j].key)Swap(R[j],lastExchangeIndexj;//}for(j=1;j<i;ilastExchangeIndex;本趟進(jìn)行過交換}//}//

//最后一個記錄的位起泡排序的結(jié)束條件最后一趟沒有進(jìn)行“交換記錄 13 9forfor(j=1;j<i;j++)if(R[j+1].key<R[j].key)時間分最好的情況（關(guān)鍵字在記錄序列中順序有序只需進(jìn)行一趟起泡“比較”的次數(shù)n-

“移動”的次數(shù)0的情況（關(guān)鍵字在記錄序列中逆序有序需進(jìn)行n1趟起泡“比較”的次數(shù) “移動”的次數(shù) n(n

3n(n

(iin

1)2

3(iin

1)2R[j].key≤R[i].key≤ (i+1≤j≤t)例

493658619775

R[s]=52為樞R[high].key要求R[high].key≥樞軸的關(guān)鍵字R[low].key要求R[low].key≤樞軸的關(guān)鍵字可見，經(jīng)過“一次劃分52,49,80,36,14,58,61,97,23,調(diào)整為:23,49,1436,(52)58,61,97,80在調(diào)整 ，設(shè)立了兩個指針：和highs和highR[high].key≥52，和R[low].key≤52,否intPartitionRedType&Rintlowinthigh{pivotkey=R[low].key;//用子表的第一個記錄做樞軸while(low<high);//從表的兩端交替向中間掃描{while(low<high&&--R[low]←→R[high];;//將比樞軸小的記錄交換while(low<high&&R[low]←→R[high];//將比樞軸大的記錄交換到高}return //返回樞軸所在位}//intPartition(RedTypeR[],intlow,inthigh)R[0R[low];pivotkeyR[low].key;樞while(low<high)while(low<high&& 從右向左搜R[low]=while(low<high&& 從左向右搜R[high]=}R[low]= return}//三、快速排無序的記錄序列無序的記錄序列一次劃voidQSort(RedType&R[],ints,intt)//對記錄序列R[s..t]進(jìn)行快速排if(s<t-1) 長度大于pivotloc=Partition(R,s,R[s..t進(jìn)行一次劃QSort(R,s,pivotloc-//對低子序列遞歸排序，pivotloc是樞軸位QSort(R,pivotloc+1,t);對高子序列遞歸排}}//Qsort時，待排序記錄序列的上、下界分別為1和L.length。voidQuickSort(SqList&L)QSort(L.r,1,}//假設(shè)i=k，則對n個記錄進(jìn)行快排所需時間：T(n)=Tpass(n)+T(k-1)+T(n-其中Tpass(n)n個記錄進(jìn)行一次劃分k1n中任意一值的可能性相Tavg(n)

Cn

navgnknavg

Tavg(n

k)Tavg

(2

2c)(n

ln(n

結(jié)論:快速排序的時間復(fù)雜度為先對R(s).key,R(t).key和R[(s+t)/2].key， 堆排序堆排序假設(shè)排序 ，待排記錄序列的狀態(tài)為有序序列R[1..i-無序無序序列

從中選關(guān)鍵字最小的簡單選擇排序voidSelectSort(ElemR[],intn)對記錄序列R[1..n]作簡單選擇排序for(i=1;i<n;++i)ij=SelectMinKey(R,在R[i..n]if(i!=j)i}}//對n個記錄進(jìn)行簡單選擇排序，所需進(jìn)行的關(guān)鍵字間的比較次數(shù)n

n(n(ni

i)2最大值為3(n-1)堆是滿足下列性質(zhì)的數(shù)列{r1r2

(小頂堆

(大頂堆r r 2i 2i例如{12,36,27,65,40,34,98,81,73,55,

是小頂{12362765401498817355 r2irir2i+1ri的右孩子 例如

不是例如{40,55,49,73,12,27,98,81,64,36{98,81,49,73,36,27,40,55,64,1298{12,81,49,73,36,27,40,55,64,98

{81,73,49,64,36,27,40,55,12,98voidHeapSort(HeapType&H)對順序H進(jìn)行堆排for( --iHeapAdjustH.ri,H.length 建大頂for(i=H.length;i>1;--i)//將堆頂記錄和當(dāng) 排序子序//H.r[1..i]中最后一個記錄相互交換HeapAdjust(H.r1i-1);H.r[1進(jìn)行篩選}}//typedefSqList堆堆例如

9812進(jìn)行互換之后，它就不voidHeapAdjust(RcdType&R[],ints,int 已知R[s..m]中記錄的關(guān)鍵字除R[s之外rc //forj=2*sj<=mj*=2j初值指向左孩}R[s]=rc;//將調(diào)整前的堆頂記 到s位}//if(j<m&&R[j].key<R[j+1].key)//左/右“子樹根”之間先進(jìn)行相互比令j指示關(guān)鍵字較大記錄的位if(rc.key>=R[j].key)//再作“根”和“子樹根”之間的比較若“>=”成立，則說明已找rc的入位置s，不需要繼續(xù)往下調(diào)R[s]= s=//否則記錄上移，尚需繼續(xù)往下調(diào)例如將一個無序序列建成一個堆(初始堆）的方法篩選過程的算法為從最后一個非葉結(jié)點開始，逐步向根結(jié)點，反復(fù)進(jìn)行“篩選”過程，使其結(jié)點元素的關(guān)鍵字大于左右孩子結(jié)點的關(guān)鍵字。最后一個非葉結(jié)點怎么求已知待排序序列數(shù)據(jù)元素個數(shù)為最后一個非葉結(jié)點的孩子結(jié)點一定是最后一個結(jié)點，則2i=n或者則堆排序voidHeapsort(Sqlist{Hfor(i=H.length/2;i>0;--HeapAdjust(H,i,H.length);//將H.r[1..H.length]建成大頂for(i=H.length;i>1;--{ 排序子序Hr[1..iHeapadjust(H,1,i-1)//將H.r[1..i-1}}堆排序的時間復(fù)雜度分析對深度為k的堆，“篩選”所需進(jìn)行的關(guān)鍵字n個關(guān)鍵字，建成深度為h(=log2n+1)的堆，所需進(jìn)行的關(guān)鍵字比較的次數(shù)至多4n；調(diào)整“堆頂”n-1次，總共進(jìn)行的關(guān)鍵2(log2(n-1)+log2(n-2)+…+log22)<歸并排序歸并排序的過程基于下基本思想進(jìn)行子序列“歸并一個有序在排序中，通常采用的是2-路有序子序列 有序子序

這個操作對順序表而言，是輕而易舉的voidMerge(RcdTypeSR[],RcdTypeinti,intm,intn)將有序的記錄序列SR[i..m//歸并為有序的記錄序列for(j=m+1,k=i;i<=m&&j<=n; //將SR中記錄由小到大地并入TRif(SR[i].key<=SR[j].key)TR[kSR[i++];elseTR[k]=SR[j++]; }//if(i<=m)TR[k..n]=//將剩余的 到if(j<=n)TR[k..n]=//將剩余的 到R[s..t] 52,23, 36,68, (s=1,[52,23, [36,68,[52, [36,[

[23,[23,52,

[36,[14,36,[14,23,36,52,68,80voidMsort(RcdTypeRcdType&TR1[],ints,intt)將SR[s..t]歸并排序為if(s==t) }}//m=//將SR[s..t]平分為SR[s..m]和Msort(SR,TR2,s,遞歸地將SR[s..m]歸并為有序的TR2[s..m]Msort(SR,TR2,m+1,t);//遞歸地SR[m+1..t]歸并為有序的Merge(TR2,TR1,s,m,//將TR2[s..m]和TR2[m+1..t]歸并到voidMergeSort(SqList&L)L作2-MSort(L.r,L.r,1,}//n個記錄進(jìn)行歸并排序的O(n)，總共需進(jìn)行l(wèi)og2n趟?；鶖?shù)排序序”的排序算法。n個記錄的序列R1,R2對關(guān)鍵字(Ki0Ki1,…,Kid-1有序?qū)τ谛蛄兄腥我鈨蓚€記錄Ri和Rj(1≤i<j≤n)都滿足下列(詞典)有序關(guān)系：(Ki0,Ki1,…,Kid-1)<(Kj0,Kj1,…,Kjd-其中: 被稱為“最主”位關(guān)鍵Kd- “ 優(yōu)先MSD（MostSignificant（LeastSignificant先對K0進(jìn)行排序K0后，分別對K1進(jìn)行排序 先對Kd-1進(jìn)行排序，然后對Kd-2 鍵字K0排序完成為止。 無序序?qū)2排對K1排對K0排{209,386,768,185,247,606,230,834,539首先按“個位數(shù)”取值分別為019“分配10組，之后按09的順序?qū)⑺鼈儭笆占痹谝黄?；然后按其“十位?shù)”取值分別為01“分配10組，之后再按從09的順序?qū)⑺鼈儭笆占痹谝黄?；最后按其“百位?shù)”重復(fù)一遍上述操作 ２．“分按當(dāng)前“關(guān)鍵字位”所取值，將記錄分配到不同的“鏈隊列”中，每個隊列中記錄的“關(guān)鍵字位”相同；４．對每個關(guān)鍵字位均重23兩步進(jìn)行第一次分f[9]→369→239→139[9]進(jìn)行第一次收p→230→367→167→237→138進(jìn)行第二次分32302313239139[3636167368[6

進(jìn)行第三次分9←[進(jìn)行第三次收集之后便得到記錄的有序序提醒注意法Arrange將它調(diào)整為有序表。其中：分配為#defineMAX_NUM-OF-KEY8//關(guān)鍵碼項數(shù)最大#define 10//關(guān)鍵碼基數(shù)，此時為十進(jìn)制整數(shù)的基#defineMAX_SPACE1000//分配的最大可利 空typedef keys[MAX_NUM_OF_KEY]；/*關(guān)鍵碼字 otheritems；//其它字 next；//指針字}SLCell；//表結(jié)點類typedefSLCellr[MAX_SPACE]//靜態(tài)鏈表的可利用空間，r[0]為頭結(jié) keynum；//關(guān)鍵碼個 renum；//當(dāng)前表中記錄}SLList；//鏈表類分配算voidDistribute(SLCell&r，inti，ArrType&f，ArrType{//靜態(tài)鏈表L的r域中記錄已按(kye[0]，keys[1]，…，keys[i-1])有序。本算法按第i個關(guān)鍵碼ey[]建立RDX個子表，使同一子表中的記錄的[]相同，f[0…RDX-1]和0…RDX-1]分別指向各子表的第一個和最后一個記錄for(j=0；j<RADIX；j+f[j]=0子表初始化為空{(diào)//ord將記錄中第i個關(guān)鍵 到[0…RADIX-if(!f[j])elser[e[j]].next=p；//e[j]指向字表表尾元素的位序e[j]=p；//將p所指的結(jié)點 }}第i9←[f[3]→367...

收集算voidCollect(SLCell&r，inti，ArrTypef，ArrType{/*本算法按keys[i]自小到大地將f[0…RADIX-1]所指各子表依次成一個for(j=0；!f[j]；j=succ(j))；//找第一個非空子表，succ為求后繼函數(shù)r[0].next=f[j]；t=e[j]//r[0].next指向第一個非空子表中第一個結(jié)點{for(j=succ(j)；j<RADIX-1&&!f[j]；j=succ(j))；//找下一個非空子表if(f[j]){r[t].next=f[j]；t=e[j]；}// }r[t].next=0；//t指向最后一個非空子表中的最后一個}voidRadixSort(SLList{//L是采用靜態(tài)鏈表表示的順序?qū)作