內(nèi)部排序及改進(jìn)(算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì))

1、wilyesll收集博客（與學(xué)習(xí)無關(guān)）：.en/u/1810231802內(nèi)部排序及改進(jìn)一、問題描述排序是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，它的功能是將一個(gè)數(shù)據(jù)元素或記錄的任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列。排序分有很多種方法，有插入排序，快速排序，選擇排序，歸并排序，基數(shù)排序等，本次課程設(shè)計(jì)中討論幾種簡(jiǎn)單的排序算法，并對(duì)其進(jìn)行改進(jìn)。二、基本要求1、選擇合適的存儲(chǔ)結(jié)構(gòu)并建立排序表；2、設(shè)計(jì)冒泡排序算法，并對(duì)其進(jìn)行改進(jìn)，輸出排序結(jié)果；3、設(shè)計(jì)快速排序算法，并對(duì)其進(jìn)行改進(jìn)，輸出排序結(jié)果；4、設(shè)計(jì)簡(jiǎn)單選擇排序，并對(duì)其進(jìn)行改進(jìn)，輸出排序結(jié)果。三、測(cè)試數(shù)據(jù)對(duì)各種排序測(cè)試，測(cè)試用例如：49,38,65

2、，97，76,13,27,50四、算法思想1、冒泡排序及其算法改進(jìn)1）冒泡排序首先將第一個(gè)記錄的關(guān)鍵字和第二個(gè)記錄的關(guān)鍵字進(jìn)行比較，若為逆序（即L.r1.keyL.r2.key）,則將兩個(gè)記錄交換之，然后比較第二個(gè)記錄和第三個(gè)記錄的關(guān)鍵字，依此類推，直至第n-1個(gè)記錄和第n個(gè)記錄的關(guān)鍵字進(jìn)行過比較為止，稱第一趟冒泡排序，然后進(jìn)行以后幾趟的冒泡排序直到在一趟排序的過程中沒有進(jìn)行過交換記錄的操作。2）冒泡排序的改進(jìn)算法首先從前往后掃描，如果相鄰兩個(gè)元素前面的比后面的大，則交換，繼續(xù)往后；到尾部以后，再往回走，如果后面的元素比前面的小，則交換，繼續(xù)往前走；到了頭以后，再往后走。為了減少走動(dòng)次數(shù)，我們

3、用變量start表示頭，用變量end表示尾。每找到一個(gè)剩余數(shù)據(jù)中的最大數(shù)，就讓變量end減1,每找到一個(gè)剩余數(shù)據(jù)中的最小數(shù)，就讓變量start加1。循環(huán)條件為start=end。2、快速排序及其算法改進(jìn)1）一趟快速排序的具體做法是附設(shè)兩個(gè)指針low和high，設(shè)樞軸記錄的關(guān)鍵字為pivotkey,則首先從high所指的位置起向前搜索找到第一個(gè)關(guān)鍵字小于pivotkey的記錄和樞軸記錄互相交換，然后從low所指位置起向后搜索，找到第一個(gè)關(guān)鍵字大于pivotkey的記錄和樞軸互相交換，重復(fù)這兩步直至low二high為止?？焖倥判虻幕舅枷胧峭ㄟ^一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩個(gè)部分，其中一部分記錄

4、的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序。2）快速排序改進(jìn)算法：雙倍快速排序，對(duì)于輸入的子序列，如果規(guī)模足夠小則直接排序，否則分三步：第1步是將輸入序列分成2部分L.low.mid-1和L.mid+1.end。并使前一部分記錄小于第二部分的記錄；第2步對(duì)兩部分分別進(jìn)遞歸排序；第3步將排序好的兩部分進(jìn)行合并。3、簡(jiǎn)單的選擇排序及其算法改進(jìn)1）簡(jiǎn)單的選擇排序是在每一趟中在n-i+1（i=1,2,n）個(gè)記錄中選取關(guān)鍵字最小的記錄作為有序序列中第i個(gè)記錄。一趟簡(jiǎn)單選擇排序的操作是通過n-i次關(guān)鍵字間的比較，從n-i-1個(gè)記錄中選取關(guān)鍵字最小的記錄，并和

