《算法分析与设计》
实验报告
题目：快速排序
姓名：于文静
班级：计科F1203 学号： 0230
指导教师：靳小波
完成时间： 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
四、程序流程图
五、
#include<stdio.h>
int Partition(double a[],int low,int high){ int i,j;
double temp;
i=low;
j=high;
while(i<j){
while(a[i]<=a[j]&&i<j)
j--;
if(i<j){
temp=a[i];
a[i]=a[j];
a[j]=temp;
i++;
}
while(a[i]<=a[j]&&i<j)
i++;
if(i<j){
temp=a[i];
a[i]=a[j];
a[j]=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 a[1000];
if((file = fopen("input2.txt","r")) == NULL) {
printf("the file does not exist...\n");
return;
}
cnt = 0;
while(!feof(file))
{
fscanf(file,"%lf",&a[cnt]);
cnt++;
}
quickSort(a,0,cnt-1);
for(k=0;k<cnt;k++)
printf("%.2f ",a[k]);
}
六、实验结果
七、实验体会
通过本次实验，我了解到快速排序的基本思想，即通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的数据都小于等于某一个数，另一部分的数据都大于等于这个数，然后再用递归的思想分别对左右两部分的数据进行快速排序，从而使得整个序列都变得有序。

像这种递归分治的思想，它将一个大问题划分成若干个子问题，逐个对各个子问题一一击破，使得大问题得以解决。

这种方法用起来非常方便，以后解决有关算法之类的问题时，要有意识地去想到利用这种方法。