算法导论实验报告

《算法导论实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、算法导论实验报告实验题目：1、产生个数为22，24，26，28，210，212，214，216，218，220的字符串数组，要求每个字符串由随机产生的1~16位的字母组成，然后用插入排序、冒泡排序、堆排序、快速排序、归并排序对字符串进行排序。2、产生个数为22，24，26，28，210，212，214，216，218，220的整数数组，要求每个数组有随机产生的1~10000的整数组成，然后用插入排序、快速排序、基数排序、计数排序对整数数组进行排序。实验分析：在该实验中，我们通过对字符串和整数的排序，切实体会了在大规模的数据中算法的重要性。对于整个实验的流程大致分

2、为4个部分：1、随机个数的随机字符串和随机个数的整数的产生。2、各种排序算法的实现：插入排序、冒泡排序、堆排序、快速排序、归并排序、基数排序、计数排序。3、对程序运行时间的记录，利用系统时间进行统计。4、对实验的数据进行分析，观察出O(n2),O(n),O(lgn)的时间复杂度的算法在实践中的差距。下面进行具体分析：一、随机个数的随机字符串和随机个数的整数的产生对于第一个实验，要求产生一个给定长度的随机的随机长度为1~16的字符串。分析要求后，感觉如果要提高算法的效率和节省空间，必须采取动态分配的方案。因为如果用c中的定长分配，太浪费空间。而如果采用c++中的动

3、态数组，会造成空间无法回收的问题和字符串传递时必须进行copystring的操作，太浪费时间。我们用动态分配地址的二维数组来存储随机产生的字符串组,程序如下：str=(char**)malloc((lenw+1)*sizeof(char*));for(i=1;i

4、实验，要求产生一个给定长度的随机1~10000的整数。我们仍然采用动态分配的一维数组存储数据，程序如下：len=(int)pow(2,a);str=(int*)malloc((len+1)*sizeof(int));二、各种排序算法的实现根据具体的数据类型对各种排序算法进行改进，具体实现见后程序。问题分析见后实验小结。三、对程序运行时间的记录我们利用windows.h中的QueryPerformanceCounter(&time)函数来调用系统时间，可以精确到ms的量级。程序如下：LARGE_INTEGERtime1;LONGLONGbegin,end;Quer

5、yPerformanceCounter(&time1);begin=time1.QuadPart;INSERT_SORT(integ1,n);QueryPerformanceCounter(&time1);end=time1.QuadPart;printf("程序运行的时间为%ems",(double)(end-begin));四、对实验的数据进行分析实验一的数据统计：字符串个数22242628210插入排序（ms）9142577612670冒泡排序（ms）1020160254357970堆排序（ms）13321285922593归并排序（ms）501303

6、2914265678.3快速排序（ms）1422733331574字符串个数212214216218220插入排序（ms）325775298829302003561004827245000冒泡排序（ms）1179690555765605344271009996333000堆排序（ms）160661533731009263571401931345710归并排序（ms）293561395607196693213791271439500快速排序（ms）8187115481464306348710149117910各个算法的运行的是时间性能如下图：由于堆排序、归并排序和

7、快速排序的曲线比较靠近，做细分图如下：有上述图我们可以看出冒泡排序是一种极差的排序算法，而插入排序所需的时间也是极多的，由于这两者都是时间复杂度为O(n2)的算法，冒泡排序每查找一次就需要改变一次位置，而插入排序是先找到插入位置在调换的，所以插入排序要略优。而我们从图中看出堆排序、快速排序、归并排序的所需的时间是差不多的，因为三者的时间复杂度都为O(nlgn)，这正体现了理论上时间复杂度在实践中的应用。同时由细分图我们可以看出归并排序的性能较差，而快速排序和堆排序的性能都是相当优异的。实验二数据统计：字符串个数22242628210插入排序（ms）7103636

8、65545快速排序（ms