內(nèi)存中完成：6.1簡(jiǎn)單的分類(lèi)算法6.2Shell分類(lèi)6.3快速分類(lèi)6.4歸并分類(lèi)6.5堆分類(lèi)6.6基數(shù)分類(lèi)第6章內(nèi)部分類(lèi)（Sorting）分類(lèi)內(nèi)部分類(lèi)外部分類(lèi)外存上完成：歸并分類(lèi)(Sorting)也叫排序(Ordering)，是將一組數(shù)據(jù)按照規(guī)定順序進(jìn)行排列，其目的是為了方便查詢(xún)和處理。對(duì)于給定數(shù)組A，經(jīng)過(guò)分類(lèi)處理之后，滿(mǎn)足關(guān)系：

A[1].key≤A[2].key≤……≤A[n].key如果在分類(lèi)之前存在關(guān)系

A[i].key=A[j].key(1≤i＜j≤n)經(jīng)分類(lèi)后，A[i]和A[j]分別被移至A[i1]和A[j1]，并且i1和j1滿(mǎn)足關(guān)系

1≤i1＜j1≤n我們稱(chēng)這種分類(lèi)是穩(wěn)定的，否則稱(chēng)其為不穩(wěn)定的分類(lèi)。按分類(lèi)時(shí)分類(lèi)對(duì)象存放的設(shè)備，分成內(nèi)部分類(lèi)(internalsorting)和外部分類(lèi)(externalsorting)。分類(lèi)過(guò)程中數(shù)據(jù)對(duì)象全部在內(nèi)存中的分類(lèi)，叫內(nèi)部分類(lèi)。分類(lèi)過(guò)程數(shù)據(jù)對(duì)象并非完全在內(nèi)存中的分類(lèi)，叫外部分類(lèi)。分類(lèi)的種類(lèi)structrecords{keytypekey;fieldsother;}；typedefrecordsLIST[maxsize];分類(lèi)表的存儲(chǔ)結(jié)構(gòu)影響分類(lèi)性能的因素比較關(guān)鍵字的次數(shù)—當(dāng)關(guān)鍵字是字符串時(shí)，是主要因素。交換記錄位置和移動(dòng)記錄的次數(shù)—當(dāng)記錄很大時(shí)，是主要因素。

012345678910265076301265129751301265265129751301301301937129751438438438863937438751694694694742863937694751742742742694742863937742751751751751076694742863937863863863863863438438694742863937937937937937937如何取消不必要的循環(huán)？6.1簡(jiǎn)單的分類(lèi)算法6.1.1氣泡分類(lèi)氣泡分類(lèi)算法：VoidBubbleSort(intn,LIST&A){intx,y;for(i=1;i<=n-1;i++)for(j=n;j>=i+1;j--)if(A[j].key<A[j-1])swap(A[j],A[j-1])}Voidswap(x,y)records&x,records&y{recordsw;w=x;x=y;y=w;}=1/2·C2n2+(C3-1/2·C2)·n≤(C2/2+C3)n2當(dāng)n2≥1時(shí)