5、第i個(gè)記錄交換之。2)二元選擇排序：記錄初始和最終位置，遍歷找尋記錄中的最大值和最小值。讓最小值和低位交換，最大值和高位交換。由于在鏈表中操作可能會(huì)出現(xiàn)多次交換了同一值的情況所以要分情況來交換(最小值最大值不在正確位置)：當(dāng)最大值最小值在i，flag時(shí)，只需交換一次。當(dāng)最小值在flag時(shí)，先交換最小值。當(dāng)最大值在i時(shí)，先交換最大值。當(dāng)最大最小值都不在對(duì)應(yīng)位置時(shí)，最小值和i交換，最大值和flag交換。五、模塊劃分voidSwap(int&a,int&b)交換數(shù)據(jù)。voidCreate(SqList*L)建立一個(gè)長(zhǎng)度為n的排序表。voidTraverse(SqListL)遍歷排序表且輸出哨兵。vo

6、idBubbleSort(SqList*L,intsize)建立一個(gè)長(zhǎng)度為size的順序表，每趟冒泡排序依次將前一個(gè)記錄的關(guān)鍵字和后一個(gè)記錄的關(guān)鍵字進(jìn)行比較，若逆序則交換。voidBubbleSort2(SqList*L)建立順序表L,當(dāng)start=end時(shí)依次找到一個(gè)最大數(shù)和一個(gè)最小數(shù)。intPartition(SqList*L,intlow,inthigh)建立順序表L,附設(shè)兩個(gè)指針low和high且賦予初值分別為low和high。voidQSort(SqList*L,intlow,inthigh)對(duì)順序表中的子序列L.rlow.high用遞歸形式作快速排序。voidMerge(SqLis

7、t*L,intstart,intmid,intend)建立順序表L，附設(shè)三個(gè)指針start,mid和end，內(nèi)部for循環(huán)對(duì)子序列tempi和temp2進(jìn)行比較。voidRecMerge(SqList*L,intstart,intend)用遞歸形式作改進(jìn)的快速排序。voidMergeSort(SqList*L,intsize)合并排序voidSelectSortl(SqList*L)建立順序表L,對(duì)L.r1.n中的記錄進(jìn)行簡(jiǎn)單的選擇排序。voidSelectSort2(SqList*L)建立順序表L,記錄標(biāo)志flag，對(duì)L.r1.n中的記錄進(jìn)行二元選擇排序，找到最小值和最大值的位置，讓最小值與

8、低位交換，最大值與高位交換。voidMainMenue()輸出主要信息。voidmain()主函數(shù)。用switch選擇結(jié)構(gòu)進(jìn)行操作。六、數(shù)據(jù)結(jié)構(gòu)/(ADT)排序表的存儲(chǔ)結(jié)構(gòu)：typedefstructwilyesll收集博客(與學(xué)習(xí)無關(guān))：.en/u/1810231802KeyTypekey;/*關(guān)鍵字項(xiàng)*/RecType;/*記錄類型*/typedefstructRecTyper100;/*r0用作哨兵單元*/intlength;/*順序表長(zhǎng)度*/SqList;/*順序表類型*/七、源程序#includestdio.h#includestdlib.h#defineMAX10000#defin

9、eEQ(a,b)(a)=(b)#defineLT(a,b)(a)(b)#defineLQ(a,b)(a)=(b)/排序表的類型定義typedefintKeyType;typedefstructKeyTypekey;RecType;typedefstructRecTyper100;intlength;SqList;/交換數(shù)據(jù)voidSwap(int&a,int&b)inttemp=a;a=b;b=temp;/排序表的建立voidCreate(SqList*L)inti,n;printf(n請(qǐng)輸入表長(zhǎng)：)；scanf(%d,&n);printf(請(qǐng)輸入d元素:,n);L-r0.key=T00;fo

