快速排序(算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì))

1、快速排序一、問題描述排序是數(shù)據(jù)結(jié)構(gòu)中典型的算法，經(jīng)常有插入排序、選擇排序、快速排序等。本文要求對排序表中的無序數(shù)據(jù)進(jìn)行快速排序，并討論快速排序的改進(jìn)方法(雙倍快速排序、基于歸并的快速排序)，這樣可以對排序進(jìn)行優(yōu)化，提高效率。二、基本要求1、選擇合適的存儲結(jié)構(gòu)建立排序表，并能遍歷表輸出元素。2、編寫快速排序算法，并能夠輸出排序的結(jié)果。快速排序及其改進(jìn)雙倍快速排序和基于歸并的快速排序算法。三、測試數(shù)據(jù)輸入以下數(shù)據(jù)：5、3、7、11、1、9、4、8四、算法思想1、普通快速排序的基本思想：可以運(yùn)用一趟快速排序把序列分成分割成獨(dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對這兩

2、部分記錄繼續(xù)進(jìn)行快速排序，以達(dá)到整個(gè)序列有序。一趟的快速排序是：附設(shè)兩個(gè)指針low和high,它們的初值分別為low和high，設(shè)樞軸記錄的關(guān)鍵字為pivotkey,則首先從high所指位置起向前搜索到第一個(gè)關(guān)鍵字小于pivotkey大的記錄和樞軸記錄互相交換，然后從low所指位置向后搜索，找到第一個(gè)關(guān)鍵字大于pivotkey的記錄和樞軸記錄互相交換，重復(fù)這兩部直至low二high為止。2、雙倍快速排序思想：快速排序的基本思想是基于分支策略的思想。即對于輸入的子序列Llow.high,如果規(guī)模足夠小則直接進(jìn)行排序，否則分三步處理：分解(Divide):設(shè)輸入的序列Llow.High,確定支點(diǎn)元

3、素Llow和LHigh,并使LLow.key=LlHigh.key,然后分解(Divide):將序列Llow.High劃分成三個(gè)子序列LLow.L-l、LL+1.H-1和LH+l.High,使Llow.High中元素的關(guān)系為LLow.L-1LLLL+1.H-1LHLH+1.High。遞歸求解(Conquer)：通過遞歸調(diào)用快速排序算法分別對LLow.L-l、LL+1.H-1和LH+l.High分別進(jìn)行分解排序。合并(Merge)：對分解出的三個(gè)子序列的排序是就地進(jìn)行的,所以在LLow.L-l、LL+1.H-1和LH+l.High都排好序后不需要執(zhí)行任何計(jì)算Llow.High就已排好序。3、基于

4、歸并的快速排序：對劃分結(jié)果產(chǎn)生的兩個(gè)子序列的長度進(jìn)行檢查，如果其中一個(gè)與另一個(gè)的長度比超過某一界限，則認(rèn)為這是一個(gè)“畸形劃分”，對較短的子序列繼續(xù)使用“快速排序”，而把較長的子序列平分為兩個(gè)子序列分別排序，然后再進(jìn)行一次合并。兩個(gè)有序序列的合并是可以實(shí)現(xiàn)為線性的時(shí)間復(fù)雜度的，因此可以在每次都是畸形劃分時(shí)仍然獲得0(N*LogN)的時(shí)間復(fù)雜度。其中Partition就是眾所周知的用于“快速排序的劃分子程序，Merge(Data,First,Size)把Data中0,First)和First,Size)兩個(gè)有序列合并為一個(gè)有序序列并存放在Data中。Partition劃分的位置M處的值就是劃分的樞

