实验课程:算法分析与设计
实验名称:几种排序算法的平均性能比较 (验证型实验)
实验目标:
(1) 几种排序算法在平均情况下哪一个更快。
(2) 加深对时间复杂度概念的理解。
实验任务:
(1)实现几种排序算法(selectionsort, insertionsort,bottomupsort,quicksort, 堆排序)。对于快速分类,SPLIT中的划分元素采用三者A(low),A(high),A((low+high)/2)中其值居中者。
(2)随机产生20组数据(比如n=5000i,1≤i≤20)。数据均属于范围(0,105)内的整数。对于同一组数据,运行以上几种排序算法,并记录各自的运行时间(以毫秒为单位)。
(3)根据实验数据及其结果来比较这几种分类算法的平均时间和比较次数,并得出结论。 实验设备及环境:
PC;C/C++等编程语言。
实验主要步骤:
(1) 明确实验目标和具体任务;
(2) 理解实验所涉及的几个分类算法;
(3) 编写程序实现上述分类算法;
(4) 设计实验数据并运行程序、记录运行的结果;
(5) 根据实验数据及其结果得出结论;
(6) 实验后的心得体会。
一:问题分析(包括问题描述、建模、算法的基本思想及程序实现的技巧等): 1: 随机生成n个0到100000的随机数用来排序的算法如下.
for(int n=1000;n<20000;n+=1000)
{ int a[]=new int[n]; for(int i=0;i<n;i++){ a[i]=(int) (Math.random()*100000); }
2.计算时间的类Date通过它的对象d1的getTime()得到当前时间,再得到排序完成时的时间,相减得到排序所花的时间.
…… …… 余下全文