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

《《算法设计与分析》实验报告---快速排序》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《算法分析与设计》实验报告题目：快速排序姓名：于文静班级：计科F1203学号：201216010230指导教师：靳小波完成时间：2015-04-06实验题目用递归分治法编写Hoare快速排序算法一、实验目的1.理解时间复杂度的概念。2.深入地掌握C语言编程。3.通过编程直观地理解算法分析的意义二、实验要求请使用递归分治法编写Hoare快速排序算法，算法的输入如下：7.307.154.272.146.293.990.269.101.892.860.445.524.354.396.709.823.552.389.123.541.305.206.599.081.793.524.060

2、.435.317.196.077.069.927.793.466.161.832.783.202.959.200.227.138.285.580.802.637.443.048.589.614.522.121.734.163.662.364.089.368.034.924.909.599.837.853.992.682.494.697.677.568.853.887.746.275.487.292.813.672.521.951.824.384.425.544.411.940.318.415.694.59三、程序流程图开始将要排序的数据读入到文本文件中，再将文本文件中的内容写到

3、数组a中，其中，变量cnt为数组a的长度；对数组a进行一次划分，并定义变量i=lowj=high,low和high分别为低地址和高地址；iintPartition(doublea[],intlow,inthi

4、gh){inti,j;doubletemp;i=low;j=high;while(i

5、q-1);quickSort(a,q+1,high);}}voidmain(){FILE*file=NULL;intk,cnt;doublea[1000];if((file=fopen("input2.txt","r"))==NULL){printf("thefiledoesnotexist...");return;}cnt=0;while(!feof(file)){fscanf(file,"%lf",&a[cnt]);cnt++;}quickSort(a,0,cnt-1);for(k=0;k

6、会通过本次实验，我了解到快速排序的基本思想，即通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的数据都小于等于某一个数，另一部分的数据都大于等于这个数，然后再用递归的思想分别对左右两部分的数据进行快速排序，从而使得整个序列都变得有序。像这种递归分治的思想，它将一个大问题划分成若干个子问题，逐个对各个子问题一一击破，使得大问题得以解决。这种方法用起来非常方便，以后解决有关算法之类的问题时，要有意识地去想到利用这种方法。