算法与数据结构实验5

福建农林大学实验报告

系（教研室）： 计算机 专业： 年级： 实验课程： 姓名： 学号： 实验室号：_ 计算机号： 实验时间： 指导教师签字： 成绩：

实验五 （快速、堆、基数）排序算法的设计

一、 实验目的和要求

实验目的：

1.深刻理解排序的定义和各种排序方法的特点，并能灵活运用。 2.掌握常用的排序方法，并掌握用高级语言实现排序算法的方法。

3.了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的性能的分析方法。

实验要求：

要求彻底弄懂排序的物理存储结构，并通过此试验为以后的现实使用打下基础。

二、 实验内容和原理

（1）实验内容：

设计快速排序，堆排序和基数排序的算法。 （2）实验原理：

快速排序：在待排序的n个数据中，任取一个数据为基准，经过一次排序后以基准数据把全部数据分为两部分，所有数值比基准数小的都排在其前面，比它大的都排在其后，然后对这两部分分别重复这样的过程，直到全部到为为止。堆排序：对待排序的n个数据，依它们的值大小按堆的定义排成一个序列，从而输出堆顶的最小值数据（按最小值跟堆排序），然后对剩余的数据再次建堆，便得到次小的，如此反复进行输出和建堆，直到全部排成有序列。基数排序：LSD法：先按最低关键字位k1对待排序数据中的n个值进行排序，按k1值把待排序文件中的n个记录分配到具有不同k1值的若干个堆，然后按k1值从小到大的次序收集在一起，下次再按高一位关键子位k2的值进行分配和收集，如此不断地按更高一位关键字位进行分配和收集，直到用kn分配和收集之后，整个数据按多关键字位有序。

三、 实验环境

硬件：（1）学生用微机（2）多媒体教室或远程教学（3）局域网环境 软件：（1）Windows XP中文操作系统 （2）Turbo C 3.0

四、 算法描述及实验步骤

- 1 -

1、算法描述

快速排序算法描述：用两个变量i,j分别指向待排序列的第一个记录和最后一个记录；先将第一个记录保存到R[0]中，然后j从最后一个记录起向前扫描，直到找到R[j].keyR[0].key时R[i]移到R[j]中；就这样j自j+1从后向前扫描一次移入一个R[j]于R[i]中，i自i+1向后扫描一次移入一个R[i]于R[j]中，反复交替地扫描和移到记录;直到i=j时把R[0]给R[i]中，他把整个待排序区间分割为两个更小的序列，再将以上过程，直到区间为大小为1时，排序结束。

堆排序算法描述：堆排序分为建堆和堆调整，初始建堆时将与此序列对应的一维数组看成是一棵完全二叉树，从完全二叉树的最后一个结点K(i)（i等于n/2向下取整）开始，通过调整逐步使以K(i)到K(1)为根的子树满足堆的定义，直到以K(1)为根的树满足堆定义时初始堆建成。堆调整在出堆顶记录之后，用堆中的最后一个记录替代原堆顶记录。由于除根节点K(i)之外的所有子树仍具有堆的性质，故只需对根结点自上而下调整即可。

基数排序算法描述：可分为分配和收集。引入一个为结构体的辅助数组用于分配时保存同一关键位的元素。个位数字为低关键字位，十位数字为高关键字位。关键字位值的范围为0—9，qu[i].f与qu[i].r为第i个队列的头指针和尾指针。将不qu[i].f不为空的链表相连，进行收集。直到所有的关键字位都被分配完毕，收集完毕后退出。

2、算法流程图

堆排序：

begin j=n Y 将第一个与最后一个结点交换 调用sift函数进行堆调整 j-- j>=2 N end

- 2 -

快速排序：

begin 将1,n入栈用于第一趟排序 栈=NULL N 出栈到i，j Y 以i,j为参数进行快速排序，返回基准插入的下标值给R 以k为分段点左区间!=1 N 右区间范围!=1 N Y 令左区间的最小与最大分别入栈做下次排序的i,j Y 令右区间的最小与最大分别入栈做下次排序的i,j end

- 3 -

基数排序：

begin 为qu队列初始化 i=1 得到数R[i]的个位数值给k Y I<=n N N qu[k].r->next=p; qu[k].r=p; qu[k]=NULL Y 令队首队尾都指向q i++ 将数R[I]插入qu[i]中 j=i+1 i<=9 Y N end I=j+1 3、代码(注释)

#include\"stdio.h\" #define max 100 #define rd 10 #define d 3

typedef struct/*定义结构体*/ {int key; int ke[d+1];

/*elemtype otheritems;*/ int next; }recordtype; int f[rd],e[rd];

