十四希尔及快速排序

《十四希尔及快速排序》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验十四实现希尔和快速排序班级计算机三班姓名尹亮学号2009131334 一、实验目的熟悉希尔排序和快速排序的基本思想，掌握希尔排序和快速排序的操作过程及算法实现。二、实验内容输入待排数据元素序列，然后用希尔排序和快速排序法对其进行排序。三、实验要点及说明希尔排序是对直接插入排序的改进，其基本思想是：先将待排序记录序列分割成若干个“较稀疏的”子序列，分别进行直接插入排序。经过上述粗略调整，整个序列中的记录已经基本有序，最后再对全部记录进行一次直接插入排序。具体实现时，首先选定两个记录间的距离d1，在整个待排序

2、记录序列中将所有间隔为d1的记录分成一组，进行组内直接插入排序，然后再取两个记录间的距离d2

3、中间(称为该记录归位),这个过程称作一趟快速排序。程序代码：#include#defineMAXE20typedefintkeytype;typedefcharinfortype[10];typedefstruct{keytypekey;infortypedata;}rectype;voidshellsort(rectyper[],intn){inti,j,d,k;rectypetemp;d=n/2;while(d>0){for(i=d;i=0&&

4、r[j].key>r[j+d].key){temp=r[j];r[j]=r[j+d];r[j+d]=temp;j=j-d;}}printf("d=%d:",d);for(k=0;ki&&r[j].key>temp.

5、key)j--;if(i

6、=10;keytypea[]={9,8,7,6,5,4,3,2,1,0};rectyper[MAXE];printf("希尔排序:");for(i=0;i

7、"");printf("快速排序:");for(i=0;i

8、当前有序区中，将r[j]与r[j+d]j交换，输出每一趟的排序结果，递减增量d。快速排序：区间内至少在一个元素的情况，用区间的第一个记录作为基准，从区间两端交替向中间扫描，直至i=j为止。从右向左扫描，找第一个关键字小于temp.key的r[j]，表示找到这样的R[j],R[i]R[j]交换。六实验结论通过实验掌握了希尔排序和快速排序的运算方法。