《算法设计与分析》实验报告---快速排序.doc

算法分析与设计实验报告题目： 快速排序 姓名： 于文静 班级： 计科F1203 学号： 201216010230 指导教师： 靳小波 完成时间： 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.35 4.39 6.70 9.82 3.55 2.38 9.12 3.54 1.30 5.20 6.59 9.08 1.79 3.52 4.06 0.43 5.31 7.19 6.07 7.06 9.92 7.79 3.46 6.16 1.83 2.78 3.20 2.95 9.20 0.22 7.13 8.28 5.58 0.80 2.63 7.44 3.04 8.58 9.61 4.52 2.12 1.73 4.16 3.66 2.36 4.08 9.36 8.03 4.92 4.90 9.59 9.83 7.85 3.99 2.68 2.49 4.69 7.67 7.56 8.85 3.88 7.74 6.27 5.48 7.29 2.81 3.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四、 程序流程图开始 将要排序的数据读入到文本文件中，再将文本文件中的内容写到数组a中，其中，变量cnt为数组a的长度； 对数组a进行一次划分，并定义变量i=low j=high,low和high分别为低地址和高地址；ij? N Yai=aj&ij? Nij? Y N j-; Yai与aj交换； i+；ai=aj&ij? N ij? Y N i+; aj与ai交换； j-； Y返回i的值；以ai为中间界值，递归调用quickSort函数，分别对ai左边和右边的数据进行快速排序；输出经过排序后数组a中的内容； 结束五、 程序代码#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); quickSort(a,q+1,high);void main() FILE* file = NULL; int k,cnt;double a1000; if(file = fopen(input2.txt,r) = NULL)printf(the file does not exist.n);return;cnt = 0;while(!feof(file)fscanf(file,%lf,&acnt);cnt+;quickSort(a,0,cnt-1); for(k=0;kcnt;k+)printf(%.2f ,ak);六、 实验结果七、 实验体会通过本次实验，我了解到快速排序的基本思想，即通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的数据都小于等于某一个数，另一部分的数据都大于等于这个数，然后再用递归的思想分别对左右两部分的数据进行快速排序，从而使得整个序列都变得有序。像这种递归分治的