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

《算法分析与设计?

实验报告

题目： 快速排序

姓名： 于文静

班级： 计科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]);

六、实验结果

七、实验体会

通过本次实验，我了解到快速排序的基本思想，即通过一趟排序将要排序的 数据分割成独立的两部分，其中一部分的数据都小丁等丁某一个数， 另一部分的 数据都大丁等丁这个数，然后再用递归的思想分别对左右两部分的数据进行快速 排序，从而使得整个序列都变得有序。

　像这种递归分治的思想，它将一个大问题 划分成若干个子问题，逐个对各个子问题一一击破，使得大问题得以解决。这种 方法用起来非常方便，以后解决有关算法之类的问题时，要有意识地去想到利用 这种方法。