=Cn2T(n)=O(f(n))=O(C·n2)=O(n2)f(n)=C3n+∑C2·(n-i)i=1n-1算法分析：例：設(shè)計(jì)雙向氣泡排序算法，在排序過(guò)程中交替改變掃描方向。VoidDoubleBubbleSort(LIST&A,intn){inti=1,flag=1;while(flag){flag=0;for(j=n-i+1;j>=i+1;j--)//較小元素A[j]if(A[j].key<A[j-1].key){flag=1;swap(A[j],A[j-1]);}for(j=i+1;j<=n-i+1;j++)//較大元素A[n-i+1]if(A[j].key>A[j+1].key){flag=1;swap(A[j],A[j+1]);}i++;}}T(n)=O(n2)flag?

初始狀態(tài)：(265)301751129937863742694076438

第1趟：(265301)751129937863742694076438

第2趟：(265301751)129937863742694076438

第3趟：(129265301751)937863742694076438

第4趟：(129265301751937)863742694076438

第5趟：(129265301751863937)742694076438

第6趟：(129265301742751863937)694076438

第7趟：(129265301694742751863937)076438

第8趟：(076129265301694742751863937)438

第9趟：(076129265301438694742751863937)6.1.2插入分類(lèi)插入分類(lèi)算法：voidInsertSort(n,A)Intn;LISTA;{inti,j;A[0].key=-∞;for(i=1;i<=n;i++){j=i;while(A[j].key<A[j-1].key){swap(A[j],A[j-1]);j=j-1;}}}T(n)=O(n2)j=i;temp=A[j]While(temp.key<A[j-1].key){A[j]=A[j-1];j=j-1;}A[j]=temp;

初始狀態(tài)：265301751129937863742694

076

438

第1趟：076301751

129

937863742694265438

第2趟：076129751301937863742694

265438

第3趟：076129265

301937863742694751438

第4趟：076129265301937863742694751438

第5趟：076129265301438863742

694

751937

第6趟：076129265301438694

742

863751937

第7趟：076129265301438694742863751

937

第8趟：076129265301438694742751

863937

第9趟：076129265301438694742751863

9376.1.3選擇分類(lèi)選擇分類(lèi)算法（冒泡程序）voidSelectSort(n,A)intn;LISTA;{inti,j，lowindex;keytypelowkey;for(i=1;i<n;i++){lowindex=i;for(j=i+1;j<=n;j++)if(A[j].key<A[lowindex].key)lowindex=j;swap(A[i],A[lowindex]);}}T(n)=O(n2)例：設(shè)計(jì)算法，實(shí)現(xiàn)奇偶轉(zhuǎn)換排序。基本思想：第一趟對(duì)所有奇數(shù)的i，將A[i]和A[i+1]進(jìn)行比較；第二趟對(duì)所有偶數(shù)的i，將A[i]和A[i+1]進(jìn)行比較；

if(A[i]>A[i+1])swap(A[i],A[i+1]);

重復(fù)上述二趟交換過(guò)程交換進(jìn)行，直至整個(gè)數(shù)組有序。問(wèn)：

(1)結(jié)束條件是什么？

(2)實(shí)現(xiàn)算法。VoidOESort(LIST&A,intn){inti,flag;do{flag=0;for(i=0;i<n;i+=2)if(A[i]>A[i+1]){flag=1;swap(A[i],A[i+1]);}for(i=1;i<n;i+=2)if(A[i]>A[i+1]){flag=1;swap(A[i],A[i+1]);}}while(flag);}(2)奇偶轉(zhuǎn)換排序算法：(1)結(jié)束條件為不產(chǎn)生交換：6.2Shell分類(lèi)希爾（Shell）排序又稱(chēng)縮小增量法，基本思想為：先取定一個(gè)整數(shù)d1<n，把全部結(jié)點(diǎn)分成d1個(gè)組，所有距離為d1倍數(shù)的記錄放在一組中，在各組內(nèi)進(jìn)行直接插入排序；然后取d2<d1，重復(fù)上述分組和排序工作，直至取di=1，即所有記錄放在一個(gè)組中排序?yàn)橹埂Ｌ攸c(diǎn)：每次以不同的增量分組，組內(nèi)進(jìn)行直接插入排序，在最后一次作組內(nèi)直接插入排序時(shí)，所有記錄“幾乎”有序了?！澳嫘颉苯Y(jié)點(diǎn)作跳躍移動(dòng)，提高了排序速度。例：希爾排序過(guò)程

初始狀態(tài):265301

751

129

937863742

694

076

438第1趟分組d=5:排序結(jié)果：265301694076438863742751129937第2趟分組d=2:排序結(jié)果：129

076

265

301

438

751

694

863

742

937第3趟分組d=1:排序結(jié)果：076129265301438694742751863937VoidShellsort(LIST&A,intn){for(k=n/2;k>=1;k/=2){for(i=k+1;i<=n;i++){x=A[i];j=i-k;while((j>0)&&(x.key<A[j].key)){A[j+k]=A[j];j-=k;}A[j+k]=x;}//組內(nèi)排序，將x直接插入到組內(nèi)合適的位置

}}

是C.R.A.Hoare1962年提出的一種劃分交換排序。采用的是分治策略(一般與遞歸技術(shù)結(jié)合使用)，以減少分類(lèi)過(guò)程之中的比較次數(shù)。分解:將原問(wèn)題分解為若干個(gè)與原問(wèn)題相似的子問(wèn)題，又稱(chēng)劃分求解:遞歸地求解子問(wèn)題，若子問(wèn)題的規(guī)模足夠小，則直接求解組合:將每個(gè)子問(wèn)題的解組合成原問(wèn)題的解。6.3快速分類(lèi)—?jiǎng)澐纸粨Q分類(lèi)基本思想：對(duì)于：A[1].key,A[2].key,……,A[n].key選定中間值v，使之對(duì)某個(gè)k有：

A[1].key,A[2].key,……,A[k-1].key＜A[k].key而：A[k+1].key,A[k+2].key,……,A[n].key≥A[k].key然后分別對(duì)A[1],…,A[k-1]和A[k+1],…,A[n]作同樣的處理。算法要點(diǎn)：（1）中間值v的選擇，其位置確定在A(yíng)[k]

