快速排序詳析的設(shè)計

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告（2015）數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告快速排序詳析的設(shè)計專業(yè)計算機科學(xué)與技術(shù)學(xué)生姓名班級學(xué)號指導(dǎo)教師完成日期目 錄1. 設(shè)計內(nèi)容11.1 排序基本知識11.2 快速排序算法介紹11.3 設(shè)計題目22. 設(shè)計分析32.1 快速排序的分析32.2 系統(tǒng)流程圖設(shè)計42.3 系統(tǒng)的詳細設(shè)計53. 設(shè)計實踐63.1 開發(fā)環(huán)境63.2 快速排序過程73.3 調(diào)試過程83.4 代碼實現(xiàn)114. 測試方法154.1 測試方案154.2 測試結(jié)果155. 程序運行效果156. 設(shè)計心得19參考文獻20快速排序詳析的設(shè)計1. 設(shè)計內(nèi)容 1.1 排序基本知識排序（Sorting）是計算機程序設(shè)計的一種

2、重要操作，它的功能是將一組任意順序數(shù)據(jù)元素（記錄），根據(jù)某一個（或幾個）關(guān)鍵字按一定的順序重新排列成為有序的序列。由于待排序的記錄數(shù)量不同，使得排序過程中涉及的存儲器的不同，可將排序方法分為兩大類：一類是內(nèi)部排序，指的是待排序的記錄存放在計算機隨機存儲器中進行的排序過程；另一類是外部排序，指的是待排序記錄的數(shù)量很大，以致內(nèi)存一次不能容納全部記錄，在排序過程中尚需要對外在進行訪問的排序過程。內(nèi)部排序的方法有很多，但就其全面性能而言，很難提出一種被認為是最好的方法，每一種方法都有各自的優(yōu)缺點，適合在不同的環(huán)境下使用。按照其策略不同，可歸納為五類：插入排序、交換排序、選擇排序、歸并排序和基數(shù)排序。1

3、.2 快速排序算法介紹快速排序就像它的名稱所暗示的，是一種快速的分而治之的算法，平均時間復(fù)雜度為O(nlog2n)。它的速度主要歸功于一個非常緊湊并且高度化的內(nèi)部循環(huán)。其基本算法Quicksort(S)由以下四個步驟組成：(1)如果S中的元素的數(shù)目為0或1，則返回。(2)選擇S中的任意一個元素v，v叫做支點(Pivot)。(3)將S-v（剩下的元素在S中）分成兩個分開的部分。L=x屬于S-v|x<=v和R=x屬于S-v|x>=v。(4)依次返回Quicksort(L)、v和Quicksort(R)的結(jié)果。基本的快速排序算法可以應(yīng)用遞歸實現(xiàn)。關(guān)鍵的細節(jié)包括支點的選擇如何分組。該算法允

