内容发布更新时间 : 2024/11/20 13:36:12星期一 下面是文章的全部内容请认真阅读。

算法设计与分析实验报告

插入排序，归并排序和快速排序

一． 实验目的：

比较插入排序，归并排序和快速排序在不同规模下的不同类型的数据下的腾挪次数和比较次数。

二． 实现方式：

实验分为几个模块：生成数据集，排序，输出比较。 （1）生成数据集

通过生成数据集的函数生成三个测试数据集（n个数），分别写入三个文件：randData.txt（随机数数据），sortData.txt（正序的数据），reverseData.txt（逆序的数据）。

（2）排序

实验共有三种排序方法：插入排序，归并排序和快速排序。 A. 插入排序

直接插入排序(从小到大)： 把数组分为为排序和已排序两个序列{{a1,a2...ak}{ak,a(k+1)...an}} ，每次从未排序的序列中抽一个数出来并插入到已排序的序列里面。

B. 归并排序

利用循环，每次将数组a中长度为s的两个子段（若不够长则保留）按从小到的大的顺序合并起来并存储到数组b中，下一次合并时再把b中的子段合并

后存到a中。如此反复，直到数组a排序完毕。

C. 快速排序

每一次快速排序选出一个枢轴元素，然后把比枢轴元素小的元素排在枢轴元素前，把比枢轴元素大的元素排在枢轴元素后面。然后进行递归直到排序完毕。 在这对快速排序进行了优化，使用随机化速排序（枢轴元素为数组任意一个元素）。

（3）输出比较

调用不同的排序方式并输出相应的排序时间，腾挪次数和比较次数。输出结果都会记录在相应的文件中。

三． 实验结果及分析 （1）

当数组值为正序时，插入排序最快，其腾挪次数和比较次数都最少。而在其他情况下插入排序的比较次数远大于另外两种排序（数据规模越大则越明显）；

（2）

无论数据是何种类型，归并排序的腾挪次数和比较次数并不受数据类型的影响；

（3）

当数组值是有序的时候，普通快速排序退化，其比较次数远大于其他排序而腾挪次数无明显变化；

（4）

尽管在以上两种情况下，快速排序会出现退化，但它的腾挪次数始终比归并排序少。

（5）

当数组值为随机数的时候，三种方式的快速排序都是优势明显的，其腾挪次数和比较次数都小于另外两种排序。

（6）

分析表格如下：

插入排序 平均情况 O(n^2) 最好情况 O(n) (数组顺序) 最坏情况 O(n^2) 归并排序 O(nlogn) O(nlogn) O(nlogn) 普通快速排序 O(nlogn) O(nlogn) O(n^2) （数组有序） 三者取中快排 O(nlogn) O(nlogn) O(nlogn) 随机化快排 O(nlogn) O(nlogn) O(nlogn)

注：这里快速排序的最坏情况是指数组有序的时候

四． 总结 （1） （2）

数组有序时使用插入排序性能最好；

归并排序比较稳定，其平均效率比插入排序高，一定规模下腾挪次数和比较次数也基本不变；

（3）

快速排序的平均效率较高，其腾挪次数也会比归并排序少。