《算法分析与设计?
实验报告
题目： 快速排序
姓名： 于文静
班级： 计科F1203
学号： 201216010230
指导教师: 靳小波
完成时间： 2015-04-06
一、 实验题目
用递归分治法编写Hoare快速排序算法
二、 实验目的
理解时间复杂度的概念。
深入地掌握C语言编程。
通过编程直观地理解算法分析的意义
三、 实验要求
请使用递归分治法编写Hoare快速排序算法，算法的输入如下：
TOC \o "1-5" \h \z 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分别为低地址和高地址；
五、程序代码
#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]);
六、实验结果
七、实验体会
通过本次实验，我了解到快速排序的基本思想，即通过一趟排序将要排序的 数据分割成独立的两部分，其中一部分的数据都小丁等丁某一个数， 另一部分的 数据都大丁等丁这个数，然后再用递归的思想分别对左右两部分的数据进行快速 排序，从而使得整个序列都变得有序。
像这种递归分治的思想，它将一个大问题 划分成若干个子问题，逐个对各个子问题一一击破，使得大问题得以解决。这种 方法用起来非常方便，以后解决有关算法之类的问题时，要有意识地去想到利用 这种方法。