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

.

优质范文《算法分析与设计》实验报告

题目： 快速排序 姓名： 于文静 班级： 计科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分别为低地址和高地址； 优质范文

.

N

i

Y N

i

N a[i]<=a[j]&&i

返回i的值； a[j]与a[i]交换； j--；

结束 输出经过排序后数组a中的内容； 以a[i]为中间界值，递归调用quickSort函数，分别对a[i]左边和右边的数据进行快速排序； 优质范文

.

五、 程序代码

#include

int Partition(double a[],int low,int high){ }

优质范文

int i,j; double temp; i=low; j=high; while(i

while(a[i]<=a[j]&&i

j--;

if(i

while(a[i]<=a[j]&&i

i++; temp=a[i]; a[i]=a[j]; a[j]=temp; i++;

if(i

temp=a[i]; a[i]=a[j]; a[j]=temp; j--;

.

void quickSort(double a[],int low,int high){

int q;

if(low

void main(){

FILE* file = NULL;

int k,cnt; double a[1000];

q=Partition(a,low,high);

quickSort(a,low,q-1); quickSort(a,q+1,high); }

if((file = fopen(\

cnt = 0;

while(!feof(file)) { }

quickSort(a,0,cnt-1);

fscanf(file,\cnt++; { }

printf(\return;

优质范文