設(shè)findpivot(i,j),求A[i].key,…,A[j].key的中間值v。

ⅰv=(A[i].key，A[(i+j)/2].key,A[j].key的中值)ⅱv=從A[i].key到A[j].key

最先找到的兩個(gè)不同關(guān)鍵字中的最大的。

算法要點(diǎn)（續(xù)）：（2）A[i].key,…,A[j].key分割成A[i],…,A[k-1]和A[k+1],…,A[j]

兩部分。掃描：令游標(biāo)L從左（L=i）向右掃描，越過(guò)key小于v的記錄，直到A[L].key≥v為止；同時(shí)令游標(biāo)R從右（R=j）開(kāi)始向左掃描，越過(guò)key大于等于v的記錄,

直到A[R].key＜v的記錄A[R]為止；測(cè)試：若L>R（L=R+1），成功劃分，L是右邊子序列的起始下表；交換：若L<R,則swap(A[L],A[R])；重復(fù)上述操作，直至過(guò)程進(jìn)行到L>R（L=R+1）為止。Intfindpivot(inti,intj){keytypefirstkey;intk;firstkey=A[i].key;for(k=i;k<=j;k++)if(A[k].key>firstkey)returnk;elsereturni;return0;}找中間值算法:Intpartion(i,j,pivot)Inti,j;keytypepivot;{intL,R;L=i;R=j;do{

swap(A[L],A[R]);while(A[L].key<pivot)L=L+1;while(A[R].key>=pivot)R=R-1;}while(L<=R);returnL;}Voidquicksort(inti,intj){keytypepivot;intpiovtindex,k;pivotindex=findpivot(i,j);if(pivotindex){pivot=A[pivotindex].key;k=partion(i,j,pivot);quicksort(i,k-1);quicksort(k,j);}}分割:[i,……,j][i,…k-1,k,k+1,…j]快速分類(lèi)調(diào)用：quicksort(1,n)T(n)=O(f(n))3562951413時(shí)間復(fù)雜性和穩(wěn)定性時(shí)間復(fù)雜性：T(n)=O(nlog2n)穩(wěn)定性：是不穩(wěn)定的分類(lèi)舉例3563954112v=35569334v=5433v=49565v=9655v=6211v=29655433211組合例：對(duì)長(zhǎng)度為n的記錄序列進(jìn)行快速排序時(shí)，所需要的比較次數(shù)依賴(lài)于這n個(gè)元素的初始序列。問(wèn)：(1)當(dāng)n=8時(shí)，在最好情況下需要進(jìn)行多少次比較？

(2)給出n=8時(shí)的最好情況的初始排序?qū)嵗＝猓簄=8n=3n=4n=1n=1n=1n=2n=17次比較2次比較3次比較1次比較(1)共13次(2)如：2313172160301828一次劃分后：{18131721}23{306028}二次劃分后：{1713}18{21}四次劃分后：{28}30{60}三次劃分后：{13}1713216028結(jié)果：1317182123283060intPartition(inti，intj，intpivot)

{//對(duì)A[low..high]做劃分，并返回基準(zhǔn)記錄的位置

while(i<j)//從區(qū)間兩端交替向中間掃描，直至i=j為止

{

while(i<j&&A[j].key>=pivot)//pivot相當(dāng)于在位置i上

j--；//從右向左掃描，查找第1個(gè)關(guān)鍵字小于pivot的記錄A[j]

if(i<j)//表示找到的A[j]的關(guān)鍵字<pivot

A[i++]=A[j]；//相當(dāng)于交換A[i]和A[j]，交換后i指針加1

while(i<j&&A[i].key<=pivot)//pivot相當(dāng)于在位置j上

i++；//從左向右掃描，查找第1個(gè)關(guān)鍵字大于pivot的記錄A[i]

if(i<j)//表示找到了A[i]，使R[i].key>pivot

A[j--]=A[i];//相當(dāng)于交換A[i]和A[j]，交換后j指針減1

}//endwhile

A[i]=pivot；//基準(zhǔn)記錄已被最后定位

returni；

}//partition另一種劃分方法6.4歸并分類(lèi)合并兩個(gè)有序序列Voidmerge(l,m,n,A,B)Intl,m,n;LISTA,&B;{inti,j,k,t;i=l;k=l;j=m+1;while((i<=m)&&(j<=n)){if(A[i].key<=A[j].key)B[k++]=A[i++];elseB[k++]=A[j++];}if(i>m)for(t=j;t<=n;t++)B[k+t-j]=A[t];elsefor(t=i;t<=m;t++)B[k+t-i]=A[t];}合并A[l],…,A[m]和

