十四希尔及快速排序.doc

实验十四 实现希尔和快速排序 班级 计算机三班 姓名 尹亮 学号 2009131334 一、实验目的 熟悉希尔排序和快速排序的基本思想，掌握希尔排序和快速排序的操作过程及算法实现。 二、实验内容 输入待排数据元素序列，然后用希尔排序和快速排序法对其进行排序。 三、实验要点及说明 希尔排序是对直接插入排序的改进，其基本思想是：先将待排序记录序列分割成若干个“较稀疏的”子序列，分别进行直接插入排序。经过上述粗略调整， 整个序列中的记录已经基本有序，最后再对全部记录进行一次直接插入排序。具体实现时，首先选定两个记录间的距离d1，在整个待排序记录序列中将所有间隔为d1的记录分成一组，进行组内直接插入排序，然后再取两个记录间的距离d2d1，在整个待排序记录序列中，将所有间隔为d2的记录分成一组，进行组内直接插入排序，直至选定两个记录间的距离dt=1为止，此时只有一个子序列，即整个待排序记录序列。快速排序是由冒泡排序改进而得的。基本思想是：在待排序的n个记录中任取一个记录(通常取第一个记录),把该记录放入适当位置后,数据序列被此记录划分成两部分。所有关键字比该记录关键字小的记录放置在前一部分,所有比它大的记录放置在后一部分,并把该记录排在这两部分的中间(称为该记录归位),这个过程称作一趟快速排序。程序代码：#include#define MAXE 20typedef int keytype;typedef char infortype10;typedef struct keytype key;infortype data;rectype;void shellsort (rectype r,int n)int i,j,d,k;rectype temp;d=n/2;while(d0)for(i=d;i=0&rj.keyrj+d.key)temp=rj;rj=rj+d;rj+d=temp;j=j-d;printf( d=%d: ,d);for(k=0;kn;k+)printf(%3d,rk.key);printf(n);d=d/2;void quicksort(rectype r,int s,int t)int i=s,j=t,k;rectype temp;if (si&rj.keytemp.key)j-;if(ij)ri=rj;i+;while (ij&ri.keytemp.key)i+;if(ij)rj=ri;j-;ri=temp;printf( );for(k=0;k10;k+)if(k=i)printf(%d,rk.key);elseprintf(%4d,rk.key);printf(n);quicksort(r,s,i-1);quicksort(r,i+1,t);void main()int i,k,n=10; keytype a=9,8,7,6,5,4,3,2,1,0; rectype rMAXE;printf(希尔排序:n) ;for(i=0;in;i+)ri.key=ai;printf(n);printf( 初始关键字);for(k=0;kn;k+)printf(%3d,rk.key);printf(n);shellsort(r,n);printf( 最后结果 );for(k=0;kn;k+)printf(%3d,rk.key);printf(nn); printf(快速排序:n); for(i=0;in;i+)ri.key=ai;printf(n);printf( 初始关键字);for(k=0;kn;k+)printf(%4d, rk.key); printf(n);quicksort(r,0,n-1);printf( 最后结果 );for(k=0;kn;k+)printf(%4d,rk.key);printf(nn);四 测试结果五 算法思想希尔排序：将人rd.n-1分别插入各组当前有序区中，将r j 与r j+d j交换，输出每一趟的排序结果，递减增量d。快速排序：区间内至少在一个元素的情况，用区间的第一个记录作为基准，从区间两端交替向