数据结构与算法实验报告_内排序

《数据结构与算法实验报告_内排序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构与算法实验报告实验名称：二分插入排序及其性能姓名：学号：专业：指导教师：日期：2012-5-22一、实验目的了解二分插入排序与直接插入排序的关系；掌握二分插入排序算法的实现；掌握算法运行时间的测量。二、实验内容实现二分插入排序算法，并将它和直接插入排序算法进行性能比较，然后用理论分析支持你的结论。三、实验环境WindowXP操作系统；MicrosoftVisualC++编程环境；Pentium(R)Dual-Corecpu;2.50GHz,2.00GB内存四、实现1.类间的关系提示：总排序类、插入排序类、直接插入排序类、二分插入排序类间的关系答：父类是：总排序类

2、子类是：插入排序类和二分插入排序类父类是：插入排序类子类是：直接插入排序类2.二分插入排序类排序函数sort的实现结果：3.性能测试程序的主要代码//二分法插入排序，Array[]为待排序数组，n为数组长度templatevoidBinaryInsertSorter::Sort(RecordArray[],intn){RecordTempRecord;//用来保存当前待插入纪录的临时变量intleft,right,middle;//记录已排好序序列的左、右、中位置for(inti=1;i

3、

4、ntj=i-1;j>=left;j--)Array[j+1]=Array[j];Array[left]=TempRecord;//将待插入记录回填到正确位置}}五、实验数据及结论1.实验数据及分析实验过程的描述。数组规模1k10k100k100k正序100k逆序数组1数组2数组1数组2数组1数组2　　直接插入排序时间　0.0150.015　　0　091.75　91.719　0　71.603　二分插入排序时间0　0　　0　09.375　　9.360　0.901　2.实验结论答:1、当输入的数组较小时，两种排序算法用时相差不大。2、但是，当输入的数组较大时，两种算法的区别就

5、出来了，而二分插入排序时间相对于直接插入排序时间要小得多。说明对于比较大的数组用二分插入排序法比较适合。3、当输入序列是正序时，直接插入排序算法与二分插入排序算法所用的时间相等。4、当输入的排序为逆排序时，二分插入排序要优于直接插入排序。5、二分插入排序法，处理逆序的时间比正序的时间要长。六、理论分析答：使用二分查找插入位置尽管总的移动元素次数不可能减少，但是往往可以减少平均搜索长度，可以减少总的平均比较次数。二分插入排序的平均时间复杂度为O(n2)，最坏情况下的时间复杂度为(n2)，当待排序序列已经有序时，排序时间复杂度为O(nlogn)。空间复杂度为O(1)。直接插

6、入排序应用场合是短序列、基本有序的数据，而实验测试的记录很多，已经不是短序列，记录的比较和移动次数也很多，时间代价的分析复杂一些，空间复杂度也大，因此所用的时间比较长。