A[m+1],…,A[n]形成新的分類(lèi)序列

B[l],…,…,B[n]算法時(shí)間復(fù)雜度T(n)=O(n-l+1){26}{5}{77}{1}{61}{11}{59}{15}{48}{19}{526}{177}{1161}{1559}{1948}{152677}{11155961}{1948}{15111526596177}{1948}{151115192648596177}歸并次數(shù)：1，2，…，2i-1，若長(zhǎng)度為n，則共需歸并log2n總的時(shí)間復(fù)雜性為：T(n)=O(n·log2n)Voidmpass(n,l,A,B)intn,l;LISTA,&B;{inti,t;i=1;while(i<=(n-2*l+1)){merge(i,i+l-1,i+2*l-1,A,B)i=i+2*l;}if((i+l-1)<n)merge(i,i+l-1,n,A,B);elsefor(t=i;t<=n;t++)B[t]=A[t];}VoidT_W_SORT(n,A)Intn;LIST&A;{intl;LISTB;

l=1;while(l<n){mpass(n,l,A,B);

l=2*l;mpass(n,l,B,A);

l=2*l;}}Voidmerge(l,m,n,A,B)Voidmpass(n,l,A,B)l

mm+1nl

nABi=1;while(i<=(n-2*l+1)){merge(i,i+l-1,i+2*l-1,A,B)i=i+2*l;}if((i+l-1)<n)merge(i,i+l-1,n,A,B);elsefor(t=i;t<=n;t++)B[t]=A[t];？lllllllllllll2l2l2l2l2l2l……AB>l<l{26}{5}{77}{1}{61}{11}{59}{15}{48}{19}{526}{177}{1161}{1559}{1948}{152677}{11155961}{1948}{15111526596177}{1948}{151115192648596177}歸并次數(shù)：1，2，…，2i-1，若長(zhǎng)度為n，則共需歸并log2n總的時(shí)間復(fù)雜性為：T(n)=O(n·log2n)6.5堆分類(lèi)[定義]把具有如下性質(zhì)的數(shù)組A表示的二元樹(shù)稱(chēng)為堆（Heap）:(1)若2*i≤n，則A[i].key≤A[2*i].key;(2)若2*i+1≤n，則A[i].key≤A[2*i+1].key;小頂堆或：把具有如下性質(zhì)的數(shù)組A表示的二元樹(shù)稱(chēng)為堆（Heap）:(1)若2*i≤n，則A[i].key≥A[2*i].key;(2)若2*i+1≤n，則A[i].key≥A[2*i+1].key;大頂堆例：1123394655112339465511233946551123394655132539465132539465123453956234539561133456953345695211354569354569321145956459563321155965596433211569569543321169695543321199655433211Voidpushdown(first,last)Intfirst,last;{intr;r=first;while(r<=last/2)if((r==last/2)&&(last%2==0)){if(A[r].key>A[2*r].key)swap(A[r],A[2*r]);r=last;/*結(jié)束循環(huán)*/}elseif((A[r].key>A[2*r].key)&&(A[2*r].key<=A[2*r+1].key)){swap(A[r],A[2*r]);/*左孩子比右孩子小，與左孩子交換*/r=2*r;}elseif((A[r].key>A[2*r+1].key)&&(A[2*r+1].key<A[2*r].key)){swap(A[r],A[2*r+1]);/*右孩子比左孩子小，與右孩子交換*/r=2*r+1;}elser=last;}整理堆：O(last/first)last/2?2258491736225849173i=n/2……16225849173622534967816225349678堆分類(lèi)Voidsort(n,A)intn;LISTA;{inti;for(i=n/2;i>=1;i--)pushdown(i,n);for(i=n;i>=2;i--){swap(A[1],A[i]);pushdown(1,i-1);}}T(n)=O(n·log2n)整理堆建堆堆排序？first？last?6.6基數(shù)分類(lèi)——多關(guān)鍵字分類(lèi)321986123432543018765678987789098890109901210012Q[0]:901109Q[1]:210012018Q[2]:321123Q[3]:432Q[4]:543Q[5]:Q[6]:765Q[7]:678Q[8]:986987789Q[9]:890098901109210012018321123432543765678986987789890098Q[0]:012018098Q[1]:109123Q[2]:210Q[3]:321Q[4]:432Q[5]:543Q[6]:678Q[7]:765789Q[8]:890Q[9]:901986987012018098109123310321432543678765789890901986987Q[0]:890210Q[1]:321901Q[2]:432012Q[3]:123543Q[4]:Q[5]:765Q[6]:986Q[7]:987Q[8]:018678098Q[9]:789109890210321901432012123543765986987018678098789109

