《《算法設(shè)計(jì)與分析》實(shí)驗(yàn)報(bào)告---快速排序》由會(huì)員分享,可在線閱讀,更多相關(guān)《《算法設(shè)計(jì)與分析》實(shí)驗(yàn)報(bào)告---快速排序(6頁珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告題目:姓名:班級(jí):快速排序于文靜計(jì)科 F1203學(xué)號(hào):2指導(dǎo)教師:靳小波完成時(shí)間:2015-04-06一、實(shí)驗(yàn)題目用遞歸分治法編寫Hoare 快速排序算法二、實(shí)驗(yàn)?zāi)康?. 理解時(shí)間復(fù)雜度的概念。2. 深入地掌握 C語言編程。3. 通過編程直觀地理解算法分析的意義三、實(shí)驗(yàn)要求請(qǐng)使用遞歸分治法編寫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.
2、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.
3、41 1.94 0.31 8.41 5.69 4.59四、程序流程圖開始將要排序的數(shù)據(jù)讀入到文本文件中,再將文本文件中的內(nèi)容寫到數(shù)組a 中,其中,變量cnt 為數(shù)組 a 的長(zhǎng)度;對(duì)數(shù)組 a 進(jìn)行一次劃分,并定義變量 i=low j=high,low 和 high 分別為低地址和高地址;Nij?YNai=aj&ij?YNij?j-;Yai 與 aj 交換;i+ ;Nai=aj&ij?YNij?i+;Yaj 與 ai 交換;j- ;返回 i 的值;以 ai 為中間界值,遞歸調(diào)用quickSort 函數(shù),分別對(duì) ai 左邊和右邊的數(shù)據(jù)進(jìn)行快速排序;輸出經(jīng)過排序后數(shù)組 a 中的內(nèi)容;結(jié)束五、程序代碼#
4、includeint Partition(double a,int low,int high)int i,j;double temp;i=low;j=high;while(ij)while(ai=aj&ij)j-;if(ij)temp=ai;ai=aj;aj=temp;i+;while(ai=aj&ij)i+;if(ij)temp=ai;ai=aj;aj=temp;j-;return i;void quickSort(double a,int low,int high)int q;if(lowhigh)q=Partition(a,low,high);quickSort(a,low,q-1);q
5、uickSort(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;kcnt;k+)printf(%.2f ,ak);六、實(shí)驗(yàn)結(jié)果七、實(shí)驗(yàn)體會(huì)通過本次實(shí)驗(yàn), 我了解到快速排序的基本思想, 即通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分, 其中一部分的數(shù)據(jù)都小于等于某一個(gè)數(shù), 另一部分的數(shù)據(jù)都大于等于這個(gè)數(shù), 然后再用遞歸的思想分別對(duì)左右兩部分的數(shù)據(jù)進(jìn)行快速排序,從而使得整個(gè)序列都變得有序。 像這種遞歸分治的思想, 它將一個(gè)大問題劃分成若干個(gè)子問題, 逐個(gè)對(duì)各個(gè)子問題一一擊破, 使得大問題得以解決。 這種方法用起來非常方便, 以后解決有關(guān)算法之類的問題時(shí), 要有意識(shí)地去想到利用這種方法。