数据结构实验报告10

计算机科学与工程学院《算法与数据结构》实验报告(十)专业班级2017级实验地点503机房学生学号1710050108指导教师姚峰学生姓名刘政林实验时间20XX-XX-XX实验项目排序技术综合应用实验类别基础性（√）设计性（）综合性（）其它（）实验目的及要求（1）熟练掌握常用的排序方法，并掌握用高级语言实现排序算法的方法；（2）深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用；（3）了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。成绩评定表类别评分标准分值得分合计上机表现积极出勤、遵守纪律按要求完成设计任务30分程序与报告程序代码规范、功能正确报告详实完整、体现收获70分说明：评阅教师：姚峰日期：20年月日计算机科学与工程学院《算法与数据结构》实验报告2实验内容实验内容：对希尔排序、快速排序、归并排序任意选择两种排序方法进行比较。任意选择希尔排序、快速排序、归并排序中两种排序方法，对任意给定一组数据：单增、单减、乱码等，对它们进行比较分析。实验说明：希尔排序算法如下：快速排序算法如下：voidShellSort(intr[],intn){for(d=n/2;d=1;d=d/2)//以增量为d进行直接插入排序{for(i=d+1;i=n;i++){r[0]=r[i];//暂存被插入记录for(j=i-d;j0&&r[0]r[j];j=j-d)r[j+d]=r[j];//记录后移d个位置r[j+d]=r[0];}}}voidQuickSort(intr[],intfirst,intend){if(firstend){//递归结束pivot=Partition(r,first,end);//一次划分QuickSort(r,first,pivot-1);//递归地对左侧子序列进行快速排序QuickSort(r,pivot+1,end);//递归地对右侧子序列进行快速排序}}intPartition(intr[],intfirst,intend){i=first;j=end;//初始化while(ij){while(ij&&r[i]=r[j])j--；//右侧扫描if(ij){r[i]←→r[j];//将较小记录交换到前面i++;}while(ij&&r[i]=r[j])i++；//左侧扫描if(ij){r[j]←→r[i];//将较大记录交换到后面j--;}}retutni;//i为轴值记录的最终位置}计算机科学与工程学院《算法与数据结构》实验报告3实验内容#includeiostreamusingnamespacestd;voidShellSort(intr[],intn){inttemp;intd,i,j;d=n/2;while(d0){for(i=d;in;i++){temp=r[i];j=i-d;while(j=0&&tempr[j]){r[j+d]=r[j];j=j-d;}r[j+d]=temp;}d=d/2;}}voidQuickSort(intr[],intfirst,intend){inti,j;i=first;j=end;//初始化inttemp;if(firstend){temp=r[i];while(ij){while(ij&&r[i]=r[j])j--;//右侧扫描r[i]=r[j];//将较小记录交换到前面while(ij&&r[i]=r[j])i++;//左侧扫描r[j]=r[i];//将较大记录交换到后面}计算机科学与工程学院《算法与数据结构》实验报告4r[i]=temp;QuickSort(r,first,i-1);//递归地对左侧子序列进行快速排序QuickSort(r,i+1,end);//递归地对右侧子序列进行快速排序}}voidprint(intr[],intn){for(inti=0;in;i++){coutr[i];}return;}intmain(){intIncrease1[10]={0,1,2,3,4,5,6,7,8,9};intIncrease2[10]={0,1,2,3,4,5,6,7,8,9};intDecline1[10]={9,8,7,6,5,4,3,2,1,0};intDecline2[10]={9,8,7,6,5,4,3,2,1,0};intOutOfOrder1[10]={6,5,1,4,2,3,7,0,9,8};intOutOfOrder2[10]={6,5,1,4,2,3,7,0,9,8};cout应用希尔排序对“单增”进行排序endl;ShellSort(Increase1,10);print(Increase1,10);coutendl;cout应用快速排序对“单增”进行排序endl;QuickSort(Increase2,0,9);print(Increase2,10);coutendl;cout应用希尔排序对“单减”进行排序endl;ShellSort(Decline1,10);print(Decline1,10);coutendl;cout应用快速排序对“单减”进行排序endl;QuickSort(Decline2,0,9);print(Decline2,10);coutendl;cout应用希尔排序对“乱序”进行排序endl;计算机科学与工程学院《算法与数据结构》实验报告5ShellSort(OutOfOrder1,10);print(OutOfOrder1,10);coutendl;cout应用快速排序对“乱序”进行排序endl;QuickSort(OutOfOrder2,0,9);print(OutOfOrder2,10);coutendl;return0;}总结：希尔排序为插入排序中的一种，其时间复杂度在最坏的情况下为O(n^2),在最好的情况下为O(n)；而快速排序为交换排序中的一种，其时间复杂度在最坏的情况下为O(n^2)，在最好的情况下为O(nlog2n)；同时，两者都具有不稳定性。实验内容计算机科学与工程学院《算法与数据结构》实验报告6实验总结