4、許把任何元素作為支點。支點把數(shù)組分為兩組：小于支點的元素集和大于支點的元素集。顯然該算法成立，但是不清楚的是，為什么它比歸并排序快。如同歸并排序那樣，快速排序遞歸地解決兩個之間問題并需要線性的附加工作（第3步），不過，與遞歸排序不同，這兩個子問題并不保證逐步具有相等的大小，這是個潛在的隱患?？焖倥判蚋斓脑蛟谟冢?步劃分成兩組實際上是在適當(dāng)?shù)奈恢眠M行，并且非常有效，它的高效不僅彌補了大小不等的遞歸的不足而且還超過了它。這里介紹的方法是大量分析和經(jīng)驗研究的結(jié)果，它代表實現(xiàn)快速排序的非常有效的方法，哪怕是對該方法最微小的偏差都可能引起意想不到的不良結(jié)果。1.3 設(shè)計題目設(shè)計并實現(xiàn)一種快速排序(

5、Quicksort)的優(yōu)化版本，并且比較在下列組合情況下算法的性能表現(xiàn)。cutoff值從020。cutoff值的作用是只有當(dāng)數(shù)組的長度小于等于這個值時，才使用另一種簡單排序方法對其排序，否則使用Quicksort算法排序。選定支點的方法分別是“第一個元素”，“三個元素的中值”，“五個元素的中值”。對上述的測試分別要采用順序、逆序、隨機三種類型的輸入文件。輸入文件中測試數(shù)組的大小可以從1000個數(shù)到10000個數(shù)不等。程序從input.txt文件中讀取輸入，輸出到output.txt 文件。例如：input.txt內(nèi)容如下。5 /*數(shù)字的個數(shù)*/5 4 3 2 1 /*數(shù)字用空格分開*/ /*兩

6、組測試中間空一行*/104 6 8 7 5 1 3 9 2 0相應(yīng)的output.txt內(nèi)容如下。Case number :1Number of elements:51 2 3 4 5Case number :2Number of elements:100 1 2 3 4 5 6 7 8 9程序的重點在于對每種組合情況下算法性能的比較。不同的運行時間要用圖表表示出來，在圖表中要區(qū)分由文件大小的不同而產(chǎn)生的差別。 2. 設(shè)計分析2.1 快速排序的分析（1）最好情況：快速排序的最好情況是支點把集合分成兩個同等大小的子集，并且在遞歸的每個階段都這樣劃分。然后就有了兩個一半大小的遞歸調(diào)用和線性的分組開

7、銷。在這種情況下運行的時間復(fù)雜度是O(nlog2n)。（2）最壞情況：假設(shè)在每一步的遞歸調(diào)用中，支點都恰好是最小的元素。這樣小元素的集合L就是空的，而大元素集合R擁有了除支點以外的所有元素。設(shè)T是對N個元素進行快速排序所需的運行時間，并假設(shè)對0或1個元素排序的時間剛好是1個時間單位。那么對于N>1，當(dāng)每次都運氣很差地選擇最小的元素作為支點，得到的運行時間滿足T(N)=T(N-1)+N。即對N個項進行排序的時間等于遞歸排序大元素子集中的N-1個項所需要的時間加上進行分組的N個單位的開銷。最終得出：T(N)=T(1)+2+3+N=N(N+1)=O(N2) 2 （3）支點的選擇錯誤方式：比較常

8、見的不明智的選擇就是把第一個元素作為支點。但如果輸入是已經(jīng)預(yù)先排過序的，或者是倒序的，該支點給出的分組就很糟糕，因為它是一個末端的元素；而且這種情況會在迭代中繼續(xù)出現(xiàn)，會以O(shè)(N2)的時間復(fù)雜度而告終，所以選擇第一個元素作為支點不是好的策略。中位選擇：把中間元素，即待排序序列中中間位置元素，作為支點是合理的選擇。當(dāng)輸入已經(jīng)排過序時，這種選擇在每次遞歸調(diào)用中都會給出理想的支點。中值劃分：在上述選擇中使用中間值得作為支點可以消除非隨機輸入時出現(xiàn)的退化情況。但這是一種消極的選擇，就是說僅僅試圖避免一個壞的支點而并沒有嘗試選擇一個更好的支點。中值劃分是一種選擇比平均情況更好的支點的嘗試。在中值劃分中，

9、一種比較簡單而有效的策略是選擇待排序列的第一個、中間一個以及最后一個記錄這3個值的中值作為支點。同樣道理，也可以從待排序列中等距離地選取5個值，并將這5個值的中值作為支點。2.2 系統(tǒng)流程圖設(shè)計基本的快速排序算法可以應(yīng)用遞歸實現(xiàn)。關(guān)鍵的細節(jié)包括支點的選擇和如何分組。該算法允許把任何元素作為支點。支點把數(shù)組分為兩組：小于支點的元素集和大于支點的元素集。圖2-1展示了一組數(shù)據(jù)進行快速排序的基本過程。8 3 7 1 4 5 6 9 2 0選擇支點8 3 7 1 4 5 9 6 2 0分組60 3 4 1 2 59 8 7圖2-1 系統(tǒng)流程圖 0 1 2 3 4 5 6 7 8 96 7 8 90 1

