十四希尔及快速排序.doc

实验十四实现希尔和快速排序
班级计算机三班姓名尹亮学号2009131334
一、实验目的
熟悉希尔排序和快速排序的基本思想，掌握希尔排序和快速排序的操作过程及算法实现。
二、实验内容
输入待排数据元素序列，然后用希尔排序和快速排序法对其进行排序。
三、实验要点及说明
希尔排序是对直接插入排序的改进，其基本思想是：先将待排序记录序列分割成若干个“较稀疏的”子序列，分别进行直接插入排序。经过上述粗略调整，整个序列中的记录已经基本有序，最后再对全部记录进行一次直接插入排序。具体实现时，首先选定两个记录间的距离d1，在整个待排序记录序列中将所有间隔为d1的记录分成一组，进行组内直接插入排序，然后再取两个记录间的距离d2<d1，在整个待排序记录序列中，将所有间隔为d2的记录分成一组，进行组内直接插入排序，直至选定两个记录间的距离dt=1为止，此时只有一个子序列，即整个待排序记录序列。
快速排序是由冒泡排序改进而得的。基本思想是：在待排序的n个记录中任取一个记录(通常取第一个记录),把该记录放入适当位置后,数据序列被此记录划分成两部分。所有关键字比该记录关键字小的记录放置在前一部分,所有比它大的记录放置在后一部分,并把该记录排在这两部分的中间(称为该记录归位),这个过程称作一趟快速排序。
程序代码：
#include<stdio.h>
#defineMAXE20
typedefintkeytype;
typedefcharinfortype[10];
typedefstruct
{
keytypekey;
infortypedata;
}rectype;
voidshellsort(rectyper[],intn)
{
inti,j,d,k;
rectypetemp;
d=n/2;
while(d>0)
{
for(i=d;i<n;i++)
{
j=i-d;
while(j>=0&&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;k<n;k++)
printf("%3d",r[k].key);
printf("\n");
d=d/2;
}
}
voidquicksort(rectyper[],ints,intt)
{
inti=s,j=t,k;
rectypetemp;
if(s<t)
{
temp=r[s];
while(i!=j)
{
while(j>i&&r[j].key>temp.key)
j--;
if(i<j)
{
r[i]=r[j];
i++;
}
while(i<j&&r[i].key<temp.key)
i++;
if(i<j)
{
r[j]=r[i];
j--;
}
}
r[i]=temp;
printf("");
for(k=0;k<10;k++)
if(k==i)
printf("[%d]",r[k].key);
else
printf("%4d",r[k].key);
printf("\n");
quicksort(r,s,i-1);
quicksort(r,i+1,t);
}
}
voidmain()

{
inti,k,n=10;

keytypea[]={9,8,7,6,5,4,3,2,1,0};

rectyper[MAXE];
printf("希尔排序:\n");
for(i=0;i<n;i++)
r[i].key=a[i];
printf("\n");
printf("初始关键字");
for(k=0;k<n;k++)
printf("%3d",r[k].key);
printf("\n");
shellsort(r,n);
printf("最后结果");
for(k=0;k<n;k++)
printf("%3d",r[k].key);
printf("\n\n");
printf("快速排序:\n");

for(i=0;i<n;i++)
r[i].key=a[i];
printf("\n");
printf("初始关键字");
for(k=0;k<n;k++)
printf("%4d",r[k].key);
printf("\n");
quicksort(r,0,n-1);
printf(