算法设计及分析实验报告-快速排序.doc
. .?算法分析与设计?实验报告题目：快速排序 XX：于文静班级： 计科F1203学号：0指导教师：靳小波 完成时间：2021 -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中，其中，变量t为数组a的长度；对数组a进展一次划分，并定义变量i=low j=high,low和high分别为低地址和高地址；i<j? N Yai<=aj&&i<j? Ni<j? Y N j-; Yai与aj交换； i+；ai<=aj&&i<j? Ni<j? Y N i+;aj与ai交换； j-； Y返回i的值；以ai为中间界值，递归调用quickSort函数，分别对ai左边和右边的数据进展快速排序；输出经过排序后数组a中的内容； 完毕五、 程序代码#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,t;double a1000; if(file = fopen("input2.txt","r") = NULL)printf("the file does not exist.n");return;t = 0;while(!feof(file)fscanf(file,"%lf",&at);t+;quickSort(a,0,t-1); for(k=0;k<t;k+)printf("%.2f ",ak);六、 实验结果七、 实验体会通过本次实验，我了解到快速排序的根本思想，即通过一趟排序将要排序的数据分割成独立的两局部，其中一局部的数据都小于等于某一个数，另一局部的数据都大于等于这个数，然后再用递归的思想分别对左右两局部的数据进展快速排序，从而使得整个序列都变得有序。像这种递归分治的思想，它将一个大问题划分成假设干个子问题，逐个对各个子问题一一击破，使得大问题得以解决。这种方法用起来非常方便，以后解决有关算法之类的问题时，要有意识地去想到利用这种方法。教育之通病是教用脑的人不用手，不教用手的人用脑，所以一无所能。教育革命的对策是手脑联盟，结果是手与脑的力量都可以大到不可思议。. .word.zl.