10、r(i=1;irlow=Lr0;Traverse(*L);returnlow;/遞歸形式的快速排序/將比樞軸大的記錄移動(dòng)到高端/樞軸記錄到位/返回樞軸位置voidQSort(SqList*L,intlow,inthigh)intpivotloc;if(lowrstart+i;for(i=0;irmid+i+1;temp1n1.key/長(zhǎng)度大于1/將記錄一分為二/對(duì)低子表遞歸排序，pivotloc是樞軸的位置/對(duì)高子表遞歸排序intmid,intend)/將原記錄分成兩部分的第一段長(zhǎng)度/將原記錄分成兩部分的第二段長(zhǎng)度/將第一段里的元素存儲(chǔ)到temp1i/將第二段里的元素存儲(chǔ)到temp2itemp

11、2n2.key二MAX;/每段元素為賦最大值i=j=0;for(k=start;krk=temp1i;/比較兩段里面的元素使基本有序i+;elseLrk=temp2j;j+;/遞歸形式進(jìn)行排序voidRecMerge(SqList*L,intstart,intend)inti;if(startend)i=(start+end)/2;/取mid值RecMerge(L,start,i);/對(duì)前一段排序RecMerge(L,i+1,end);/對(duì)后一段排序Merge(L,start,i,end);/合并排序Traverse(*L);/合并排序voidMergeSort(SqList*L,intsiz

12、e)RecMerge(L,0,size);Traverse(*L);/簡(jiǎn)單選擇排序voidSelectSortl(SqList*L)inti,j,min;for(i=0;ilength;i+)/選擇第i小的記錄min=i;for(j=i+1;jlength;j+)if(LT(L-rj.key,L-rmin.key)min=j;/在L.i.L.length中選擇最小的記錄Swap(L-ri.key,L-rmin.key);/與第i個(gè)交換Traverse(*L);/簡(jiǎn)單選擇排序的改進(jìn):二元選擇排序voidSelectSort2(SqList*L)inti,j,min,max,flag;flag=0

13、;intn二Llength;flag二L-length;for(i=1;i二int(n/2);i+)min=i;max=i;for(j=i+1;j=max&max!=i)Swap(L-rmin.key,L-ri.key);Swap(L-rmax.key,L-rflag.key);elseSwap(L-rmax.key,L-rflag.key);Swap(L-rmin.key,L-ri.key);elseSwap(L-rmax.key,L-rmin.key);flag-;/將最大值最小值放入指定位置Traverse(*L);/菜單voidMainMenue()fflush(stdin);prin

14、tf(n*MainMenue*n);printf(*n)printf(*1.BubbleSort*n)printf(*2.BubbleSort2*n)printf(*3.QSort*n)printf(*4.MergeSort*n)printf(*5.SelectSortl*n)printf(*6.SelectSort2*n)printf(*7.Exit.*n)printf(*n)r-I-tI1rIlliIIIIJ/主函數(shù)voidmain()intflag=1;charch10;SqListL;Create(&L);while(flag)MainMenue();printf(Pleaseinpu

15、tyourchoice(l7):);gets(ch);switch(chO)case1:BubbleSort(&L,L.length);exit(O);case2:BubbleSort2(&L);exit(0);，o?case3:QSort(&L,l,L.length);exit(O);case4:MergeSort(&L,L.length);exit(O);case5:SelectSortl(&L);exit(0);case6:SelectSort2(&L);exit(0);case7:exit(O);default:printf(Inputerror!n);break;八、測(cè)試情況程序的測(cè)

16、試結(jié)果如下：冒泡排序：冒泡改進(jìn)算法:快速排序:J1快速排序改進(jìn)算法:E:MicrosoftVisualStudioMyProjectssortDebugSort.exe請(qǐng)攢人表卡：8請(qǐng)輸人8元素:4938659776132750*1.BubbleSort*2.BubbleSort2*3.QSort*4.MergeSort*5.SelectSortl*6.SelectSort2*7.Exit.*Pleaseinputyourchoice:44938G5977G13275038496597761327503849G59?7G13275038496597761327503849G5971376275

17、038496597137627503849G5971327507613273849506576971327384950G57697Pressanykeytocontinue選擇排序:wilyesll收集博客（與學(xué)習(xí)無關(guān)）：.en/u/1810231802E:MicrosoftVisualStudioMyProjectssortDebugSort.exe朝L兀請(qǐng)輸.A曷胡0bb7b1JZ/“WWWWWWM-：M.MMMKXM：KMKXMMMK1net丄urieiiLit:*1.BubbleSort*2.BubbleSort2*3.QSort*：4.MergeSo片七*5.SelectSoitl*

18、：6.SelectSoi*t2*7.Exit.*Pleaseinputyourchoice:54938G597761327501338G597764927501327659776493850132738977649G5501327384976976550C-100）132738495097G576132738495065977613273849506576971327384950G57697Pressanykeytocontinue.選擇排序改進(jìn)算法:測(cè)試結(jié)果均正確。九、參考文獻(xiàn)1、嚴(yán)蔚敏，數(shù)據(jù)結(jié)構(gòu)c語言清華大學(xué)出版社。2、譚浩強(qiáng)，c語言程序設(shè)計(jì)，清華大學(xué)出版社。小結(jié)通過本次課程設(shè)計(jì)，我學(xué)到了

19、很多知識(shí)，編寫一個(gè)程序不像想象中的簡(jiǎn)單，它不僅要求編程人員有非常縝密的思維，很好的整體把握能力和調(diào)試程序的能力以及編寫程序過程中的所有細(xì)節(jié)問題，一般程序的整體思路和整體算法都知道，但往往調(diào)試部成功就是因?yàn)槟承┘?xì)節(jié)之處的錯(cuò)誤，這時(shí)就會(huì)意識(shí)到團(tuán)體合作的精神很重要。常說細(xì)節(jié)決定成功，我在次此課程設(shè)計(jì)中深有體會(huì)，多一個(gè)或少一個(gè)分號(hào)或者括號(hào)整個(gè)程序就會(huì)運(yùn)行不出來，而這些往往是編程時(shí)最容易犯的錯(cuò)誤，這需要一個(gè)很細(xì)心的過程才能檢查出來。同時(shí)我也認(rèn)識(shí)到編譯工具的重要性，這次我們用的是VC+6.0環(huán)境，它提高了我編寫程序的效率，如按回車后，它能自動(dòng)空出一定距離，體現(xiàn)出程序的結(jié)構(gòu)，不用人工輸入空格、制表符，還有它

20、的調(diào)試功能，不用我人工輸出中間變量來查錯(cuò)，就能看到中間變量，還有程序?qū)懞眠\(yùn)行時(shí)有錯(cuò)誤的話它會(huì)顯示你哪行有錯(cuò)誤或有什么錯(cuò)誤,大大提高了編程的效率等等象此次的冒跑排序在以前的C語言中就學(xué)過，那時(shí)只是用簡(jiǎn)單的C語言語法借助一個(gè)for循環(huán)就可以完成，現(xiàn)在基本思路還是以前的但借助一個(gè)Swap函數(shù)，使程序看起來簡(jiǎn)單一點(diǎn)。它的改進(jìn)算法看上去沒有多大改進(jìn)，但對(duì)于不連續(xù)的一組數(shù)來說時(shí)間復(fù)雜度變小了，也節(jié)省了算法空間。整個(gè)所有的程序就是用不同的算法思想將一組雜亂無章的數(shù)藉助“交換”來進(jìn)行排序使之有序。算法的實(shí)現(xiàn)需要哪些變量，中間算法又需要哪些中間變量，這些沒有一定的編程語言的基礎(chǔ)和編程語言的經(jīng)驗(yàn)是很難完成的。在此次課程設(shè)計(jì)中我認(rèn)識(shí)到分工合作的精神很重要，集體編程和個(gè)人編程有很大不同，每個(gè)人負(fù)責(zé)編寫不同的程序，相互獨(dú)立又緊密結(jié)合在一起才有了最后的成功。像我負(fù)責(zé)寫的是選擇排序及其改進(jìn)算法，簡(jiǎn)單的選擇排序很簡(jiǎn)單，就是通過n-i次關(guān)鍵字間的比較，從n-i+1個(gè)記錄中選出關(guān)鍵字最小的記錄，并和第i個(gè)記錄交換，共要比較n(n-l)/2次，我就想選擇排序的主要操作是進(jìn)行關(guān)鍵字間的比較，因此改進(jìn)算法因從如何減少“比較”出發(fā)考慮。所以我采用了二元選擇排序，使其時(shí)間復(fù)雜度變小了。程序雖是獨(dú)立寫的但