數(shù)據(jù)結(jié)構(gòu)(c語(yǔ)言版)題集答案-第十章內(nèi)部排序

1、數(shù)據(jù)結(jié)構(gòu)（c語(yǔ)言版）題集答案-第十章-內(nèi)部排序第十章內(nèi)部排序10.23void Insert_Sortl (SqList &L)監(jiān)視哨設(shè)在高下標(biāo)端的插入排序算法k=L. length;for(i=k-l;i;i) 從后向前逐個(gè)插入排序 if(L.ri.key>L.ri+l.key) L.rk+l.key=L.rEi.key; 監(jiān)視哨 for(j=i+l;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. 24void BiI

2、nsert_Sort (SqList &L) 二路插入排序的算法int dMAXSIZE ; /輔助存儲(chǔ) x=L. r . key; d =x; first=l ;final=l;for(i=2;i<=L. length;i+) if (L. r i. key>=x) 插入前部for (j=final; dj >L. r i. key; j) dj+l=dj;dj+l=L. ri.key; final+; else 插入后部for(j=first;djdj-l=dj;d(j-2)%MAXSIZE+l=L. ri. key;first=(first-2)%MAXSIZE

3、+l; 這種形式的表達(dá)式是為了兼顧first=l的情 況 /forfor(i二first, j=l;di;i=i%MAXSIZE+l, j+)將序列復(fù)制回去L. rj. key=dEi; /BiInsert_Sort 10. 25void SLInsert_Sort (SLList &L) 靜態(tài)鏈表的插入排序算法L. r0. key=0;L. r L0. next=l;L. rl. next=0; /建初始循環(huán)鏈表 for (i=2; i<=L. length; i+) 逐個(gè)插入p=0;x=L. ri. key;while(L. rEL. rLp. next. keyp=L. r

4、Lpj. next; q=L. rip, next; L. rLp. next=i;L.ril.next=q; /forp=L. r0. next; for(i=l;iwhile(pq=L. rEp. next; if(p!=i) L. rpjL. rEi ; L. rLi. next=p; p=q; /for/SLInsert_Sort 10. 26void Bubble_Sortl(int a ,int n)對(duì)包含n個(gè)元素的數(shù)組a進(jìn)行改進(jìn)的冒泡排 序changefl; "change指示上一趟冒泡中最后發(fā)生交換的元素while (change) for (c=0, i=0; ii

5、f (ai>ai+l) c=i+1; /c指示這一趟冒泡中發(fā)生交換的元素change二c; /while/Bubble_Sortl 10. 27void Bubble_Sort2(int a int n)相鄰兩趟是反方向起泡的冒泡排序算法(low=0;high=n-l; /冒泡的上下界 change=l; while(low change=0;for (i=low; iif (ai>ai+l) change；high一; 修改上界for (i=high;i>low; i-) /從下向上起泡 if (ai change；low+; 修改下界/while)/Bubble.Sort

6、2 10. 28void Bubble_Sort3(int a ,int n)對(duì)上一題的算法進(jìn)行化簡(jiǎn)，循環(huán)體中只包含一 次冒泡int b 3 ; b0為冒泡的下界,b 2 為上界,b無(wú)用d=l;bO=O;b 2 =n-l; d為冒泡方向的標(biāo)識(shí),1為向上1為向下changed; while(b0 change：。；for(i=bl-d ;i!=bl+d ;i+=d) /統(tǒng)一的冒泡算法 if (ai-ai+d)*d>0) /注意 這個(gè)交換條件aiai+d; change=l; bl+d-二d; 修改邊界 d*=-l; /換個(gè)方向/while/Bubble_Sort3 10.29void 0E

7、_Sort (int aE , int n) 奇偶交換排序的算法(change=l;while (change) change=0;for(i=l;iif(aLi>aLi+lJ) change=l; for(i=0;iif(ai>aCi+l) aiai+l;change=l; /while /0E_Sort分析:本算法的結(jié)束條件是連續(xù)兩趟比較無(wú)交換發(fā)生10. 30typedef struct int low; int high; boundary; 子序列的上下界類型void QSort_NotRecurve (int SQList &L)快速排序的非遞歸算法low=l;h

8、igh二L. length;InitStack(S) ; S 的元素為 boundary 類型 while (lowif(high-low>2) 如果當(dāng)前子序列長(zhǎng)度大于3旦尚未排好序pivot=Partition(L, low, high); 進(jìn)行一趟劃分 if (high-pivot>pivot-low) Push(S, pivot+l, high); 把長(zhǎng)的子序列邊界入棧high=pivotT; 短的子序列 留待下次排序)else Push(S, low, pivotal); low=pivot+l; /ifelse if(low(Easy_Sort (L, low, high

9、); 直接進(jìn)行比較排序low二high; 當(dāng)前子序列標(biāo)志為己排 好序1else 如果當(dāng)前子序列已排好序但棧中還有未排序的子序列Pop(S, a); 從棧中取出一個(gè)子序列 low=a. low; high=a. high; /while/QSort_NotRecurveint Partition(SQList &L, int low, int high)一趟劃分的算法，與書上相同L. r 01=L. r low;pivotkey=L. rElow, key; while(lowwhiledow=pivotkey) high-;L. rlow=L. rhigh; while(lowlow+

10、; L. rEhigh=L. rLlowJ; /whileL. rlow=L. rEO; return low; /Partitionvoid Easy_Sort (SQList &L, int low, int high)對(duì)長(zhǎng)度小'3 的子序列進(jìn)行比較排 序if (high-low=l) 子序列只含兩個(gè)元素if (L. rlow. key>L. rhigh, key) L. rlowL. rhigh ; else 子序列含有三個(gè)元 素if (L. rlow. key>L. rlow+11. key) L. r lowL. rlow+1;if (L. r llow+1. key>L. rhigh. key) L. r E1ow+1L. rhigh;if (L. rlow. key>L. r low+1. key) L. rlowL. rlow+l ; void Divide(int a , int n)把數(shù)組a中所有值為負(fù)的記錄調(diào)到非負(fù)的記錄之前l(fā)ow=0;high=n-l; while(lowwhile (low=0) high; 以 0 作為虛擬的樞軸記錄 a low a high;while (Iowa low a high ; /Divide 10. 32type