《算法设计与分析》实验报告 快速排序.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 ij? Y a[i]=a[j]ij? a[i]=a[j]ij? ij? Y N ij? j--; j--; Y a[i]与 a[i]与a[j]交换； i++； a[i]=a[j]ij a[i]=a[j]ij? N ij? Y N ij? i++; i++; a[j a[j]与a[i]交换； j--； 返回 返回i的值； 以 以a[i]为中间界值，递归调用quickSort函数，分别对a[i]左边和右边的数据进行快速排序； 输出经过排序后数组 输出经过排序后数组a中的内容； 结束 结束 程序代码 #includestdio.h int Partition(double a[],int low,int high){ int i,j; double temp; i=low; j=high; while(ij){ while(a[i]=a[j]ij) j--; if(ij){ temp=a[i]; a[i]=a[j]; a[j]=temp; i++; } while(a[i]=a[j]ij) i++; if(ij){ temp=a[i]; a[i]=a[j]; a[j]=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);