《算法設(shè)計(jì)與分析》實(shí)驗(yàn)報(bào)告---快速排序

算法分析與設(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.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 的長度；對(duì)數(shù)組 a 進(jìn)行一次劃分，并定義變量 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ù)，分別對(duì) ai 左邊和右邊的數(shù)據(jù)進(jìn)行快速排序；輸出經(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);六、實(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í)地去想到利用這種方法。