10、 2 3 4 5Quicksort Quicksort2.3 系統(tǒng)的詳細設(shè)計程序主要由6部分組成，分別是：(1)程序入口main函數(shù)，從input.txt文件中讀取數(shù)據(jù)，放Array數(shù)組中，在執(zhí)行QuickSort函數(shù)之前用clock函數(shù)獲取系統(tǒng)時95F44stop變量中。使用stop-start獲得QuickSort函數(shù)的執(zhí)行時間。將運行時間和排序后的數(shù)組一起輸入到output.txt文件中。關(guān)閉input.txt文件，關(guān)閉output.txt文件。(2)Quicksort，快速排序算法的實現(xiàn)部分，Quicksort函數(shù)包括五個參數(shù)分別是數(shù)組的地址Array，待排序的第一個元素在數(shù)組中的下標(biāo)

11、，待排序的最后一個元素在數(shù)組中的下標(biāo)，cutoff（小于cutoff時使用另一種簡單的方法進行排序），支點median。Quicksort函數(shù)分為以下幾個步驟：1 確定數(shù)組的大小是否為0或1，若為0或1則直接退出函數(shù)排序未完成。2 判斷支點median取值是否為1，3或5，否則返回錯誤。3 判斷cutoff取值是否恰當(dāng)。4 用median函數(shù)獲得支點。5 在分別設(shè)定指針low和high指向數(shù)組第一個和最后一個元素。6 通過low+和high-的方式讓low和high向中間移動直到Arraylow大于median或Arrayhigh小于median。7 判斷l(xiāng)ow是否小于high，若不小于，則交

12、換Arraylow與Arrayhigh的值，否則跳出循環(huán)排序語句。8 將原數(shù)組分成兩部分后分別用Quicksort函數(shù)處理兩個數(shù)組。Quicksort函數(shù)排序是一個將數(shù)組以median為分界分成一個元素都小于median的數(shù)組和一個元素都大于median的數(shù)組。再將這兩個數(shù)組用Quicksort函數(shù)處理的遞歸調(diào)用過程。(3)MedianOf3,選擇三個值的中值作為支點；(4)MedianOf5,選擇五個值的中值作為支點；(5)Swap,簡單地交換兩個元素的值；(6)InsertionSort，在數(shù)組長度小于cutoff值時使用插入排序來代替快速排序。下面描述main和Quicksort兩個函數(shù)

13、的基本算法的運算過程。main函數(shù)：打開input.txt和output.txt文件；讀入數(shù)的個數(shù)n;從文件中順序讀入n個數(shù)，并放到數(shù)組中；應(yīng)用Quicksort對該數(shù)組排序；將排序后的數(shù)輸出到文件output.txt中；讀入下一個數(shù)組的個數(shù)，繼續(xù)上述過程；關(guān)閉文件。Quicksort函數(shù)：參數(shù)：待排數(shù)組，待排段的起點位置，待排段的終點位置，cutoff值，支點選擇方法If數(shù)組是空的ExitIf待排數(shù)段的元素個數(shù)大于等于cutoff值，且元素個數(shù)大于等于支點選擇方法所要求的元素個數(shù)根據(jù)支點選擇方法選擇一個元素作為支點設(shè)置low為起點值、high為終點值While low<=high Wh

14、ile low位置的值小于支點值 low+ While high位置的值大于支點值 high- If low<high 交換low、high兩個元素將low位置的元素與支點元素交換Quicksort遞歸調(diào)用左半段Quicksort遞歸調(diào)用右半段Else應(yīng)用直接插入排序法對數(shù)組元素排序3. 設(shè)計實踐3.1 開發(fā)環(huán)境Microsoft Visual C+ 6.0Microsoft Visual C+，（簡稱Visual C+、MSVC、VC+或VC）是Microsoft公司推出的開發(fā)Win32環(huán)境程序，面向?qū)ο蟮目梢暬删幊滔到y(tǒng)。它不但具有程序框架自動生成、靈活方便的類管理、代碼編寫和界面

