实验报告（2015/2016学年第2学期）课程名称数据结构A实验名称各种内排序算法的实现及性能的比较实验时间2016年6月20日指导单位计算机科学与技术系指导教师骆健学生姓名班级学号学院(系)管理学院专业信息管理与信息系统一、问题陈述（1）验证教材的各种内排序算法（2）分析各种内排序算法的时间复杂度（3）改进教材中的快速排序法，使得当子集和小于10个元素时改用直接插入排序（4）使用随机数发生器产生大数据集合，运行上述各排序算法，使系统时钟测量个算法所需的实际时间，并进行比较。系统时钟包含在头文件“time.h”中。二、概要设计Main.cpp调用Menu.h，为主程序。Menu.h主菜单Selectsort.h简单选择排序Insertsort.h直接插入排序Bubblesort.h冒泡排序Quicksort.h快速排序Mergesort.h合并排序三、详细设计①简单选择排序：将初始序列（A[0]~A[n-1]）作为待排序序列，第一趟在待排序序列（A[0]~A[n-1]）中找最小元素，与该序列中第一个元素A[0]交换，这样子序列（A[0]）有序，下一趟排序在带牌子序列（A[1]~A[n-1]）中进行。第i趟排序子序列（A[i-1]~A[n-1]）中进行。开始i=0i
0&&temp0last=0;j=0jA[left]i=j时将j与第一个元素交换。程序流程图：⑤两路合并排序：将有n个元素的序列看成是n个长度为1的有序开始intsize=1Sizen-1j2=n-1Merge(A,i1,j1,i2,j2)i1=j2+1size*=2结束j2=i2+size-1NYYNNY子序列，然后两两合并子序列，得到[n/2]个长度为2或1的有序子序列，再两两合并…直到得到一个长度为n的有序序列时结束。程序流程图：四、程序代码selectsort.h#include//简单选择排序templatevoidSelectSort(TA[],intn){intsmall;for(inti=0;i//直接插入排序templatevoidInsertSort(TA[],intn){for(inti=1;i0&&temptemplatevoidBubbleSort(TA[],intn){inti,j,last;i=n-1;while(i>0){last=0;for(j=0;j//改进的快速排序templatevoidquick(TA[],intn){int*a;inttop=0,right,left,j;a=newint[n];if(a==NULL)return;a[top++]=0;a[top++]=n-1;//lcfor(j=0;a[j]!=NULL;j++){left=a[j++];right=a[j];if(left>right)Swap(left,right);if(right-left<15)InsertSortExt(A,left,right);else{a[top++]=left;a[top++]=QuickSort(A,left,right)-1;a[top++]=a[top-2]...
