实 验 报 告 （ 2010 / 2011 学年 第 2 学期）课程名称 数据结构——使用C++语言描述 实验名称 各种内排序算法的实现及性能比较 实验时间 2011 年 5 月 27 日 指导单位 计算机科学与技术系 指导教师 学生姓名 班级学号 学院(系 ) 专 业 一．实验目的和要求 内容： 验证教材的各种内排序算法。分析各种排序算法的时间复杂度。 要求： 使用随机数产生器产生大数据集合，运行上述各种排序算法，使用系统时钟测量各算法所需的实际时间，并进行比较。 二．实验环境（实验设备） Visu al C++6.0 三．实验原理及内容 //selectsort.h #include
//简单选择排序 template void SelectSort(T A[], int n) { int small; for (int i=0; i//直接插入排序 template void InsertSort(T A[], int n) { for(int i=1; i0&&temp template void BubbleSort(T A[], int n) { int i,j,last; i=n-1; while(i>0){ last=0; for(j=0;j //改进的快速排序 template void quick(T A[],int n) { int *a; //用数组保存待排序的子序列的上、下界 int top=0,right,left,j; //left 和 right 为待排序 a=new int[n]; if(a==NULL) return; a[top++]=0; a[top++]=n-1; //以初始序列为待排序序列开始改进的快速排序 //lc for(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+...