Voidradixsort(figure,A)intfigure;QUEUE&A;{QUEUEQ[10];recordsdata;intpass,r,i;for(pass=1;pass<=figure;pass+){for(i=0;i<=9;i++)MAKENULL(Q[i]);while(!EMPTY(A)){data=FRONT(A);DEQUEUE(A);r=RADIX(data.key,pass);ENQUEUE(data,Q[r]);}for(i=0;i<=9;i++)while(!EMPTY(Q[i])){data=FRONT(Q[i]);DEQUEUE(Q[i]);ENQUEUE(data,A);}}}IntRADIX(k,p)Intk,p;{intpower,i;power=1;for(i=1;i<=p-1;i++)power=power*10;return((k%(power*10))/power);}6.7*詞典排序[定義]設(shè)集合S

中的元素為整數(shù)元組，關(guān)系≤為S

的線(xiàn)性序，對(duì)兩個(gè)元素(s1,s2,…,sp)

和(t1,t2,…,tq)

存在(s1,s2,…,sp)≤(t1,t2,…,tq)

，當(dāng)存在一個(gè)整數(shù)j，1≤j≤max[p,q]，使得sj≤tj，且所有1≤i＜j，si＝ti；或者p≤q，并且si＝ti，1≤i≤p，則關(guān)系≤稱(chēng)為詞典序。輸入:一個(gè)序列A1,A2,…,An，其中Ai為k元組(ai1,ai2,…,aik),aij為0～m-1的整數(shù)輸出:一個(gè)序列A1,A2,…,An，B1,B2,…,Bn，使得Bi≤Bi+1,1≤i＜n。{將A1,A2,…,An

進(jìn)入隊(duì)列QUEUE;for(j=k;j>=1;j--){for(i=0;i<=m-1;i++)初始化桶Q[i];while(QUEUE不空){設(shè)Ai

為QUEUE的隊(duì)首元素，刪除Ai，并放到桶Q[aij]中；}for(i=0;i<=m-1;i++)將桶Q[i]連接到隊(duì)列QUEUE后;}}詞典排序算法6.8*求第k個(gè)最小元素——順序統(tǒng)計(jì)問(wèn)題在一個(gè)含有n

個(gè)元素的序列中，要求出第

k

個(gè)最小元素,也稱(chēng)順序統(tǒng)計(jì)?？梢韵冗M(jìn)行排序，然后求出第k

個(gè)最小元素。T(n)=O(nlogn)。下面的算法使得T(n)=O(n)。（證明P233略）基本思想：

根據(jù)某一元素m

將原序列S

化分成3個(gè)子序列S1，S2和S3，使得S1的所有元素都小于m

，S2的所有元素等于m，而S3的所有元素都大于m，通過(guò)統(tǒng)計(jì)S1和S2的元素個(gè)數(shù)，可以確定所求的第k個(gè)最小元素是在S1和S2或S3中。通過(guò)上述方式，將一個(gè)給定的問(wèn)題轉(zhuǎn)換成一個(gè)更小的問(wèn)題。為保證O(n)，必須保證在線(xiàn)性時(shí)間里找到劃分元素m，使得S1和S2的大小不超過(guò)S的一個(gè)固定部分。問(wèn)題的關(guān)鍵是如何選擇劃分元素m。下面算法中，S被劃分成若干子序列，每個(gè)子序列由5個(gè)元素組成。對(duì)每個(gè)子序列排序，取其中值組成一個(gè)序列M。M只包含n/5個(gè)元素，可以比原來(lái)快5倍的速度找到n個(gè)元素的中值。輸入：由n

個(gè)元素組成的序列S

和整數(shù)k(1≤k≤n)

。輸出：S

中第k

