排序算法设计与分析报告

《排序算法设计与分析报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、排序算法分析报告一、题目要求：分别设计实现插入排序、合并排序、快速排序算法，设计测试数据集测试算法正确性、复杂度及效率。二、算法描述：（1）插入排序：思路：插入排序即将数组看成两部分，前段为已排序序列，后段为未排序列，将后段第一个元素按照排序方式，插入到前段序列中，每次增加1个数到有序区，不断重复直至排序完成。最好情况：数据按正序即非递减排列，比较次数n-1，腾挪次数为0。最坏情况：数据按逆序排列即递减排列，比较次数为n(n-1)/2，腾挪次数为n(n-1)/2。平均情况：数据按随机排列，比较次数约为(n2)/4，移动次数也为(n2)/4。时间复杂度：O(n2)。（

2、2）合并排序：思路：待排序数组采用分治法，看成合并两个有序的长度为N/2的数组，再一分为二，直至仅剩一个数据。再两两合并，最终形成一个有序序列。最好情况、最坏情况、平均情况，合并排序的时间复杂度都是O(nlog2n)。算法的时间复杂度为O(nlog2n)。（3）快速排序：思路：在本次算法程序中，采用随机快速排序，通过生成随机数的方式指定基准数据，并将其放在第一位，再对于其两侧的序列进行同样的排序方式，直至形成有序序列。相对于普通快速排序将第一位作为基准来说，避免了倒序和正序排列时，每次只能将无序序列长度缩小1的弊端。由于基准数据是随机指定的，因此算法复杂度均为O(n

3、log2n)。三、测试数据集的实现：在设计测试数据集时，考虑到要兼顾最好最坏及平均情况并且能够涉及到不同规模的数据，保证各分支可以被测试到，所以利用生成随机数的方式生成数组，数组的规模可变，随机整数的大小及顺序都可变，通过不同的参数输入可选择排序的整数个数N及整数的顺序，程序会自动生成N个随机整数用于测试。设计如下图。为了体现三种算法之间的比较，将生成的数组复制，对同一数组分别用三种排序方式进行排序，互相验证正确性，及比较腾挪次数。在整数个数少时，三种排序差异不大，但随着要排序的数组规模增大，快速排序的优势应该会逐渐体现出来，而插入排序因为每一次都要全数比较而变得十

4、分复杂。一、测试程序：测试程序分为两部分。第一部分在小数据下测试三种排序正确性及比较次数、腾挪次数，数组分为递增、递减及随机三种情况，为了更有效的比较三种算法，每一种下，三种算法都针对同一组数据进行排序，并在测试中将排序的过程打印出来。测试结果：(1)插入排序:(2)合并排序：(3)快速排序：(1)插入排序:(1)合并排序：(2)快速排序：(1)插入排序:(1)合并排序：(2)快速排序：经测试程序验证，可知三种算法的过程正确性及结果正确性。可以看出，(1)插入排序:对于N较小的序列，排序快，效率还不错，但最好和最坏情况差距很大，比较次数和交换次数显著增多。(2)合并

5、排序:无较大差异，三种数组条件下表现较为比较均衡，与原始数组的排序情况关系不大，N的大小决定合并的次数。另外由于数组长度为10，在合并过程中会出现奇数个组的情况，再次合并时，序列变为（40,60,77,85），（1,44,90,98），（3,10），验证合并时，两组序列应能够互相穿插，最终得到一个有序序列，结果得到了（1,3,10,40,44,60,77,85,90,98）因此可得出合并排序算法是正确的。(3)快速排序：可以看出，随机快速排序的效率也是仅与N的大小有密切关系，由于是随机产生的基准数据，比较次数、交换次数不会受原始数据顺序影响不存在最好、最快情况。应该

6、是比普通快速排序中好的地方吧。另外，要说明的是腾挪次数，快速排序看起来腾挪次数很多，可能是算法有一些争议，在划分过程中，每次交换数据按照腾挪次数+3处理，使结果看着很大，如果按1处理似乎效率看着不错，但我个人查阅资料说法不一此处仍存疑，所以还是先按+3进行。第二部分为大数据测试。主要功能是看看每种算法的复杂性表现。所以数组长度较大略去打印及排序过程，只做比较、腾挪次数及时间效率的对比。通过测试结果可以看出，(1)插入排序随着N的增大效率明显降低无论是花费时间还是比较腾挪次数都显著增多，而且最好最坏情况的差异也是相当大的。(2)合并排序随着N的增大效率还不错，而且表现

7、地非常稳定，突出了它稳定排序的特性，在N为100000时的时间与插入排序N为10000的相差不多。(3)快速排序的效率也比较高，但表现不稳定，基于划分的对称性决定了它的算法性能，最好情况是每次基准都恰好取到中值，测试的算法所采取的基准策略为随机选择数组中的数，由第一部分测试打印的基准位数字也可以看出这种策略还是会有得到非常不对称的情况，另外一个令我很惊奇的是上面的测试中我的快速排序算法是按照书上的包含各个子函数的调用，它在100000时平均情况所花费时间是合并算法的十倍之多，并不像想象中的快速，之后我做了改进只写了一个函数，结果是这样的没想到函数的调用对时间影响