《算法設(shè)計與分析》實驗報告---快速排序

算法分析與設(shè)計實驗報告題目：姓名：班級：快速排序于文靜計科 F1203學號：2指導教師：靳小波完成時間：2015-04-06一、實驗題目用遞歸分治法編寫Hoare 快速排序算法二、實驗目的1. 理解時間復雜度的概念。2. 深入地掌握 C語言編程。3. 通過編程直觀地理解算法分析的意義三、實驗要求請使用遞歸分治法編寫Hoare 快速排序算法，算法的輸入如下：7.30 7.15 4.27 2.14 6.29 3.99 0.26 9.10 1.89 2.86 0.44 5.52 4.354.39 6.70 9.82 3.55 2.38 9.12 3.54 1.30 5.20 6.59 9.08 1.79 3.524.06 0.43 5.31 7.19 6.07 7.06 9.92 7.79 3.46 6.16 1.83 2.78 3.202.95 9.20 0.22 7.13 8.28 5.58 0.80 2.63 7.44 3.04 8.58 9.61 4.522.12 1.73 4.16 3.66 2.36 4.08 9.36 8.03 4.92 4.90 9.59 9.83 7.853.99 2.68 2.49 4.69 7.67 7.56 8.85 3.88 7.74 6.27 5.48 7.29 2.813.67 2.52 1.95 1.82 4.38 4.42 5.54 4.41 1.94 0.31 8.41 5.69 4.59四、程序流程圖開始將要排序的數(shù)據(jù)讀入到文本文件中，再將文本文件中的內(nèi)容寫到數(shù)組a 中，其中，變量cnt 為數(shù)組 a 的長度；對數(shù)組 a 進行一次劃分，并定義變量 i=low j=high,low 和 high 分別為低地址和高地址；Ni<j?YNai<=aj&&i<j?YNi<j?j-;Yai 與 aj 交換；i+ ；Nai<=aj&&i<j?YNi<j?i+;Yaj 與 ai 交換；j- ；返回 i 的值；以 ai 為中間界值，遞歸調(diào)用quickSort 函數(shù)，分別對 ai 左邊和右邊的數(shù)據(jù)進行快速排序；輸出經(jīng)過排序后數(shù)組 a 中的內(nèi)容；結(jié)束五、程序代碼#include<stdio.h>int Partition(double a,int low,int high)int i,j;double temp;i=low;j=high;while(i<j)while(ai<=aj&&i<j)j-;if(i<j)temp=ai;ai=aj;aj=temp;i+;while(ai<=aj&&i<j)i+;if(i<j)temp=ai;ai=aj;aj=temp;j-;return i;void quickSort(double a,int low,int high)int q;if(low<high)q=Partition(a,low,high);quickSort(a,low,q-1);quickSort(a,q+1,high);void main()FILE* file = NULL;int k,cnt;double a1000;if(file = fopen("input2.txt","r") = NULL)printf("thereturn;not exist.n");cnt = 0;while(!feof(file)fscanf(file,"%lf",&acnt);cnt+;quickSort(a,0,cnt-1);for(k=0;k<cnt;k+)printf("%.2f ",ak);六、實驗結(jié)果七、實驗體會通過本次實驗， 我了解到快速排序的基本思想， 即通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分， 其中一部分的數(shù)據(jù)都小于等于某一個數(shù)， 另一部分的數(shù)據(jù)都大于等于這個數(shù)， 然后再用遞歸的思想分別對左右兩部分的數(shù)據(jù)進行快速排序，從而使得整個序列都變得有序。 像這種遞歸分治的思想， 它將一個大問題劃分成若干個子問題， 逐個對各個子問題一一擊破， 使得大問題得以解決。 這種方法用起來非常方便， 以后解決有關(guān)算法之類的問題時， 要有意識地去想到利用這種方法。