個(gè)最小元素。ElementtypeSelect(intk,LISTS){if(|S|<50){Sort(S);returnS中第k個(gè)最小元素；

}else{將S分為|S|/5個(gè)元素序列，每個(gè)序列由5個(gè)元素組成，剩余元素最多4個(gè)；設(shè)M為由每個(gè)5元素序列的中值組成的序列；

m=Select

(┌|M|/2┐,M);

設(shè)S1，S2，和S3分別為S中小于、等于和大于m的元素序列；

if(|S|>=k)returnSelect(k,S1);elseif(|S1|+|S2|>=k)returnm;elsereturnSelect(k-|S1|-|S2|,S3);}}小結(jié)——各種排序的比較排序方法平均時(shí)間最好情況最壞情況輔助空間穩(wěn)定性簡(jiǎn)單排序O(n2)O（n）O(n2)O(1)穩(wěn)定希爾排序O（n1.3）------O(1)不穩(wěn)定快速排序O(n·log2n)O(n·log2n)O(n2)O(log2n)不穩(wěn)定堆排序O(n·log2n)O(n·log2n)O(n·log2n)O(1)不穩(wěn)定歸并排序O(n·log2n)O(n·log2n)O(n·log2n)O(n)穩(wěn)定基數(shù)排序O(d·(n+r·d))O(d·(n+r·d))O(d·(n+r·d))O(n+r·d)穩(wěn)定不同條件下，排序方法的選擇：

(1)若n較小(如n≤50)，可采用直接插入或直接選擇排序。

當(dāng)記錄規(guī)模較小時(shí)，直接插入排序較好；否則因?yàn)橹苯舆x擇移動(dòng)的記錄數(shù)少于直接插人，應(yīng)選直接選擇排序?yàn)橐恕?/p>

(2)若文件初始狀態(tài)基本有序(指正序)，則應(yīng)選用直接插人、冒泡或隨機(jī)的快速排序?yàn)橐?；且以直接插入排序最佳?/p>

(3)若n較大，則應(yīng)采用時(shí)間復(fù)雜度為O(nlgn)的排序方法：快速排序、堆排序或歸并排序。

快速排序是目前基于比較的內(nèi)部排序中被認(rèn)為是最好的方法，當(dāng)待排序的關(guān)鍵字是隨機(jī)分布時(shí)，快速排序的平均時(shí)間最短；堆排序所需的輔助空間少于快速排序，并且不會(huì)出現(xiàn)快速排序可能出現(xiàn)的最壞況。這兩種排序都是不穩(wěn)定的。基數(shù)排序適用于n值很大而關(guān)鍵字較小的序列。若要求排序穩(wěn)定，則可選用歸并排序，基數(shù)排序穩(wěn)定性最佳。課堂練習(xí)題：在上面的排序方法中:(1)直接插入排序、冒泡排序、歸并排序和基數(shù)排序是穩(wěn)定的。(2)其他排序算法均是不穩(wěn)定的。(3)以帶*號(hào)的表示區(qū)別：希爾排序：[8,1,10,5,6,8*]

快速排序：[2,2*,1]

直接選擇排序：[2,2*,1]

堆排序：[2,2*,1]1、以關(guān)鍵字序列(265,301,751,129,937,863,742,694,076,438)為例，分別寫(xiě)出執(zhí)行以下排序算法的各趟排序結(jié)束時(shí)，關(guān)鍵字序列的狀態(tài)。

(1)直接插入排序(2)希爾排序(3)冒泡排序(4)快速排序

(5)直接選擇排序(6)歸并排序(7)堆排序(8)基數(shù)排序上述方法中：(1)哪些是穩(wěn)定的排序?(2)哪些是非穩(wěn)定的排序?(3)對(duì)不穩(wěn)定的排序試舉出一個(gè)不穩(wěn)定的實(shí)例。初始態(tài)：265[301751129937863742694076438]第一趟：265301[751129937863742694076438]第二趟：265301751[129

937863742694076438]第三趟：129265301751[937863742694076438]第四趟：129265301751937[863

742694076438]第五趟：129265301751863937[742

694076438]第六趟：129265301742751863937[694076438]第七趟：129265301694742751863937[076438]第八趟：076129265301694742751863937[438]第九趟：076129265301438694742751863937

(1)直接插入排序(方括號(hào)表示無(wú)序區(qū))(2)希爾排序(增量為5，3，1)

初始態(tài)：265

301

751129

937

863

742

694076

438

第一趟：265301694076438863742751129937

第二趟：076301129265438694742751863937

第三趟：076129265301438694742751863937

(3)冒泡排序(方括號(hào)為無(wú)序區(qū))初始態(tài)：[265301751129937863742694076438]第一趟：076[265301751129937863742694438]第二趟：076129[265301751438937863742694]第三趟：076129265[301438694751937863742]第四趟：076129265301[438694742751937863]第五趟：076129265301438[694742751863937]第六趟：076129265301438694742751863937(4)快速排序(方括號(hào)表示無(wú)序區(qū)，層表示對(duì)應(yīng)的遞歸樹(shù)的層數(shù))初始態(tài)：[265301751129937863742694076438]第二層：[076129]265[751937863742694301438]第三層：076[129]265[438301694742]751[863937]第四層：076129265[301]438[694742]751863[937]第五層：076129265301438694[742]751863937第六層：076129265301438694742751863937(5)直接選擇排序(方括號(hào)為無(wú)序區(qū))