15、設(shè)計集成交互操作、可開發(fā)多種程序等優(yōu)點，而且通過簡單的設(shè)置就可使其生成的程序框架支持數(shù)據(jù)庫接口、OLE2，WinSock網(wǎng)絡(luò)、3D控制界面。它以擁有“語法高亮”，IntelliSense（自動完成功能）以及高級除錯功能而著稱。比如，它允許用戶進行遠程調(diào)試，單步執(zhí)行等。還有允許用戶在調(diào)試期間重新編譯被修改的代碼，而不必重新啟動正在調(diào)試的程序。其編譯及建置系統(tǒng)以預(yù)編譯頭文件、最小重建功能及累加連結(jié)著稱。這些特征明顯縮短程式編輯、編譯及連結(jié)花費的時間，在大型軟件計劃上尤其顯著。3.2 快速排序過程在待排序的n各記錄中任取一條記錄（通常去第一條記錄），把它作為基準(zhǔn)元素，確定該條記錄的最終位置，即該條記

16、錄左邊的記錄的所有記錄的關(guān)鍵字的值均小于該記錄，右邊的所有記錄的關(guān)鍵字的值均大于等于該記錄。待排序序列以基準(zhǔn)元素為界限被分割成兩個區(qū)域，這個過程稱作一次快速排序。之后對所有的區(qū)間分別重復(fù)上述過程，直至每個區(qū)間只有一條記錄為止?？焖倥判蚴且粋€遞歸過程，整個排序過程對不同的區(qū)間進行快速排序。假設(shè)要排序的數(shù)組是A1AN，首先任意選取一個數(shù)據(jù)（通常選用第一個數(shù)據(jù)）作為關(guān)鍵數(shù)據(jù)，然后將所有比它的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個過程稱為一躺快速排序。一躺快速排序的算法是：設(shè)置兩個變量I、J，排序開始的時候I：=1，J：=N；     

17、60;     以第一個數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給X，即X：=A1；           從J開始向前搜索，即由后開始向前搜索（J：=J-1），找到第一個小于X的值，兩者交換； 從I開始向后搜索，即由前開始向后搜索（I：=I+1），找到第一個大于X的值，兩者交換； 重復(fù)第3、4步，直到I=J； 【事例模范】例：將數(shù)據(jù)（45，53，18，36，72，30，48，93，15，36）進行快速排序。 快

18、速排序的一次劃分過程如下所示：【45 53 18 36 72 30 48 93 15 36】移動比較ji【36 53 18 36 72 30 48 93 15 45】交換位置并比較ji【36 45 18 36 72 30 48 93 15 53】交換位置并比較ji【36 15 18 36 72 30 48 93 45 53】交換位置并比較ji【36 15 18 36 45 30 48 93 72 53】交換位置并比較ijj【36 15 18 36 30 45 48 93 72 53】交換位置,i=ji【36 15 18 36 30】45【48 93 72 53】一趟排序的結(jié)果 一次完整的快速排

19、序的排序過程（待排序區(qū)間以中括號括起來）如下所示：【45 53 18 36 72 30 48 93 15 36】【30 36 18 36 15】45【48 93 72 53】【18 15】30【36 36】45【48 93 72 53】15 18 30 【36】【36】45【48 93 72 53】15 18 30 36 36 45 【48 93 72 53】15 18 30 36 36 45 48 【93 72 53】15 18 30 36 36 45 48 【53 72】9315 18 30 36 36 45 48 53 72 93    3.3 調(diào)

20、試過程1. 啟動VC啟動VC的前提是首先要安裝VC軟件。如果你的系統(tǒng)安裝了VC軟件，當(dāng)你啟動了Windows系統(tǒng)之后，從“開始”菜單進入“所有程序”子菜單，找到Microsoft Visual C+ 6.0并單擊它即進入VC軟件的主窗口，如圖3-3-1所示：圖3-3-12編輯程序若要在VC窗口下進行C程序的編輯，首先，單擊工具欄的New Text File按鈕，生成一個新的文本文件窗口，如圖所示；接著，單擊Save按鈕，激活“保存為”對話框，在指定的文件夾下，輸入當(dāng)前程序的文件名（注意：文件名必須給出.C的擴展名），再按“保存”按鈕。到此為止，在指定的目錄下，就生成了一個由讀者自己命名的C文件

