[算法实验.doc

实验课程：算法分析与设计 第一部分 实验内容 1. 实验目标： （1） 几种排序算法在平均情况下哪一个更快。 （2） 加深对时间复杂度概念的理解。 2. 实验任务： （1）实现几种排序算法（selectionsort, insertionsort,bottomupsort,quicksort, mergesort）。对于快速分类，SPLIT中的划分元素采用三者A(low)，A(high)，A((low+high)/2)中其值居中者。 （2）随机产生20组数据（比如n=5000i，1≤i≤20）。数据均属于范围（0，105）内的整数。对于同一组数据，运行以上几种排序算法，并记录各自的运行时间（以毫秒为单位）。 （3）根据实验数据及其结果来比较这几种分类算法的平均时间和比较次数，并得出结论。 3. 实验设备及环境： PC；vs2005 C/C++等编程语言。 4. 实验主要步骤： 明确实验目标和具体任务； 理解实验所涉及的几个分类算法； 编写程序实现上述分类算法； 设计实验数据并运行程序、记录运行的结果； 根据实验数据及其结果得出结论； 实验后的心得体会。 第二部分 问题及算法 1．问题描述： （1）实现几种排序算法（selectionsort, insertionsort,bottomupsort,quicksort, mergesort）。对于快速分类，SPLIT中的划分元素采用三者A(low)，A(high)，A((low+high)/2)中其值居中者。 （2）随机产生20组数据（比如n=5000i，1≤i≤20）。数据均属于范围（0，105）内的整数。对于同一组数据，运行以上几种排序算法，并记录各自的运行时间（以毫秒为单位）。 2．所求： 根据实验数据及其结果来比较这几种分类算法的平均时间和比较次数，并得出结论。 算法思想： Selectionsort思想：通过从前往后比较，交换后面元素中比当前元素最小的元素。 Insertionsort思想：通过从后往前比较，逐个向后移动比当前元素笑得元素。 Bottomupsort思想：通过把元素分成2的幂的子集，然后进行n/(2^j)次的合并。 Quicksort思想：通过以基准元素为标准，结合分治的思想。 Mergesort思想：方法跟Bottomupsort相似。 第三部分 实验结果与分析 1．实验数据和结果 实验环境：vs2005 C++环境 基于随机生成数据n（5000*i）(1=i=20) Selectionsort 时间、次数 Insertionsort 时间、次数 Bottomupsort 时间、次数 Quicksort 时间、次数 Mergesort 时间、次数 1 47ms47ms 6206785 0ms 56868 0ms 111139 0ms 38528 2 203ms203ms16ms 123500 0ms 234023 0ms 82440 3 453ms 112492500 469ms15ms 189973 0ms 363645 16ms 123430 4 828ms 199990000 844ms 100008516 16ms 267373 0ms 508543 15ms 176137 5 1328ms 312487500 1328ms 157364239 0ms 341699 16ms 651399 15ms 223612 6 1938ms 449985000 1906ms 224904486 16ms 410396 0ms 799837 0ms 264543 7 2656ms 612482500 2610ms 305848690 15ms 508484 0ms 972991 15ms 335453 8 3485ms 799980000 3453ms 402610714 16ms 574710 0ms 1098546 16ms 376823 9 4422ms 1012477500 4344ms 505041090 15ms 646959 16ms 1267471 16ms 421620 10 5484ms 1249975000 5406ms 625620823 16ms 733365 16ms 1427203 16ms 47871 11 6656ms 1512472500 6562ms 756629466 16ms 802657 15ms 1525995 16ms 52056 12 7906ms 1799970000 7844ms 900489818 15ms 880554 15m