真誠為您提供優(yōu)質(zhì)參考資料，若有不當(dāng)之處，請指正。第十章 內(nèi)部排序 10.23 void Insert_Sort1(SqList &L)/監(jiān)視哨設(shè)在高下標(biāo)端的插入排序算法k=L.length;for(i=k-1;i;-i) /從后向前逐個(gè)插入排序if(L.ri.key>L.ri+1.key)L.rk+1.key=L.ri.key; /監(jiān)視哨for(j=i+1;L.rj.key>L.ri.key;+j)L.rj-1.key=L.rj.key; /前移L.rj-1.key=L.rk+1.key; /插入/Insert_Sort1 10.24 void BiInsert_Sort(SqList &L)/二路插入排序的算法int dMAXSIZE; /輔助存儲x=L.r.key;d=x;first=1;final=1;for(i=2;i<=L.length;i+)if(L.ri.key>=x) /插入前部for(j=final;dj>L.ri.key;j-)dj+1=dj;dj+1=L.ri.key;final+;else /插入后部for(j=first;dj<L.ri.key;j+)dj-1=dj;d(j-2)%MAXSIZE+1=L.ri.key;first=(first-2)%MAXSIZE+1; /這種形式的表達(dá)式是為了兼顧first=1的情況/forfor(i=first,j=1;di;i=i%MAXSIZE+1,j+)/將序列復(fù)制回去L.rj.key=di;/BiInsert_Sort 10.25 void SLInsert_Sort(SLList &L)/靜態(tài)鏈表的插入排序算法L.r0.key=0;L.r0.next=1;L.r1.next=0; /建初始循環(huán)鏈表for(i=2;i<=L.length;i+) /逐個(gè)插入p=0;x=L.ri.key;while(L.rL.rp.next.key<x&&L.rp.next)p=L.rp.next;q=L.rp.next;L.rp.next=i;L.ri.next=q;/forp=L.r0.next;for(i=1;i<L.length;i+) /重排記錄的位置while(p<i) p=L.rp.next;q=L.rp.next;if(p!=i)L.rp<->L.ri;L.ri.next=p;p=q;/for/SLInsert_Sort 10.26 void Bubble_Sort1(int a ,int n)/對包含n個(gè)元素的數(shù)組a進(jìn)行改進(jìn)的冒泡排序change=n-1; /change指示上一趟冒泡中最后發(fā)生交換的元素while(change)for(c=0,i=0;i<change;i+)if(ai>ai+1)ai<->ai+1;c=i+1; /c指示這一趟冒泡中發(fā)生交換的元素change=c;/while/Bubble_Sort1 10.27 void Bubble_Sort2(int a ,int n)/相鄰兩趟是反方向起泡的冒泡排序算法low=0;high=n-1; /冒泡的上下界change=1;while(low<high&&change)change=0;for(i=low;i<high;i+) /從上向下起泡if(ai>ai+1)ai<->ai+1;change=1;high-; /修改上界for(i=high;i>low;i-) /從下向上起泡if(ai<ai-1)ai<->ai-1;change=1;low+; /修改下界/while/Bubble_Sort2 10.28 void Bubble_Sort3(int a ,int n)/對上一題的算法進(jìn)行化簡,循環(huán)體中只包含一次冒泡int b 3 ; /b0為冒泡的下界,b 2 為上界,b1無用d=1;b0=0;b 2 =n-1; /d為冒泡方向的標(biāo)識,1為向上,-1為向下change=1;while(b0<b 2 &&change)change=0;for(i=b1-d;i!=b1+d;i+=d) /統(tǒng)一的冒泡算法if(ai-ai+d)*d>0) /注意這個(gè)交換條件ai<->ai+d;change=1;b1+d-=d; /修改邊界d*=-1; /換個(gè)方向/while/Bubble_Sort3 10.29 void OE_Sort(int a ,int n)/奇偶交換排序的算法change=1;while(change) change=0;for(i=1;i<n-1;i+=2) /對所有奇數(shù)進(jìn)行一趟比較if(ai>ai+1)ai<->ai+1;change=1;for(i=0;i<n-1;i+=2) /對所有偶數(shù)進(jìn)行一趟比較if(ai>ai+1)ai<->ai+1;change=1;/while/OE_Sort 分析:本算法的結(jié)束條件是連續(xù)兩趟比較無交換發(fā)生10.30 typedef struct int low; int high; boundary; /子序列的上下界類型 void QSort_NotRecurve(int SQList &L)/快速排序的非遞歸算法low=1;high=L.length;InitStack(S); /S的元素為boundary類型while(low<high&&!StackEmpty(S) /注意排序結(jié)束的條件if(high-low>2) /如果當(dāng)前子序列長度大于3且尚未排好序pivot=Partition(L,low,high); /進(jìn)行一趟劃分if(high-pivot>pivot-low)Push(S,pivot+1,high); /把長的子序列邊界入棧high=pivot-1; /短的子序列留待下次排序elsePush(S,low,pivot-1);low=pivot+1;/ifelse if(low<high&&high-low<3)/如果當(dāng)前子序列長度小于3且尚未排好序Easy_Sort(L,low,high); /直接進(jìn)行比較排序low=high; /當(dāng)前子序列標(biāo)志為已排好序else /如果當(dāng)前子序列已排好序但棧中還有未排序的子序列Pop(S,a); /從棧中取出一個(gè)子序列l(wèi)ow=a.low;high=a.high;/while/QSort_NotRecurve int Partition(SQList &L,int low,int high)/一趟劃分的算法,與書上相同L.r0=L.rlow;pivotkey=L.rlow.key;while(low<high)while(low<high&&L.rhigh.key>=pivotkey)high-;L.rlow=L.rhigh;while(low<high&&L.rlow.key<=pivotkey)low+;L.rhigh=L.rlow;/whileL.rlow=L.r0;return low;/Partition void Easy_Sort(SQList &L,int low,int high)/對長度小于3的子序列進(jìn)行比較排序if(high-low=1) /子序列只含兩個(gè)元素if(L.rlow.key>L.rhigh.key) L.rlow<->L.rhigh;else /子序列含有三個(gè)元素if(L.rlow.key>L.rlow+1.key) L.rlow<->L.rlow+1;if(L.rlow+1.key>L.rhigh.key) L.rlow+1<->L.rhigh;if(L.rlow.key>L.rlow+1.key) L.rlow<->L.rlow+1;/Easy_Sort 10.31 void Divide(int a ,int n)/把數(shù)組a中所有值為負(fù)的記錄調(diào)到非負(fù)的記錄之前l(fā)ow=0;high=n-1;while(low<high)while(low<high&&ahigh>=0) high-; /以0作為虛擬的樞軸記錄alow<->ahigh;while(low<high&&alow<0) low+;alow<->ahigh;/Divide 10.32 typedef enum RED,WHITE,BLUE color; /三種顏色 void Flag_Arrange(color a ,int n)/把由三種顏色組成的序列重排為按照紅,白,藍(lán)的順序排列i=0;j=0;k=n-1;while(j<=k)switch(aj)case RED:ai<->aj;i+;j+;break;case WHITE:j+;break;case BLUE:aj<->ak;k-; /這里沒有j+;語句是為了防止交換后aj仍為藍(lán)色的情況/Flag_Arrange分析:這個(gè)算法中設(shè)立了三個(gè)指針.其中,j表示當(dāng)前元素;i以前的元素全部為紅色;k以后的元素全部為藍(lán)色.這樣,就可以根據(jù)j的顏色,把其交換到序列的前部或者后部. 10.33 void LinkedList_Select_Sort(LinkedList &L)/單鏈表上的簡單選擇排序算法for(p=L;p->next->next;p=p->next)q=p->next;x=q->data;for(r=q,s=q;r->next;r=r->next) /在q后面尋找元素值最小的結(jié)點(diǎn)if(r->next->data<x)x=r->next->data;s=r;if(s!=q) /找到了值比q->data更小的最小結(jié)點(diǎn)s->nextp->next=s->next;s->next=q;t=q->next;q->next=p->next->next;p->next->next=t; /交換q和s->next兩個(gè)結(jié)點(diǎn)/for/LinkedList_Select_Sort 10.34 void Build_Heap(Heap &H,int n)/從低下標(biāo)到高下標(biāo)逐個(gè)插入建堆的算法for(i=2;i<n;i+) /此時(shí)從H.r1到H.ri-1已經(jīng)是大頂堆j=i;while(j!=1) /把H.ri插入k=j/2;if(H.rj.key>H.rk.key)H.rj<->H.rk;j=k;/for/Build_Heap 10.35 void TriHeap_Sort(Heap &H)/利用三叉樹形式的堆進(jìn)行排序的算法for(i=H.length/3;i>0;i-)Heap_Adjust(H,i,H.length);for(i=H.length;i>1;i-)H.r1<->H.ri;Heap_Adjust(H,1,i-1);/TriHeap_Sort void Heap_Adjust(Heap &H,int s,int m)/順序表H中,H.rs+1到H.rm已經(jīng)是堆,把H.rs插入并調(diào)整成堆rc=H.rs;for(j=3*s-1;j<=m;j=3*j-1)if(j<m&&H.rj.key<H.rj+1.key) j+;if(j<m&&H.rj.key<H.rj+1.key) j+;H.rs=H.rj;s=j;H.rs=rc;/Heap_Adjust分析:本算法與課本上的堆排序算法相比,只有兩處改動(dòng):1.建初始堆時(shí),i的上限從H.length/3開始(為什么?) 2.調(diào)整堆的時(shí)候,要從結(jié)點(diǎn)的三個(gè)孩子結(jié)點(diǎn)中選擇最大的那一個(gè),最左邊的孩子的序號的計(jì)算公式為j=3*s-1(為什么?) 10.36 void Merge_Sort(int a ,int n)/歸并排序的非遞歸算法for(l=1;l<n;l*=2) /l為一趟歸并段的段長for(i=0;(2*i-1)*l<n;i+) /i為本趟的歸并段序號start1=2*l*i; /求出待歸并的兩段的上下界end1=start1+l-1;start2=end1+1;end2=(start2+l-1)>(n-1)?(n-1):(start2+l-1);/注意end2可能超出邊界Merge(a,start1,end1,start2,end2); /歸并/Merge_Sort void Merge(int a ,int s1,int e1,int s2,int e2)/將有序子序列as1到ae1和as2到ae2歸并為有序序列as1到ae2int bMAXSIZE; /設(shè)立輔助存儲數(shù)組bfor(i=s1,j=s2,k=s1;i<=e1&&j<=e2;k+)if(ai<aj) bk=ai+;else bk=aj+;while(i<=e1) bk+=ai+;while(j<=e2) bk+=aj+; /歸并到b中for(i=s1;i<=e2;i+) /復(fù)制回去ai=bi;/Merge 10.37 void LinkedList_Merge_Sort1(LinkedList &L)/鏈表結(jié)構(gòu)上的歸并排序非遞歸算法for(l=1;l<L.length;l*=2) /l為一趟歸并段的段長for(p=L->next,e2=p;p->next;p=e2)for(i=1,q=p;i<=l&&q->next;i+,q=q->next);e1=q;for(i=1;i<=l&&q->next;i+,q=q->next);e2=q; /求出兩個(gè)待歸并子序列的尾指針if(e1!=e2) LinkedList_Merge(L,p,e1,e2); /歸并/LinkedList_Merge_Sort1 void LinkedList_Merge(LinkedList &L,LNode *p,LNode *e1,LNode *e2)/對鏈表上的子序列進(jìn)行歸并,第一個(gè)子序列是從p->next到e1,第二個(gè)是從e1->next到e2q=p->next;r=e1->next; /q和r為兩個(gè)子序列的起始位置while(q!=e1->next&&r!=e2->next)if(q->data<r->data) /選擇關(guān)鍵字較小的那個(gè)結(jié)點(diǎn)接在p的后面p->next=q;p=q;q=q->next;elsep->next=r;p=r;r=r->next;/whilewhile(q!=e1->next) /接上剩余部分p->next=q;p=q;q=q->next;while(r!=e2->next)p->next=r;p=r;r=r->next;/LinkedList_Merge 10.38 void LinkedList_Merge_Sort2(LinkedList &L)/初始?xì)w并段為最大有序子序列的歸并排序,采用鏈表存儲結(jié)構(gòu)LNode *endMAXSIZE; /設(shè)立一個(gè)數(shù)組來存儲各有序子序列的尾指針for(p=L->next->next,i=0;p;p=p->next) /求各有序子序列的尾指針if(!p->next|p->data>p->next->data) endi+=p;while(end0->next) /當(dāng)不止一個(gè)子序列時(shí)進(jìn)行兩兩歸并j=0;k=0; /j:當(dāng)前子序列尾指針存儲位置;k:歸并后的子序列尾指針存儲位置for(p=L->next,e2=p;p->next;p=e2) /兩兩歸并所有子序列e1=endj;e2=endj+1; /確定兩個(gè)子序列if(e1->next) LinkedList_Merge(L,p,e1,e2); /歸并endk+=e2; /用新序列的尾指針取代原來的尾指針j+=2; /轉(zhuǎn)到后面兩個(gè)子序列/while/LinkedList_Merge_Sort2 void LinkedList_Merge(LinkedList &L,LNode *p,LNode *e1,LNode *e2)/對鏈表上的子序列進(jìn)行歸并,第一個(gè)子序列是從p->next到e1,第二個(gè)是從e1->next到e2q=p->next;r=e1->next;while(q!=e1->next&&r!=e2->next)if(q->data<r->data)p->next=q;p=q;q=q->next;elsep->next=r;p=r;r=r->next;/whilewhile(q!=e1->next)p->next=q;p=q;q=q->next;while(r!=e2->next)p->next=r;p=r;r=r->next;/LinkedList_Merge,與上一題完全相同 10.39 void SL_Merge(int a ,int l1,int l2)/把長度分別為l1,l2且l12<(l1+l2)的兩個(gè)有序子序列歸并為有序序列start1=0;start2=l1; /分別表示序列1和序列2的剩余未歸并部分的起始位置for(i=0;i<l1;i+) /插入第i個(gè)元素for(j=start2;j<l1+l2&&aj<astart1+i;j+); /尋找插入位置k=j-start2; /k為要向右循環(huán)移動(dòng)的位數(shù)RSh(a,start1,j-1,k);/將astart1到aj-1之間的子序列循環(huán)右移k位start1+=k+1;start2=j; /修改兩序列尚未歸并部分的起始位置/SL_Merge void RSh(int a ,int start,int end,int k)/將astart到aend之間的子序列循環(huán)右移k位,算法原理參見5.18len=end-start+1;for(i=1;i<=k;i+)if(len%i=0&&k%i=0) p=i; /求len和k的最大公約數(shù)pfor(i=0;i<p;i+) /對p個(gè)循環(huán)鏈分別進(jìn)行右移j=start+i;l=start+(i+k)%len;temp=aj;while(l!=start+i)aj=temp;temp=al;al=aj;j=l;l=start+(j-start+k)%len; /依次向右移astart+i=temp;/for/RSh 10.40 書后給出的解題思路在表述上存在問題,無法理解.比如說,"把第一個(gè)序列劃分為兩個(gè)子序列,使其中的第一個(gè)子序列含有s1個(gè)記錄,0<=s1<s,第二個(gè)子序列有s個(gè)記錄."可是題目中并沒有說明,第一個(gè)序列的長度<2s.請會(huì)做的朋友提供解法. 10.41 void Hash_Sort(int a )/對1000個(gè)關(guān)鍵字為四位整數(shù)的記錄進(jìn)行排序int b10000;for(i=0;i<1000;i+) /直接按關(guān)鍵字散列for(j=ai;bj;j=(j+1)%10000);bj=ai;for(i=0,j=0;i<1000;j+) /將散列收回a中if(bj)for(x=bj,k=j;bk;k=(k+1)%10000)if(bk=x)ai+=x;bk=0;/if/Hash_Sort 10.42 typedef struct int gt; /大于該記錄的個(gè)數(shù) int lt; /小于該記錄的個(gè)數(shù) place; /整個(gè)序列中比某個(gè)關(guān)鍵字大或小的記錄個(gè)數(shù) int Get_Mid(int a ,int n)/求一個(gè)序列的中值記錄的位置place bMAXSIZE;for(i=0;i<n;i+) /對每一個(gè)元素統(tǒng)計(jì)比它大和比它小的元素個(gè)數(shù)gt和ltfor(j=0;j<n;j+)if(aj>ai) bi.gt+;else if(aj<ai) bi.lt+;mid=0;min_dif=abs(b0.gt-b0.lt);for(i=0;i<n;i+) /找出gt值與lt值最接近的元素,即為中值記錄if(abs(bi.gt-bi.lt)<min_dif) mid=i;return mid;/Get_Mid 10.43 void Count_Sort(int a ,int n)/計(jì)數(shù)排序算法int cMAXSIZE;for(i=0;i<n;i+) /對每一個(gè)元素for(j=0,count=0;j<n;j+) /統(tǒng)計(jì)關(guān)鍵字比它小的元素個(gè)數(shù)if(aj<ai) count+:ci=count;for(i=0;i<n;i+) /依次求出關(guān)鍵字最小,第二小,.,最大的記錄min=0;for(j=0;j<n;j+)if(cj<cmin) min=j; /求出最小記錄的下標(biāo)minai<->amin; /與第i個(gè)記錄交換cmin=INFINITY; /修改該記錄的c值為無窮大以便下一次選取/Count_Sort 10.44 void Enum_Sort(int a ,int n)/對關(guān)鍵字只能取v到w之間任意整數(shù)的序列進(jìn)行排序int numberw+1,posw+1;for(i=0;i<n;i+) numberai+; /計(jì)數(shù)for(pos0=0,i=1;i<n;i+)posi=posi-1+numi; /pos數(shù)組可以把關(guān)鍵字的值映射為元素在排好的序列中的位置for(i=0;i<n;i+) /構(gòu)造有序數(shù)組ccposai+=ai;for(i=0;i<n;i+)ai=ci;/Enum_Sort分析:本算法參考了第五章三元組稀疏矩陣轉(zhuǎn)置的算法思想,其中的pos數(shù)組和那里的cpot數(shù)組起的是相類似的作用. 10.45 typedef enum 0,1,2,3,4,5,6,7,8,9 digit; /個(gè)位數(shù)類型typedef digit3 num; /3位自然數(shù)類型,假設(shè)低位存儲在低下標(biāo),高位存儲在高下標(biāo) void Enum_Radix_Sort(num a ,int n)/利用計(jì)數(shù)實(shí)現(xiàn)基數(shù)排序,其中關(guān)鍵字為3位自然數(shù),共有n個(gè)自然數(shù)int number ,pos ;num cMAXSIZE;for(j=0;j<3;j+) /依次對個(gè)位,十位和百位排序for(i=0;i<n;i+) numberaij+; /計(jì)數(shù)for(pos0=0,i=1;i<n;i+)posi=posi-1+numi; /把關(guān)鍵字的值映射為元素在排好的序列中的位置for(i=0;i<n;i+) /構(gòu)造有序數(shù)組ccposaij+=ai;for(i=0;i<n;i+)ai=ci;/for/Enum_Radix_Sort分析:計(jì)數(shù)排序是一種穩(wěn)定的排序方法.正因?yàn)槿绱?它才能夠被用來實(shí)現(xiàn)基數(shù)排序. 10.46 typedef struct int key; int pos; Shadow; /影子序列的記錄類型 void Shadow_Sort(Rectype b ,Rectype &a ,int n)/對元素很大的記錄序列b進(jìn)行排序,結(jié)果放入a中,不移動(dòng)元素Shadow dMAXSIZE;for(i=0;i<n;i+) /生成影子序列di.key=bi.key;di.pos=i;for(i=n-1,change=1;i>1&&change;i-) /對影子序列執(zhí)行冒泡排序change=0;for(j=0;j<i;j+)if(dj.key>dj+1.key)dj<->dj+1;change=1;/forfor(i=0;i<n;i+) /按照影子序列里記錄的原來位置復(fù)制原序列ai=bdi.pos;/Shadow_Sort15 / 15