21、（比如main.C），接下來，就可以進入編輯屏幕輸入你的C源程序了。由于當(dāng)前的文件是C源程序文件，在其中輸入的任何內(nèi)容（如：關(guān)鍵字、用戶標(biāo)識符及各種運算符），VC系統(tǒng)都會按C源程序的格式進行編排、組織。比如：在文件中，當(dāng)你輸入了一個C關(guān)鍵字時，VC系統(tǒng)自動將其設(shè)定為藍色字體以示區(qū)別；在編輯過程中，如果你輸入了一個塊結(jié)構(gòu)語句（如：for(i=0;i<10;i+)、if(s!=0)、while(k<5)），按回車后，VC系統(tǒng)會把光標(biāo)定位在該塊語句起始位置開始的下一行的每五個字符位置上，以表示下面輸入的內(nèi)容是屬于該塊語句的，以體現(xiàn)C源程序的縮進式書寫格式；此時，如果輸入一個左花括號“”并

22、回車，VC系統(tǒng)將把該花括號左移到與上一行塊語句起始位置對齊的位置上；接著，再按下回車鍵，VC系統(tǒng)會自動采用縮進格式，將當(dāng)前光標(biāo)位置定位在此花括號的下一行的第五列上；如果上一行語句與下一行語句同屬于一個程序段（比如：同一個復(fù)合語句中的語句）,VC系統(tǒng)會自動將這兩個程序行的起始位置對齊排列。如圖3-3-2所示：圖3-3-2微型編譯條工具欄3. 編譯程序程序編輯完后，即可對源程序進行編譯處理。按“編譯微型條”的Compile（功能鍵是Ctrl+F7）按鈕，對程序進行編譯，這時，屏幕上出現(xiàn)如圖3-3-3所示的對話框，讓建立一個默認的工程工作區(qū)，選“是”按鈕確認；緊接著，又出現(xiàn)如圖3-3-4所示的對話框

23、，問是否要保存當(dāng)前的C文件，回答“是”；然后，系統(tǒng)開始編譯當(dāng)前程序。如果程序正確，即程序中不存在語法錯誤，則VC窗口的輸出如圖3-3-5所示的結(jié)果。圖3-3-3圖3-3-4輸出窗口圖3-3-54運行程序當(dāng)程序編譯提示無錯誤信息（0 error(s)）后，按下微型編譯條工具欄上的“建立執(zhí)行程序”（BuildExecute）按鈕 ，或相應(yīng)的功能鍵Ctrl+F5，程序開始運行，然后顯示程序的輸出結(jié)果如圖所示。輸出結(jié)果的屏幕將等待用戶按下任意鍵后，才返回編輯狀態(tài)，一個C程序的執(zhí)行過程結(jié)束。如圖3-3-6所示：圖3-3-63.4 代碼實現(xiàn)#include <stdio.h>#include

24、<stdlib.h>#include <string.h>#include <time.h>#define SIZE 10000 /* 數(shù)組最大的容量 */int MedianOf3(int a,int low, int high);int MedianOf5(int a,int low, int high);void Swap(int *a,int *b);void QuickSort(int a, int left, int right, int cutoff, int median);void InsertionSort(int a,int low,

