南邮数据结构上机实验四内排序算法的实现以及性能比较.docVIP

实 验 报 告 （ 2015 / 2016学年 第学期） 课程名称 实验名称 实验时间 2016 年 月 日 指导单位 系 指导教师 学生姓名 班级学号 学院(系) 专 业 实习题名:内排序算法的实现及性能比较 班级 B141116 姓名 耿宙 学号 日期2016.05.26 问题描述 验证教材的各种内排序算法，分析各种排序算法的时间复杂度；改进教材中的快速排序算法，使得当子集合小于10个元素师改用直接插入排序；使用随即数发生器产生大数据集合，运行上述各排序算法，使用系统时钟测量各算法所需的实际时间，并进行比较。系统时钟包含在头文件“time.h”中。 概要设计 文件Sort.cpp中包括了简单选择排序SelectSort()，直接插入排序InsertSort()，冒泡排序BubbleSort()，两路合并排序Merge()，快速排序QuickSort()以及改进的快速排序GQuickSort()六个内排序算法函数。主主函数main的代码如下图所示： 详细设计 类和类的层次设计 在此次程序的设计中没有进行类的定义。程序的主要设计是使用各种内排序算法对随机生成的数列进行排列，并进行性能的比较，除此之外还对快速排序进行了改进。下图为主函数main的流程图：  main() 核心算法 简单选择排序： 简单选择排序的基本思想：第1趟，在待排序记录r[1]~r[n]中选出最小的记录，将它与r[1]交换；第2趟，在待排序记录r[2]~r[n]中选出最小的记录，将它与r[2]交换；以此类推，第i趟在待排序记录r[i]~r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。 GQuickSort () 四、程序代码 templateclass T void GQuickSort(T A[],int n) //改进的快速排序 { GQSort(A,0,n-1); } templateclass T void GQSort(T A[],int left,int right) { int i,j; if(right=9) { if(leftright) { i=left; j=right+1; do { do i++;while (A[i]A[left]); do j--;while (A[j]A[left]); if(ij) Swap(A[i],A[j]); }while(ij); Swap(A[left],A[j]); QSort(A,left,j-1); QSort(A,j+1,right); } } else { InsertSort(A,right-left+1); return ; } } 五、测试和调试 测试用例和结果 测试结果如下图 生成随机数据 简单选择排序及其所需时间 直接插入排序及其所需时间 冒泡排序及其所需时间 快速排序及其所需时间 改进快速排序及其所需时间 两路合并排序及其所需时间 结果分析 简单选择排序的最好、最坏的平均情况的时间复杂度都为O(n2),是不稳定的排序方法；直接插入排序的最好情况的时间复杂度为O(n)，最坏情况的时间复杂度为O(n2)；冒泡排序最好情况的时间复杂度为O(n)，最坏情况的时间复杂度为O(n2)，是稳定的排序方法；快速排序最好情况的时间复杂度为O(n2)，最坏情况的时间复杂度为O(nlog2n)，是不稳定的排序方法；两路合并排序的时间复杂度为O(nlog2n)，是稳定的排序方法。 实习小结 在这次实验中,我们对内部排序算法进行了比较以及性能分析,通过这次实验,我们加深了对内部排序算法的理解,对内部排序算法的基本运算的实现有所掌握,对课本中所学的各种数据结构进一步理解和掌握,学会了如何把学到的知识用于解决实际问题,锻炼了自己动手的能力。 通过这次实验，我明白了，没有总是最好的排序方法。对于一般列表，快速排序、希的性能较好。通过本次实验，我深刻体会到问题解决方案的重要性，算法效率分析的必要性。法时。 附录： #includeiostream.h #includestdlib.h #includetime.h templateclass T void Swap(T a,T b) { T temp=a; a=b; b=temp; } templateclass T void SelectSort(T A[],int n) //简单选择排序 { int small; for(in