希尔排序和快速排序.doc

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