数据结构实验报告四.doc

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

1、实验报告（2014/2015学年第二学期）课程名称数据结构A实验名称基本内排序算法的验证和性能比较，改进快速排序算法实验时间年月日指导单位指导教师学生姓名班级学号学院(系)专业实验报告实验名称基本内排序算法的验证和性能比较，改进快速排序算法指导教师实验类型设计实验学时2实验时间一、实验目的和要求（1）验证内排序算法，分析算法的时间性能①验证各种基本排序算法②分析各算法的最好、最坏和平均情况时间复杂度，以渐近表示法表示。③产生不同规模和排列状态的数据集，测量算法的实际执行时间；④比较理论分析和实际运行时间，解释理由。提示：使用随机数发生器产生随机测试数据；使用系

2、统时钟测量运行时间。要求：（1）理解和掌握各种基本排序算法；（2）学会测量和分析排序算法的时间和空间性能；（3）改进快速排序算法，理解改进的理由，验证算法改进的效果。二、实验环境(实验设备)硬件：微型计算机软件：Windows操作系统、MicrosoftVisualC++6.0三、实验原理及内容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)实验

3、报告2、源代码#include#includeusingnamespacestd;templatevoidSwap(T&a,T&b){//交换两个数值Ttemp;temp=a;a=b;b=temp;}templatevoidSelectSort(TA[],intn){//简单选择排序intsmall,i,j;for(i=0;i

4、templatevoidInsertSort(TA[],intn){//直接插入排序for(inti=1;i0&&tempvoidBubbleSort(TA[],intn){//冒泡排序inti,j,last;i=n-1;while(i>0){last=0;for(j=0;j

5、}}i=last;}}templatevoidQuickSort(TA[],intn){//快速排序QSort(A,0,n-1);}templatevoidQSort(TA[],intleft,intright){inti,j;if(leftA[left]&&j>=left);if(i

6、,A[j]);QSort(A,left,j-1);QSort(A,j+1,right);}}templatevoidMerge(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++];elsetemp[k++]=A[j++];}while(i<=j1)temp[k++]=A[i++];while(j

7、=0;ivoidMergeSort(TA[],intn){inti1,j1,i2,j2;intsize=1;while(sizen-1)j2=n-1;elsej2=i2+size-1;Merge(A,i1,j1,i2,j2);i1=j2+1;}size*=2;}}templatevoidAdjustDown(TA[],intr

8、,intj){//堆排序intchil