int divideareasort(recordtype R[],int s,int t)/*对待排序记录区间R[s]到R[t]以R[s]为基准进行一次分割排序，并返回基准记录的最终位置*/ {int i,j;

recordtype temp;/*定义暂存工作单元*/ i=s;j=t;

temp=R[s];/*确定分割基准*/ do

- 4 -

{while((R[j].key>=temp.key)&&(ij--;/*自后向前扫描找小于基准关键字的记录*/ if(i{R[i]=R[j];/*把R[j]移入R[i]中*/ i++;}

while((R[i].key<=temp.key)&&(ii++;/*自前向后扫描找大于基准关键字的记录*/ if(i{R[j]=R[i]; j--;}}

while(ivoid quicksort(recordtype R[],int s,int t)/*对待排序文件R[s..t]进行快速排序*/ {int i; if(s{i=divideareasort(R,s,t);/*分割区间并把基准位置送i*/ quicksort(R,s,i-1);/*对基准记录前的区间快速排序*/ quicksort(R,i+1,t);/*对基准记录后的区间快速排序*/ }}

void heapadjust(recordtype R[],int s,int t)/*对R[s..t]进行筛选的堆调整算法，除R[s]外其他位置都满足最小值根堆定义*/ {int i,j;

recordtype temp;/*定义临时工作单元*/

temp=R[s];/*待筛选记录送临时工作单元中*/ i=s;/*i初始化为s，即指向待筛选记录*/

j=2*i;/*j初始化为2i，即指向待筛选记录的左孩子*/ while(j<=t)/*逐层向下筛选*/ {if((jR[j+1].key))

j++;/*若右孩子记录关键字值小，让j指向右孩子*/ if(temp.key>R[j].key)/*孩子记录关键字小，向下筛选*/ {R[i]=R[j];/*孩子记录上移*/ i=j;/*为继续向下筛选做准备*/ j=2*i;} else

j=t+1;/*孩子记录关键字值大时，筛选结束，准备退出循环*/ }

R[i]=temp;/*将最初的待筛选记录填入正确位置*/ }

void heapsort(recordtype R[],int n)/*对待排序文件R[]中的n个记录进行堆排序的算法*/ {int i;

recordtype temp; for(i=n/2;i>=1;i--)

heapadjust(R,i,n);/*调用筛选算法建立初始堆*/ for(i=n;i>1;i--)/*n-1次输出堆顶记录并调整堆*/

{temp=R[1];/*堆顶记录与当前堆中最后一个记录交换*/ R[1]=R[i]; R[i]=temp;

heapadjust(R,1,i-1);/*调用筛选算法重建堆*/ }}

int radixsort(recordtype R[])/*对待排序文件R[]单链表基数排序，返回指向结果单链表的指针值*/ {int i,j,k,p,t;

p=1;/*p初始化，指向R中第一个记录结点*/ for(i=d;i>=1;i--)/*控制d趟分配和收集*/

{for(j=0;jwhile(p!=-1)/*控制一趟中各记录结点的分配*/

{k=R[p].ke[i];/*p结点的第i关键字基数位的值送k中*/ if(f[k]==-1)/*若队列为空时作为队头结点插入*/ f[k]=p; else

R[e[k]].next=p;/*否则插入队尾*/

- 5 -

e[k]=p;/*修改队尾指针指向刚插入的结点*/

p=R[p].next;/*p指向下一个记录结点，为后续分配做好准备*/ }

j=0;/*一趟分配完成为收集做准备*/ while(f[j]==-1)/*找第一个非空队列*/ j++;

p=f[j];/*第一个非空队列头指针送p*/ t=e[j];/*第一个非空队列尾指针送t*/ while(jif(f[j]!=-1)/*若第j个队列不空*/

{R[t].next=f[j];/*队头接入收集链尾*/ t=e[j];/*t指向队尾，即收集链尾*/ }}

R[t].next=-1;/*本趟收集完毕，将链尾指针域置为空*/ }

return(p);/*返回单链表的指针值*/ }

void main() {int a,i,j,k,n,q;

recordtype R[max];

printf(\"请输入排序表长度:\"); scanf(\"%d\

printf(\"请输入数据:\\n\"); for(i=1;i<=n;i++)

{scanf(\"%d\printf(\"输入 key[d]:\\n\"); for(j=1;j<=d;j++)

{printf(\" \");

scanf(\"%d\输入各关键字值的基数*/ }

if(i==n)

R[i].next=-1;/*输入最后一个尾指针为-1*/ else

R[i].next=i+1;/*输入尾指针使其指向下一个关键字*/ }

printf(\" R[i].key :\"); for(i=1;i<=n;i++)

printf(\"%-4d\

q=radixsort(R);/*首先调用基数排序函数，并将返回值给q*/ printf(\"\\n 基数排序 :\");

while(q!=-1)/*用while循环输出数据*/ {printf(\"%-4d\q=R[q].next;}

heapsort(R,n);/*调用堆排序函数进行堆排序*/ printf(\"\\n 堆排序 :\"); for(i=1;i<=n;i++)

printf(\"%-4d\

quicksort(R,1,n);/*调用快速排序函数进行快速排序*/ printf(\"\\n 快速排序 :\"); for(i=1;i<=n;i++)

printf(\"%-4d\printf(\"\\n\");}

五、 调试过程

补充：scanf(\"%d\

printf(\"请输入数据:\\n\");

- 6 -

for(i=1;i<=n;i++) 不然程序无法正常运行。

六、 实验结果

测试数据：key[d]:3,2,1,5 key[d]:11,21,31,12

key[d]:35,4,6,9 key[d]:10,13,8

实验结果：基数排序：9

堆排序：112 12 9 5 快速排序：5 9 12 112

实验截图：

七、 总结

通过这次实验，相对掌握了这三个程序的算法实现，同时也加深了对排序的理解，把三个算法放在一起做比较，它们适用于不同的环境，不同的辅助空间的量下使用，可以从程序的时间复杂度这是衡量排序算法的最重要的因素）比较出了三个算法的优劣性。

附录：

参考文献

[1]谭浩强、张基温等《C语言程序设计（第三版）》，北京：高等教育出版社， 2007； [2]宁正元、王秀娟《算法与数据结构》， 北京：清华大学出版社， 2006； [3]严蔚敏、佩娟等《数据结构》，北京：国防工业出版社， 1981；

- 7 -