初始態(tài)265301751129937863742694076438]第一趟：076[301751129937863742694265438]第二趟：076129[751301937863742694265438]第三趟：076129265[301937863742694751438]第四趟：076129265301[937863742694751438]第五趟：076129265301438[863742694751937]第六趟：076129265301438694[742751863937]第七趟：076129265301438694742[751863937]第八趟：076129265301438694742751[937863]第九趟：076129265301438694742751863937(6)歸并排序(為了表示方便，采用自底向上的歸并，方括號(hào)為有序區(qū))初始態(tài)：[265][301][751][129][937][863][742][694][076][438]第一趟：[265301][129751][863937][694742][076438]第二趟：[129265301751][694742863937][076438]第三趟：[129265301694742751863937][076438]第四趟：[076129265301438694742751863937](6)堆排序（通過(guò)畫(huà)二叉樹(shù)可以一步步得出排序結(jié)果）初始態(tài)：[265301751129937863742694076438]建立初始堆：[937694863265438751742129075301]第一次排序重建堆：[863694751765438301742129075]937第二次排序重建堆：[751694742265438301075129]863937第三次排序重建堆：[742694301265438129075]751863937第四次排序重建堆：[694438301265075129]742751863937第五次排序重建堆：[438265301129075]694742751863937第六次排序重建堆：[301265075129]438694742751863937第七次排序重建堆：[265129075]301438694742751863937第八次排序重建堆：[129075]265301438694742751863937第九次排序重建堆：075129265301438694742751863937(8)基數(shù)排序(方括號(hào)內(nèi)表示一個(gè)箱子共有10個(gè)箱子，箱號(hào)從0到9)初始態(tài)：265301751129937863742694076438第一趟：[][301751][742][863][694][265][076][937][438][129]第二趟：[301][][129][937438][742][751][863265][076][][694]第三趟：[075][129][265][301][438][][694][742751][863][937]

若關(guān)鍵字是非負(fù)整數(shù)，則基數(shù)排序最快；若要求輔助空間為O(1)，則應(yīng)選堆排序；若要求排序是穩(wěn)定的，且關(guān)鍵字是實(shí)數(shù)，則應(yīng)選歸并排序，因?yàn)榛鶖?shù)排序不適用于實(shí)數(shù)，雖然它也是穩(wěn)定的。

此時(shí)Partion返回值是low.此時(shí)快速排序的運(yùn)行時(shí)間是：

(high-low)(high-low-1)/2=O((high-low)^2)，可以修改Partion，將其中RecTypepivot=R[i];句改為：

RecTypepivot=R[(j+i)/2]；也就是取中間的關(guān)鍵字為基準(zhǔn)，這樣就能使劃分的結(jié)果是平衡的。3、若關(guān)鍵字是非負(fù)整數(shù)，快速排序、歸并、堆和基數(shù)排序哪一個(gè)最快?

若要求輔助空間為O(1)，則應(yīng)選擇誰(shuí)?

若要求排序是穩(wěn)定的，且關(guān)鍵字是實(shí)數(shù)，則應(yīng)選擇誰(shuí)?2、當(dāng)R[low..high]中的關(guān)鍵字均相同時(shí)，Partion返回值是什么?

此時(shí)快速排序的的運(yùn)行時(shí)間是多少?能否修改Partion,使得劃分結(jié)果是平衡的(即劃分后左右區(qū)間的長(zhǎng)度大致相等)?

堆的性質(zhì)是：任一非葉結(jié)點(diǎn)上的關(guān)鍵字均不大于(或不小于)其孩子結(jié)點(diǎn)上的關(guān)鍵字。據(jù)此我們可以通過(guò)畫(huà)二叉樹(shù)來(lái)進(jìn)行判斷和調(diào)整：

(1)此序列不是堆，經(jīng)調(diào)整后成為大頂堆：

(100,80,73,66,39,42,57,35,21)

(2)此序列不是堆，經(jīng)調(diào)整后成為小頂堆：

(12,24,33,65,33,56,48,92,86,70)

(3)此序列是一大頂堆。

(4)此序列不是堆，經(jīng)調(diào)整后成為小頂堆：

(05,23,20,56,28,38,29,61,35,76,100)4、判別下列序列是否為堆(小頂堆或大頂堆)，若不是，則將其調(diào)整為堆：

