1、1緒論快速排序(quicksort)是分治(divideandconquer)法的一個典型例子。快速排序(Quicksort)是對冒泡排序的一種改進。由C.A.R.Hoare在1962年提出。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。快速排序算法具有良好的平均性能,因此它在實際中常常是首選的排序算法。本次任務主要以快速排序算法實現對任意數字序列的排序，并解決書本P59頁2-26問題：試說明如何修改快速排序算法，使它在最壞情

2、況下的計算時間為0210gn)所選編程語言為C語言。2快速排序算法2.1 快速排序算法簡介快速排序算法是基于分治策略的排序算法。即對于輸入的子數組ap:r,按以下三個步驟進行排序。(1)分解：以ap為基準元素將ap:r劃分成3段ap:q-1,aq和aq+1:r,使ap:q-1中任何一個元素小于等于aq，而aq+1:r中任何一個元素大于等于aq。下標q在劃分過程中確定。(2)遞歸求解：通過遞歸調用快速排序算法分別對ap:q-1和aq+1:r進行排序。(3)合并：由于對ap:q-1和aq+1:r的排序是就地進行的，所以在ap:q-1和aq+1:r都已排好的序后，不需要執行任何計算，ap:r就已排好

3、序。2.2 快速排序算法流程圖圖1快速排序算法流程圖2.3 快速排序算法的算法實現第一趟處理整個待排序列，選取其中的一個記錄，通常選取第一個記錄，以該記錄的關鍵字值為基準，通過一趟快速排序將待排序列分割成獨立的兩個部分，前一部分記錄的關鍵字比基準記錄的關鍵字小，后一部分記錄的關鍵字比基準記錄的關鍵字大，基準記錄得到了它在整個序列中的最終位置并被存放好，這個過程稱為一趟快速排序。第二趟即分別對分割成兩部分的子序列再進行快速排序，這樣兩部分子序列中的基準記錄也得到了最終在序列中的位置并被存放好，又分別分割出獨立的兩個子序列。這是一個遞歸的過程，不斷進行下去，直至每個待排子序列中都只有一個記錄是為止

4、,此時整個待排序列已排好序,排序算法結束。快速排序的過程：(1)初始化。取第一個記錄作為基準，設置兩個整型指針i,j,分別指向將要與基準記錄進行比較的左側記錄位置和右側記錄位置。最開始從右側比較，當發生交換操作后，再從左側比較。(2)用基準記錄與右側記錄進行比較。即與指針j指向的記錄進行比較，如果右側記錄的關鍵字值大，則繼續與右側前一個記錄進行比較，即j減1后,再用基準元素與j所指向的記錄比較，若右側的記錄小，則將基準記錄與j所指向的記錄進行交換。(3)用基準記錄與左側記錄進行比較。即與指針i指向的記錄進行比較，如果左側記錄的關鍵字值小，則繼續與左側后一個記錄進行比較，即i加1后,再用基準記錄

5、與i指向的記錄比較，若左側的記錄大，則將基準記錄與i指向的記錄比較。(4)右側比較與左側比較交替重復進行，直到指針i與j指向同一位置，即指向基準記錄最終的位置。可實現的快速排序算法如下：voidQuickSort(inta,intp,intr)(if(P<r)(intq=Partition(a,p,r);QuickSort(a,p,q-1);QjickSort(a,q+1,r);)對含有n個元素的數組a0;n-1進行快速排序只要調用QuickSort(a,0,n-1)即可。上述算法中的函數Partition，以確定的一個基準元素ap對子數組ap:r進行劃分，它是快速排序算法的關鍵。int

6、Partition(inta,intp,intr)inti=p,j=r+1;intx=ap;while(true)while(a+i<x&&i<r);while(a-j>x);if(i>=j)break;Swap(ai,aj);)ap=aj;aj=x;returnj;)Partition對ap:r進行劃分時，以元素x=ap作為劃分的基準，分別從左、右兩端開始，擴展兩個區域ap:i和aj:r,使ap:i中元素小于或等于x,而aj:r中元素大于或等于x。初始時，i=p,且j=r+1。在while循環體中，下標j逐漸減小，i逐漸增大，直到ai>=x>

7、;=aj。此時若i<j,就應該交換ai與aj的位置，擴展左右兩個區域。while循環重復至i>=j時結束。這時ap:r已被劃分成ap:q-1,aq和aq+1:r,且滿足ap:q-1中元素不大于aq+1:r中元素。在Partition結束時返回劃分點q=j3程序運行運行程序，任意輸入一個亂序數組，例如:5418956112374614運行得到排序后的結果如下圖:4問題解答完全保證使快速排序算法在最壞情況下的計算時間為5n10gn)是很困難的,但可以采用一些辦法來消除算法的退化結構，比如課本上的隨機選擇策略等。鑒于在平時生活中的數據排序，其數據往往帶有規律性。在中值的選擇策略上，我們比

8、較一下第一個，最后一個，以及中間一個的值，以這3個值中位于中間的那個來進行劃分，這樣就能使快速排序避免了大多數的最壞情況，即使是對于兩邊小中間大的特殊情況，這個方法也有其作用一一在第一遍排序時打亂這個特殊情況。因此，這個算法在實際運用中是比較好的一種快速排序，修改程序如下：template<classType>intpartition(Typea,intp,intr)inti=p,j=r+1;Typex=ap;while(1)while(a+i<x);while(a-j>x);if(i>=j)break;Swap(ai,aj);ap=aj;aj=x;returnj

9、;intBalancePartion(Typea,intp,intr)inti,m;m=(p+r)/2;switch(1)case(ap<=am&&ap>=ar)|(ap>=am&&ap<=ar):i=p;break;case(am<=ap&&am>=ar)|(am>=ap&&am<=ar):i=m;break;case(ar<=am&&ar>=ap)|(ar>=am&&ar<=ap):i=r;break;Swap(ai,ap)

10、;returnPartition(a,p,r);voidBalanceQuickSort(Typea,intp,intr)if(p<r)intq=BalancePartition(a,p,r);BalanceQuickSort(a,p,q-1);BalanceQuickSort(a,q+1,r);5課程設計總結及心得課程設計是培養學生綜合運用所學知識，發現，提出，分析和解決實際問題，鍛煉實踐能力的重要環節，是對學生實際工作能力的具體訓練和考察過程.回顧此次快速排序算法演示課程設計，至今我仍感慨頗多，的確，從選題到定稿，從理論到實踐，在整整兩星期的日子里，可以說得是苦多于甜，但是可以學到很多很多的的東西，同時不僅可以鞏固了以前所學過的知識，而且學到了很多在書本上所沒有學到過的知識。在做程序的過程中遇到了很多問題，有的是知識存儲不足，有的是考慮不夠周全，之所以能夠順利實現基本功功能，離不開老師和同學的大力相助。止匕外，通過這次課程設計使我懂得了理論與實際相結合是很重要的，只有理論知識是遠遠不夠的，只有把所學的理論知識與實踐相結合起來，從理論中得出結論，才能真正為社會服務，從而提高自己的實際動手能力和獨立思考的能力。6參考文獻1王曉東.算法設計與分析（第二版）.北京：清華大學出版社