25、int high);int main()int i,group=0,numbOFelements, elements, Amount;int Array10000;int cutoff = 0, median = 3; clock_t start, stop;FILE *InputPTR,*OutputPTR; /* input和output文件指針 */InputPTR=fopen("input.txt","r+");OutputPTR=fopen("output.txt","w+");if(InputPTR=N

26、ULL) /* 檢查input文件是否存在 */printf("Can not open file!");exit(0);printf("Please Input the value of cutoff(0 20):");scanf("%d",&cutoff);printf("Please Input the value of median(1 or 3 or 5):");scanf("%d",&median); Amount = fscanf(InputPTR,"%d

27、",&numbOFelements); /* 讀取每次迭代的元素的個數(shù) */while (Amount!=EOF) /* 當(dāng)讀到的不是文件的末尾 */group+; fprintf(OutputPTR,"Case number: %dnNumber of elements: %dn", group, numbOFelements); /*輸出的格式 */for(i=0;i<numbOFelements;i+)fscanf(InputPTR,"%d",&Arrayi); /*將輸入讀入到數(shù)組中 */fgetc(InputPT

28、R); fgetc(InputPTR); QuickSort(Array,0,numbOFelements-1,cutoff,median);/*給數(shù)組排序 */for(i=0;i<numbOFelements;i+)fprintf(OutputPTR,"%d ",Arrayi); /*打印排序后的數(shù)組 */Amount = fscanf(InputPTR,"%d",&numbOFelements); fprintf(OutputPTR,"nn");fclose(InputPTR);fclose(OutputPTR);r

29、eturn 0;/*支點（pivot）選擇三個值的中值的算法*/int MedianOf3(int a,int low, int high) int mid=(low+high)/2; /* 確定中間位置 */if(alow>amid)Swap(&alow,&amid);if(alow>ahigh)Swap(&alow,&ahigh);if(amid>ahigh)Swap(&amid,&ahigh);Swap(&amid,&ahigh); /* 交換排序后的中間元素和最后元素的值 */return ahigh;/

30、*支點（pivot）選擇五個值的中值的算法*/int MedianOf5(int a,int low, int high) int i,temp,j,largest;int Step;Step=(high-low)/4; /* 設(shè)定步長為四分之一，這樣便能選出五個元素 */for (j=0; j<4; +j) largest = high-j*Step; /*每次迭代選擇不同的值作為最大值 */for (i=j+1; i<5; +i) /* 比較每次選中的值，用來找到最大值 */ if (ahigh-i*Step>alargest) largest = high-i*Step

31、; /* 設(shè)定新的最大值 */Swap(&ahigh-j*Step,&alargest); /* 將每次找到的最大值放在每次對應(yīng)的位置 */Swap(&ahigh-Step-Step,&ahigh); /* 將選定的支點放到最后面 */Swap(&ahigh-3*Step,&alow); return ahigh;/*交換兩個元素*/void Swap(int *a,int *b)int temp=*a;*a=*b;*b=temp;/*插入排序*/void InsertionSort(int a, int min, int max)int j,i

32、,temp;for (i=min;i<=max;i+)temp=ai; for(j=i;j>min && aj-1>temp;j-)aj=aj-1;aj=temp; /*快速排序*/void QuickSort(int Array, int min, int max, int cutoff, int median)/* median=1時使用第一個值作為支點 median=3時使用三個值的中值作為支點 median=5時使用五個值的中值作為支點*/int low,high,Pivot;if (max-min)=0)return; /* 如果數(shù)組中沒有元素 */

33、if( (median != 1) && (median!=3) && (median!=5) )/* median只可以為1、3、5 */printf("Invalid median value!n");exit(0);if (min+cutoff <= max && (max-min+1)>=median) /* 檢查cutoff值是否合適 */if (median = 1)Swap(&Arraymin,&Arraymax);Pivot=Arraymax;else if (median = 3)

34、 /* 調(diào)用函數(shù)MedianOf3 */Pivot = MedianOf3(Array, min,max); else if (median = 5) /*調(diào)用函數(shù)MedianOf5 */Pivot = MedianOf5(Array,min,max); low = min; high = max;for( ; ; )while(Arraylow < Pivot) /*跳過比支點小的值 */low+;while(Array-high > Pivot) /* 跳過比支點大的值 */if(low<high) /* 交換兩個值 */Swap(&Arraylow,&A

35、rrayhigh);else /* 如果指針重疊了，則跳出循環(huán) */break;Swap(&Arraylow,&Arraymax); QuickSort(Array, min, low-1,cutoff, median); /* 分成兩部分遞歸調(diào)用快速排序 */QuickSort(Array, low+1, max,cutoff,median); elseInsertionSort(Array, min, max); /* 對剩余的數(shù)組進行插入排序 */4. 測試方法4.1 測試方案對本程序的測試不僅是測試程序是否正常運行，是否排序正確，更重要的是記錄不同情況下的運行時間（ru