(1)(100,86,73,35,39,42,57,66,21)

(2)(12,70,33,65,24,56,48,92,86,33)

(3)(103,97,56,38,66,23,42,12,30,52,06,20)

(4)(05,56,20,23,40,38,29,61,35,76,28,100)5、有序數(shù)組是堆嗎?這四種排序算法中，直接選擇、快速排序均是不穩(wěn)定的，因此先予以排除，剩下兩種算法中，由于直接插入算法所費(fèi)時(shí)間比冒泡法更少，因此選擇直接插入排序算法為宜。有序數(shù)組是堆。因?yàn)橛行驍?shù)組中的關(guān)鍵字序列滿(mǎn)足堆的性質(zhì)。

若數(shù)組為降序，則此堆為大頂堆，反之為小頂堆。6、若文件初態(tài)是反序的，且要求穩(wěn)定排序，則在直接插入、直接選擇、冒泡排序和快速排序中選哪則種方法為宜?應(yīng)選直接選擇排序?yàn)楦?。分析如下?/p>

(1)在直接插入排序算法中，反序輸入時(shí)是最壞情況，此時(shí)：關(guān)鍵字的比較次數(shù)：Cmax=(n+2)(n-2)/2

記錄移動(dòng)次數(shù)為：Mmax=(n-1)(n+4)/2

Tmax=n2-4n-3(以上二者相加)

(2)在冒泡排序算法中，反序也是最壞情況，此時(shí)：

Cmax=n(n-1)/2

Mmax=3n(n-1)/2

Tmax=2n2-2n

(3)在選擇排序算法中，

Cmax=n(n-1)/2Mmax=3(n-1)

Tmax=n2/2-5n/2-3

雖然它們的時(shí)間復(fù)雜度都是O(n2),但是選擇排序的常數(shù)因子為1/2，因此選擇排序最省時(shí)間。7、若文件初態(tài)是反序的，則直接插入，直接選擇和冒泡排序哪一個(gè)更好?

重寫(xiě)的算法如下：

voidInsertSort(SeqListR)

{//對(duì)順序表中記錄R[0..n-1]按遞增序進(jìn)行插入排序

inti,j;

for(i=n-2;i>=0;i--)//在有序區(qū)中依次插入R[n-2]..R[0]

if(R[i].key>R[i+1].key)//若不是這樣則R[i]原位不動(dòng)

{

R[n]=R[i];j=i+1;//R[n]是哨兵

do{//從左向右在有序區(qū)中查找插入位置

R[j-1]=R[j];//將關(guān)鍵字小于R[i].key的記錄向右移

j++;

}while(R[j].key<R[n].key]);

R[j-1]=R[n];//將R[i]插入到正確位置上

}//endif}8、將哨兵放在R[n]中，被排序的記錄放在R[0..n-1]中，重寫(xiě)直接插入排序算法。intQuickSort(SeqListR,intj,intlow,inthigh){//對(duì)R[low..high]快速排序

intpivotpos；//劃分后的基準(zhǔn)記錄的位置

if(low<high){//僅當(dāng)區(qū)間長(zhǎng)度大于1時(shí)才須排序

pivotpos=Partition(R，low，high)；//對(duì)R[low..high]做劃分

if(pivotpos==j)returnr[j];

elseif(pivotpos>j)return(R,j,low,pivotpos-1);

elsereturnquicksort(R,j,pivotpos+1,high);

}//Endif}//QuickSort9、對(duì)給定的j(1≤j≤n),要求在無(wú)序的記錄區(qū)R[1..n]中找到按關(guān)鍵字自小到大排在第j個(gè)位置上的記錄(即在無(wú)序集合中找到第j個(gè)最小元)，試?yán)每焖倥判虻膭澐炙枷刖帉?xiě)算法實(shí)現(xiàn)上述的查找操作。

10、設(shè)向量A[0..n-1]中存有n個(gè)互不相同的整數(shù)，且每個(gè)元素的值均在

0到n-1之間。試寫(xiě)一時(shí)間為O(n)的算法將向量A排序，結(jié)果可輸出到另一個(gè)向量B[0..n-1]中。Sort(int*A,int*B)

{//將向量A排序后送入B向量中

inti;

for(i=0;i<=n-1;i++)

B[A[i]]=A[i];

}Sort(int*A)

{inti;

for(i=0;i<=n-1;i++)

A[i]=i;

}寫(xiě)一個(gè)heapInsert(R,key)算法，將關(guān)鍵字插入到堆R中去，并保證插入R后仍是堆。提示：應(yīng)為堆R增