下载此文档

数据结构实验报告四.doc


文档分类:高等教育 | 页数:约14页 举报非法文档有奖
1/14
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/14 下载此文档
文档列表 文档介绍
实验报告(2014/2015学年第二学期)课程名称数据结构A实验名称基本内排序算法的验证和性能比较,改进快速排序算法实验时间年月日指导单位指导教师学生姓名班级学号学院(系)专业实验报告实验名称基本内排序算法的验证和性能比较,改进快速排序算法指导教师实验类型设计实验学时2实验时间实验目的和要求(1)验证内排序算法,分析算法的时间性能①验证各种基本排序算法②分析各算法的最好、最坏和平均情况时间复杂度,以渐近表示法表示。③产生不同规模和排列状态的数据集,测量算法的实际执行时间;④比较理论分析和实际运行时间,解释理由。提示:使用随机数发生器产生随机测试数据;使用系统时钟测量运行时间。要求:(1)理解和掌握各种基本排序算法;(2)学会测量和分析排序算法的时间和空间性能;(3)改进快速排序算法,理解改进的理由,验证算法改进的效果。二、实验环境(实验设备)硬件:微型计算机软件:Windows操作系统、MicrosoftVisualC++、实验原理及内容voidman()1、case4:QuickSort(B,n)case5:MergeSort(B,n)case6:HeapSort(B,n)case1:SelectSort(B,n)case2:InsertSort(B,n)case3:BubbleSort(B,n)实验报告2、源代码#include<iostream>#include<>usingnamespacestd;template<classT>voidSwap(T&a,T&b){//交换两个数值 Ttemp; temp=a; a=b; b=temp;}template<classT>voidSelectSort(TA[],intn){//简单选择排序 intsmall,i,j; for(i=0;i<n-1;i++){ small=i; for(j=i+1;j<n;j++){ if(A[j]<A[small]) small=j; } Swap(A[i],A[small]); }}template<classT>voidInsertSort(TA[],intn){//直接插入排序 for(inti=1;i<n;i++) { intj=i; Ttemp=A[i]; while(j>0&&temp<A[j-1]){ A[j]=A[j-1]; j--; } A[j]=temp; }}template<classT>voidBubbleSort(TA[],intn){//冒泡排序 inti,j,last; i=n-1; while(i>0){ last=0; for(j=0;j<i;j++){ if(A[j+1]<A[j]){ Swap(A[j],A[j+1]); last=j; } } i=last; }}template<classT>voidQuickSort(TA[],intn){//快速排序 QSort(A,0,n-1);}template<classT>voidQSort(TA[],intleft,intright){ inti,j; if(left<right){ i=left; j=right+1; do{ do i++;while(A[i]<A[left]&&i<=right); do j--;while(A[j]>A[left]&&j>=left); if(i<j) Swap(A[i],A[j]); }while(i<j); Swap(A[left],A[j]); QSort(A,left,j-1); QSort(A,j+1,right); }}template<classT>voidMerge(TA[],inti1,intj1,inti2,intj2){//两路合并排序 T*temp=newT[j2-i1+1]; inti=i1,j=i2,k=0; while(i<=j1&&j<=j2){ if(A[i]<=A[j]) temp[k++]=A[i++]; else temp[k++]=A[j++]; } while(i<=j1) temp[k++]=A[i++]; while(j<j2) temp[k++]=A[j++]; for(i=0;i<k;i++) A[i1++]=temp[i]; delete[]temp;}template<classT>voidMergeSort(TA[],intn){ inti1,j1,i2,j2; intsize=1; while(size<n){ i1=0; while(i1+size<n){ i2=i1+size; j1=i2-1; if(i2+size-1>n-1) j2=n-1; else j2=i2+size-1; Merge(A,i1,j1,i2,j2);

数据结构实验报告四 来自淘豆网www.taodocs.com转载请标明出处.

非法内容举报中心
文档信息
  • 页数14
  • 收藏数0 收藏
  • 顶次数0
  • 上传人glfsnxh
  • 文件大小1.28 MB
  • 时间2020-08-07