5、值，也就是說序列可以分成O,M-1、M,M和M+l,Size-l三部分。如果Partition的實(shí)現(xiàn)不能保證這一點(diǎn)，則MoreData應(yīng)為DataM，而MoreSize也應(yīng)為Size-M。(五、模塊劃分1、voidCreate(SqList*L)，建立排序表。2、voidTraverse(SqListL)，遍歷排序表(輸出哨兵)。3、voidswap(int*a,int*b)，用于交換兩個(gè)數(shù)。4、intPartition(SqList*L,intlow,inthigh)，將一個(gè)序列劃分成兩個(gè)子序列，后一子序列所有值都不大于前一子序列任意值。返回子序列分割處索引。5、voidQSort1(SqL

6、ist*L,intlow,inthigh)，調(diào)用快排函數(shù)進(jìn)行排序。6、intQSort2(SqList*L,intlow,inthigh)，調(diào)用雙倍快排函數(shù)進(jìn)行排序。7、voidMerge(RedTypeSR,RedTypeTR,inti,intm,intn),兩個(gè)有序序列合并為一個(gè)有序列序。8、voidMSort(RedTypeSR,RedTypeTR1,ints,intt),歸并排序。9、intqsort1(SqList*L,intlow,inthigh)，快速排序。10、voidmenu，輸出時(shí)清晰。11、intmain(),主函數(shù)。六、數(shù)據(jù)結(jié)構(gòu)ey)；L-length=n;/*遍歷排序

7、表(輸出哨兵)*/voidTraverse(SqListL)inti;for(i=1;ir0=L-rlow;pivotkey=L-rlow.key；while(lowhigh)while(lowrhigh.key=pivotkey)high-；L-rlow=L-rhigh；while(lowrlow.keyrhigh=L-rlow；L-rlow=L-r0；Traverse(*L)；/*每一趟的輸出*/(printf(n)；returnlow；/*快速排序函數(shù)*/voidQSort1(SqList*L,intlow,inthigh)intpivotloc；/*設(shè)置樞軸*/if(lowhigh|l

8、ow=high)return1；if(L-rlow.keyL-rhigh.key)/*確保區(qū)間內(nèi)第一個(gè)元素的值不大于區(qū)間內(nèi)最后一個(gè)元素的值*/swap(&L-rlow.key,&L-rhigh.key)；Ls=low；Hs=high；for(i=low+1；iri.keyL-rhigh.key)Hs-；swap(&L-ri.key,&L-rHs.key)；/*交換兩數(shù)*/i-；/*下一個(gè)比較位置不變*/n-；/*循環(huán)次數(shù)減1*/swap(&L-rLs.key,&L-rlow.key)；/*交換兩數(shù)*/swap(&L-rHs.key,&L-rhigh.key)；/*交換兩數(shù)*/Traverse(

9、*L)；/*每一趟的輸出*/printf(n)；QSort2(L,low,Ls-l)；/*對分解后的第一部分遞歸快速排序*/QSort2(L,Ls+l,Hs-l)；/*對分解后的第二部分第歸快速排序*/QSort2(L,Hs+l,high)；/*對分解后的第三部分第歸快速排序*/return0；%/*基于歸并的快速排序*/voidMerge(RedTypeSR,RedTypeTR,inti,intm,intn)/*調(diào)用歸并函*/intj,k；/*定義兩數(shù)*/for(j=m+1,k=i;i=m&j=n;+k)ifLQ(SRi.key,SRj.key)TRk=SRi+；elseTRk=SRj+；i

10、f(i=m)while(k=n&i=m)TRk+=SRi+；if(j=n)while(k=n&jhigh)return1；k=Partition(L,low,high)；f=k-low；s=high-k；if(fs&s!=0)r=f/s;/*檢查其中一個(gè)子序列與另一個(gè)的長度比是否超過某一界限*/elseif(f!=0)r=s/f;if(rM)mid=(k-l-low)/2+s；/*較長的子序列平分為兩個(gè)子序列*/QSort1(L,s,mid);/*此時(shí)進(jìn)行快速排序*/|QSort1(L,mid+1,k-1)；MSort(L-r,L-r,mid,k-1)；mid=(f-k-1)/2+k+1；QS

11、ort1(L,k+1,mid)；QSort1(L,mid+1,f)；MSort(L-r,L-r,mid,f)；Traverse(*L)；printf(n)；elseQSort1(L,low,high)；return0；voidmenu()SqListL；intx；【printf(n08課程設(shè)計(jì)快速排序算法演示n)；printf(nl快速排序算法n);printf(n2雙倍快速排序算法n);printf(n3基于歸并的快速排序算法n);printf(n4退出演示n);scanf(%d,&x);switch(x)/*調(diào)用switch語句進(jìn)行輸出*/case1:printf（n普通快速排序n）;Cr

12、eate(&L);QSort1(&L,1,;break;case2:printf(n雙倍快速排序n)；Create(&L);QSort2(&L,1,；break；case3:printf(n基于歸并改良的快速排序n)；Create(&L)；qsort1(&L,1,；break；case4:printf(n演示結(jié)束n);break；default：printf(n輸入有錯(cuò)n);/*主函數(shù)*/intmain()menu();system(pause);return1;八、測試情況程序的測試結(jié)果如下：1、快速排序結(jié)果：2、雙倍快速排序運(yùn)行結(jié)果正確經(jīng)驗(yàn)證，手工運(yùn)算也對。3、基于歸并的快速排序運(yùn)行正確，

13、結(jié)果也正確。九、參考文獻(xiàn)1、嚴(yán)蔚敏，數(shù)據(jù)結(jié)構(gòu)C語言，清華大學(xué)出版社。2、譚浩強(qiáng)，c語言程序設(shè)計(jì)，清華大學(xué)出版社。小結(jié)經(jīng)過一年的數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)，對于程序編寫的算法及其應(yīng)用有了一定的了解和掌握，并且能夠在一些方面將其運(yùn)用。這次的課程設(shè)計(jì)是關(guān)于快速排序以及其的一些改進(jìn)方法的設(shè)計(jì)。雖然這次的課程設(shè)計(jì)并沒有真正的涉及生活工作中的應(yīng)用，但是我們通過本次的數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計(jì)，了解并知道了一些調(diào)試程序的方法，而且學(xué)會了一些處理錯(cuò)誤的方法。這次的課程設(shè)計(jì)使得我們對數(shù)據(jù)結(jié)構(gòu)有了進(jìn)一步的掌握，并是的我們對VC+的運(yùn)用更加的熟悉。經(jīng)歷了這次課程設(shè)計(jì)，不僅僅是對我們的學(xué)習(xí)提供了幫助，也同時(shí)對我們的意志力進(jìn)行了一次鍛煉。沒

14、有足夠的耐心就會剛編輯一點(diǎn)程序或者出個(gè)錯(cuò)誤找不到就會不耐煩，從而導(dǎo)致接下來的工作無法進(jìn)行而被迫暫時(shí)擱置，最終使得課程設(shè)計(jì)的完成效率大大降低?？焖倥判蛩惴ǖ淖詈脮r(shí)間O(nlogn)平均時(shí)間O(N*LogN)最壞時(shí)間O(N2)穩(wěn)定性一不穩(wěn)定解釋：在所有同數(shù)量級O(N*LogN)的排序方法中，快速排序被認(rèn)為是平均性能最好的一種；但是，若初始記錄序列按關(guān)鍵字逆序或基本有逆序時(shí)，快速排序則蛻化為冒泡排序，此時(shí)，算法的時(shí)間復(fù)雜度為O(N2)。從時(shí)間上看快速排序平均性能優(yōu)于書上的各種排序吧，但是也存在缺點(diǎn)，上面提到的雙倍快速排序和基于歸并的快速排序剛好彌補(bǔ)了這一瑕疵，從中找到不足使快排更快。同時(shí)經(jīng)過這次課程

15、設(shè)計(jì)我們領(lǐng)略到分工合作精神，集體編程和個(gè)人編程有很大不同，相互間獨(dú)立而又緊密聯(lián)系在一起，我們每個(gè)人都是獨(dú)立的個(gè)體，我們可以獨(dú)立的查找資料來獨(dú)立的編輯一個(gè)程序，然而我們也可以互相研討而一起完成一個(gè)程序。相對來說獨(dú)立的個(gè)人畢竟一個(gè)人的能力是有限的，而通過團(tuán)隊(duì)合作我們就可很好的完成一個(gè)人完成起來比較困難的工作，這種合作就使得我們的設(shè)計(jì)相對來說輕松了不少。這次的課程設(shè)計(jì)不僅僅是使我們有了上面的收獲，同時(shí)也使我們深刻的認(rèn)識到自己專業(yè)知識的匱乏，以及獨(dú)立完成程序設(shè)計(jì)的能力上的不足。通過這次的課程設(shè)計(jì)，我們認(rèn)識到了自我的不足還有很多，因此我們在接下來的時(shí)間里將會更加努力的去學(xué)習(xí)和應(yīng)用，以提高自身的專業(yè)技能和實(shí)際能力，自強(qiáng)