算法设计实验Word格式.docx

算法设计实验Word格式.docx

《算法设计实验Word格式.docx》由会员分享，可在线阅读，更多相关《算法设计实验Word格式.docx（11页珍藏版）》请在冰点文库上搜索。

先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。

3、归并排序

归并排序法是将两个（或两个以上）有序的表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。

然后再把有序子序列合并为整体有序序列。

4、快速排序

选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。

另一部分记录的元素值比基准值大。

此时基准元素在其排好序后的正确位置，然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。

三、算法伪代码

1、冒泡排序伪代码

2、插入排序伪代码

3、归并排序伪代码

4、快速排序伪代码

四、算法时间复杂性理论比较

算法分析项

冒泡排序

插入排序

归并排序

快速排序

问题规模参数

数组大小n

基本操作

比较、交换

比较、移动

比较

影响基本操作执行次数的因素

数组原始排列影响交换次数

原始排列影响比较移动次数

不受原始排列影响

原始排列影响比较和交换次数

基本操作执行次数表达式或递推方程

1+2+…+n-1

最好情况下为1+1+…+1；

最坏情况下为1+2+…+n-1

T（n）=2T（n/2）+O（n）

时间复杂性

O（n^2）

O（n*logn）

最好O（n）

平均O（n*logn）

最坏O（n^2）

空间复杂性

O

（1）

O（n）

O（logn）

五、测试用例设计

1、测试用例设计原则

（1）每种排序多次测试，使用不同数据规模。

（2）让四种排序测试同一组数据，对比其执行时间。

2、具体测试用例

使用文件读写，存放在“in.txt”文件之中。

六、算法时间复杂性实验比较

1、实验环境

PC的配置：

编程工具：

CodeBlocks

2、实验方法

根据各个排序算法的思想和伪代码，编写出相应的程序。

首先测试程序本身的正确性：

使用多组小规模数据，测试四种排序是否正确将原来无序数组正确排序为有序数组。

四种排序测试无误之后，分别进行时间复杂性分析。

因为要使用大规模数据且测试结果需要记录以备分析、拟合，所以采用文件读写方式。

读入数据：

输出测试结果：

测试数组使用随机数产生：

测试排序运行时间的办法：

在C++中使用clock（）函数：

由于在小规模情况下很多测试结果为零，因此考虑重复排序次数以达到放大效果，同时舍去测试结果为0的数据，取有效次数的平均值。

3、结果记录

（1）冒泡排序和插入排序

对冒泡和插入排序排序分别采用10次重复和20次重复，测试结果如下，左边为10次重复，右边为20次重复，三列数据分别表示数据规模，平均用时，有效次数：

使用excel拟合出两种排序再10次和20次重复下的趋势图：

（2）归并排序和快速排序

由于在小规模（1万以下）案例下，归并和快速排序测试结果几乎全部为0，因此不得不考虑使用超大规模案例：

拟合出的曲线如下：

七、算法时间复杂性理论与实验结果比较与分析

1、算法复杂性理论与实验结果比较

实验结果表明：

（1）同等规模下，快速排序和归并排序比冒泡排序和插入排序要快，随着问题规模的增加，这种差异越来越明显。

（2）冒泡排序和插入排序的时间复杂性确实呈现O（n^2）的复杂度

（3）冒泡排序和插入排序时间复杂性都为O（n^2），但在大规模情况下，插入排序要比冒泡排序要快，这与理论相符合，因为冒泡排序比较的次数是固定的，但插入排序比较的次数与原数组的输入密切相关，平均情况下比较次数没有冒泡排序多。

（4）快速排序和归并排序时间复杂性都是O（n*logn），但在大规模情况下，快速排序要比归并排序要快，理论分析上，归并排序复制数组占用大量的时间，而快速排序没有这个操作，实验结果印证了这一分析。

2、理论与实验差距分析

快速排序和归并排序拟合出的效果几乎是线性的，我认为这与有效的测试用例太少有关，实验的偶然性增加。

同时，经过数学推导，当n比较大事，扩大k倍的数据规模，时间复杂性扩大的规模近似为k倍，这也解释了为什么拟合出的曲线类似线性增长。

八、问题思考与总结

1、对不同算法思想的理解

冒泡排序：

从列表的第一个数字到倒数第二个数字，逐个检查：

若某一位上的数字大于他的下一位，则将它与它的下一位交换。

插入排序：

每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置，直到全部插入排序完为止。

归并排序：

归并排序法是将多个有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。

快速排序：

先保证列表的前半部分都小于后半部分，然后分别对前半部分和后半部分排序。

2、对不同算法程序结构的总结

冒泡排序使用两层循环，第一层确定冒泡的规模，表示已经排好的数据的个数，因为最后几个数据已经沉底；

第二层让选出的数据进行冒泡，只要前者比后者大，交换。

插入排序外层也是一个循环，表示待插入的那个数的位置，内部是一个不定循环，确定这个数应插入的位置。

归并排序使用分治策略，把待排序的数组一分为二，采用递归结构，最后在合并数组。

快速排序的结构与归并排序类似，也采用分治策略和递归结构，但分完以后无需合并数组，比归并排序简洁。

九、实验出现的问题与解决

一开始数组开在函数之中，当数组长度超过一定规模就会导致内存溢出，因此把测试用的数组设为全局变量。