36、nning time）來比較在不同的支點算法中的運行效率。根據(jù)題目要求生成不同的測試用例。需要3種類型的測試用例。（1）順序(Sorted)的測試用例；（2）逆序(Reverse-Ordered)的測試用例；（3）隨機(Random)的測試用例。提示：對于第三種測試用例，可使用rand()函數(shù)生成。如果每次運行時間太小難以記錄，可以重復(fù)運行機制100次，甚至更多來求平均值。注：每個測試用例中都包含不同Size（待排序列大小）的測試。Size一般不要大于20000。建議使用Size分別為了1000、2000、3000、4000、5000、6000、7000、8000、9000、10000等10種

37、類型。使用測試文件對采用三種不同支點選擇方法的算法進行測試，每次測試可以使用不同的cutoff值（cutoff從020，選擇其中的0、5、10、15、20，共5個）。4.1 測試結(jié)果通過測試得出：在順序測試用例情況下，當(dāng)cutoff為20時，平均用時最少；在逆序測試用例情況下，當(dāng)cutoff為20時，平均用時最少；在隨機測試用例情況下，當(dāng)cutoff為15時，平均用時最少。（注：結(jié)果僅供參考，不同環(huán)境下得出的結(jié)論可能會有出入。）5. 程序運行效果圖5-1 input.txt文件輸入圖u median=1時，使用第一個值作為支點，運行界面如圖5-2所示：圖5-2 u median=1時，outp

38、ut.txt文件輸出界面如圖5-3所示：圖5-3圖5-6 MedianOf3 Pivot/cutoff at 5 時的輸出圖u median=3時，使用三個值的中值作為支點，運行界面如圖5-4所示：圖5-4u median=3時，output.txt文件輸出界面如圖5-5所示：圖5-5u median=5時，使用五個值的中值作為支點，運行界面如圖5-6所示：圖5-6u median=5時，output.txt文件輸出界面如圖5-7所示：圖5-7快速排序（Quicksort）的優(yōu)化版本總結(jié)如下：優(yōu)化版的快速排序?qū)τ谠瓉淼目焖倥判蛩惴▉碚f，主要有兩點優(yōu)勢：（1） 首先，它使得最壞的情況發(fā)生的幾率減

39、小了。（2） 其次，未改進的快速排序算法為了防止比較時數(shù)組越界，在最后要設(shè)置一個哨點。如要在分區(qū)排序時，中間的這個元素（也即中軸）是與最右邊過來第二個元素進行交換的話，那么就可以省略與這一哨點值的比較。關(guān)于這一改進還有更進一點的改進，在繼續(xù)的改進中不僅僅是為了選擇更好的中軸才進行左中右三個元素的比較，它同時將這三個數(shù)排好序后按照其順序放回待排數(shù)組，這樣就能夠保證一個長度為n的待排數(shù)組在分區(qū)之后最長的子分區(qū)的長度為n-2，而不是原來的n-1。也可以在選取中軸值時，可以從由左中右三個中選取擴大到五個元素中或者更多元素中選取。根據(jù)分區(qū)大小調(diào)整算法減少遞歸棧使用的優(yōu)化，快速排序的實現(xiàn)需要消耗遞歸棧的空間，而大多數(shù)情況下都會通過使用系統(tǒng)遞歸棧來完成遞歸求解。對系統(tǒng)棧的頻繁存取會影響到排序的效率。然后快速排序?qū)τ谛∫?guī)模的數(shù)據(jù)集性能不是很好。沒有插入性能高?？焖倥判蛩惴ㄊ褂昧朔种渭夹g(shù)，最終來說大的數(shù)據(jù)集都要分為小的數(shù)據(jù)集來進行處理。當(dāng)數(shù)據(jù)集較小