希尔排序和快速排序

整理文档很辛苦,赏杯茶钱您下走!

免费阅读已结束,点击下载阅读编辑剩下 ...

阅读已结束,您可以下载文档离线阅读编辑

资源描述

实验题目:排序技术综合应用实验目的:(1)熟练掌握常用的排序方法,并掌握用高级语言实现排序算法的方法;(2)深刻理解排序的定义和各种排序方法的特点,并能加以灵活应用;(3)了解各种方法的排序过程及其依据的原则,并掌握各种排序方法的时间复杂度的分析方法。实验内容:对希尔排序、快速排序、归并排序任意选择两种排序方法进行比较。任意选择希尔排序、快速排序、归并排序中两种排序方法,对任意给定一组数据:单增、单减、乱码等,对它们进行比较分析。设计分析:在排序过程中,若整个表都是放在内存中处理,排序是不涉及数据的内外存交换,则称之为内排序。本次实验要求实现内排序中的两种:希尔排序和快速排序。希尔排序的过程:先取定一个小于n的整数d1作为第一个增量,把表的全部记录分成d1的倍数的记录放在同一个组中,在各组内进行直接插入排序,然后去第二个增量d2(d1),重复上述的分组和排序,直到所取的增量d1=1,即所有记录放在同一组中进行直接插入排序为止。快速排序的过程:在待排序的n个记录中任取一个记录(通常取第一个记录),把该记录放入适当位置后,数据序列被此记录划分成两部分。所有关键字比该记录关键字小的记录放置在前一部分,所有比他大的记录放置在后一部分,并把该记录排在这两部分的中间,这个过程称作一趟快速排序。之后对所有的两部分分别重复上述过程,直到每部分有一个记录或空为止。源程序代码:#includestdio.h#defineMax30typedefstruct{intkey;}RecType;RecTypeR[Max],S[Max];voidShellSort(RecTypeR[],intn)//希尔排序{inti,j,gap;RecTypetmp;gap=n/2;while(gap0){for(i=gap;in;i++){tmp=R[i];j=i-gap;while(j=0&&tmp.keyR[j].key){R[j+gap]=R[j];j=j-gap;}R[j+gap]=tmp;}gap=gap/2;}}voidQuickSort(RecTypeR[],ints,intt)//快速排序{inti=s,j=t;RecTypetmp;if(sj){tmp=R[s];while(i!=j){while(ji&&R[j].keytmp.key)j--;R[i]=R[j];while(ij&&R[i].keytmp.key)i++;R[j]=R[i];}R[i]=tmp;QuickSort(R,s,i-1);QuickSort(R,i+1,t);}}voidmain(){intn,i;printf(请输入关键字个数:);scanf(%d,&n);printf(请输入关键字序列:\n);for(i=0;in;i++){scanf(%d,&R[i].key);S[i].key=R[i].key;}ShellSort(R,n);printf(希尔排序结果为:);for(i=0;in;i++)printf(%d,R[i].key);printf(\n);QuickSort(S,0,n-1);printf(快速排序结果为:);for(i=0;in;i++)printf(%d,S[i].key);printf(\n);}测试用例:对序列{0,1,2,3,4,5,6,7,8,9},{9,8,7,6,5,4,3,2,1,0}和{3,5,2,8,0,6,1,4,7,9}的测试结果如图所示。图9-1图9-2图9-3实验总结:此次实验实现了两种排序方法:希尔排序和快速排序。通过编程调试运行和不断地修改,我也基本上了解了两种排序的原理过程,感觉这两种方法效率非常高,而相对于它们以前学过的冒泡排序就显得稍慢一点,总而言之,不能硬说哪种优秀哪种差,针对不同的序列就有不同的排序方法,在今后的实验中,将会很多次的需要对数据进行排序,学会了这几种排序方法对数据处理的编程有很大帮助。

1 / 3
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功