快速堆基数排序算法的设计.docx
《快速堆基数排序算法的设计.docx》由会员分享，可在线阅读，更多相关《快速堆基数排序算法的设计.docx（18页珍藏版）》请在冰点文库上搜索。
快速堆基数排序算法的设计
福建农林大学计算机与信息学院
实验报告
课程名称：
算法与数据结构
姓名：
邓建国
系：
计算机与信息系
专业：
网络工程
年级：
09级
学号：
091154050
指导教师：
黄思先
职称：
副教授
福建农林大学计算机与信息学院实验报告
系：
计算机与信息专业：
网络工程年级：
09级
姓名：
邓建国学号:
091154050实验室号:
计算机号:
实验五（快速、堆、基数）排序算法的设计
一、实验目的和要求
实验目的：
1.深刻理解排序的定义和各种排序方法的特点，并能灵活运用。
2.掌握常用的排序方法，并掌握用高级语言实现排序算法的方法。
3.了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的性能的分析方法。
实验要求：
要求彻底弄懂排序的物理存储结构，并通过此试验为以后的现实使用打下基础。
二、实验内容和原理：
（1）实验内容：
设计快速排序，堆排序和基数排序的算法。
（2）实验原理：
快速排序：
在待排序的n个数据中，任取一个数据为基准，经过一次排序后以基准数据把全部数据分为两部分，所有数值比基准数小的都排在其前面，比它大的都排在其后，然后对这两部分分别重复这样的过程，直到全部到为为止。
堆排序：
对待排序的n个数据，依它们的值大小按堆的定义排成一个序列，从而输出堆顶的最小值数据（按最小值跟堆排序），然后对剩余的数据再次建堆，便得到次小的，如此反复进行输出和建堆，直到全部排成有序列。
基数排序：
LSD法：
先按最低关键字位k1对待排序数据中的n个值进行排序，按k1值把待排序文件中的n个记录分配到具有不同k1值的若干个堆，然后按k1值从小到大的次序收集在一起，下次再按高一位关键子位k2的值进行分配和收集，如此不断地按更高一位关键字位进行分配和收集，直到用kn分配和收集之后，整个数据按多关键字位有序。
三、实验环境
硬件：
（1）学生用微机；
（2）多媒体实验教室；（3）局域网环境；
软件：
（1）WindowsXP中文操作系统；
（2）TurboC3.0；
四、算法描述及实验步骤
描述:
（1）快速排序:
例：
初始关键字3673659713
ij
j向左扫描后3673659713
ij
R[j]移入R[i]1373659736
ij
i向右扫描1373659736
ij
R[i]移入R[j]后1336659773
ij
i向左扫描1336659773
ij
i向左扫描1336659773
ij
i向左扫描1336659773
ij
i=j第一次结束
1次排序结束后1336659773
2次排序结束后1336659773
3次排序结束后1336657397（排序结束）
堆排序：
4333618272（初始状态）
堆排序：
例：
初始值61211108
1．把数据建成堆，n＝5,就从第三个数据开始，3,2,1个数据筛选过程如下图：
2．建立好了初始堆后，就要从最后一个元素开始，把第k个元素和根交换，然后把根筛选一次
3．再从第--k个元素开始进行与跟交换这时，再进行筛选，直到所有的k<=0时堆排序完毕。
基数排序：
分为两个部分，第一个分配位数，第二个收集。
创建一个结构体数组用于分配时保存同一关键位的元素。
个位数字为低关键字位，十位数字为高关键字位。
关键字位值的范围为0—9，qu[i].f与qu[i].r为第i个队列的头指针和尾指针。
将不qu[i].f不为空的链表相连，分个位和十位先后进行收集。
直到所有的关键字位都被分配完毕，收集完成后退出。
流程图:
（1）快速排序:
调用到的partition（i,j）函数:
（2）堆排序:
调用到的函数sift（j,n）:
（3）基数排序:
实验步骤:
[程序代码]
#include"stdlib.h"
#include"alloc.h"
#defineN030000
typedefintkeytype;
typedefstructnode/*创建待排序的数*/
{
keytypekey;/*待排序的数*/
}Element;
ElementR[N0+1];/*存储一组待排序的数*/
intn=150;/*定义随机生成数的个数为150*/
voidgetData（）/*随机产生150个数*/
{inti;
randomize（）;
for（i=1;i<=n;i++）
R[i].key=random（1000）;
}
voidprintData（）/*将getData（）函数产生的数据输出*/
{inti;
for（i=1;i<=n;i++）
{printf（"%6d",R[i].key）;/*输出数据*/
if（i%8==0）printf（"\n"）;
}
printf（"\n"）;
}
longcount;/*用来计算排序的次数*/
intpartition（inti,intj）/*快速排序的一次排序过程*/
{R[0]=R[i];/*确定分割基准*/
while（i{while（R[j].key>=R[0].key&&iR[i]=R[j];/*当扫描到小于基准关键字的数时将小的数赋给当前关键字所在的位置*/
while（R[i].key<=R[0].key&&iR[j]=R[i];/*当扫描到大于基准关键字的数时将大的数赋给当前关键字所在的位置*/
}
R[i]=R[0];/*将基准记录移入最终位置*/
returni;/*返回基准记录的最终位置*/
}
voidquickSort（）/*快速排序*/
{struct/*用来对待排序数进行区间分割*/
{intlow,high;/*把区间分割成两块，分别用low和high标记*/
}s[N0/2+1];/*最多分割成N0/2+1个区间*/
inttop=0,i,j,k;/*i，j为指示器变量*/
s[++top].low=1;
s[top].high=n;
while（top）
{i=s[top].low;
j=s[top--].high;
k=partition（i,j）;/*进行排序*/
if（k-1>i）
{s[++top].low=i;
s[top].high=k-1;
}
if（k+1{s[++top].low=k+1;
s[top].high=j;
}
}
}
voidsift（inti,intm）/*调整堆*/
{intk=2*i;/*k初始化为2i，即指向待筛记录的左孩子*/
R[0]=R[i];/*待筛记录送临时工作单元中*/
while（k<=m）/*逐层向下筛选*/
{
if（kR[k].key）k++;/*若右孩子记录关键字值小，让count指向右孩子*/
count++;
if（R[k].key>R[0].key）/*如果孩子的值大于其父亲，则进行调整*/
{R[i]=R[k];/*孩子记录上移*/
i=k;/*为继续向下筛选做准备*/
k=2*i;
count++;
}
elsebreak;/*孩子记录关键字大时，筛选结束，退出循环*/
}
R[i]=R[0];/*将最初的筛选记录填入正确位置*/
}
voidheapSort（）/*堆排序*/
{intj;/*定义循环变量*/
for（j=n/2;j>=1;j--）sift（j,n）;/*调用筛选法，初始化堆*/
for（j=n;j>=2;j--）/*n-1次输出堆顶记录并调整堆*/
{R[0]=R[1];R[1]=R[j];R[j]=R[0];/*堆顶记录与当前堆中最后一个记录交换*/
sift（1,j-1）;/*调用筛选法重建堆*/
}
}
voidradixSort（）/*基数排序*/
{typedefstructnode/*用链表来存储待排序数组*/
{keytypekey;/*数据域*/
structnode*next;/*指向下个结点的指针域*/
}ND;
struct
{ND*f,*r;/*定义队头和队尾指针*/
}qu[10];/*定义队头和队尾指针数组*/
ND*p,*head;
inti,j,k;
longdd=1;
for（i=0;i<10;i++）qu[i].f=qu[i].r=NULL;/*初始化队列为空*/
for（i=1;i<=n;i++）
{k=R[i].key/dd%10;count++;/*先取个位数进行比较*/
p=（ND*）malloc（sizeof（ND））;
if（qu[k].f==NULL）qu[k].f=qu[k].r=p;/*如果队列为空作为队头结点插入*/
else/*否则插入队尾*/
{qu[k].r->next=p;
qu[k].r=p;
}
p->key=R[i].key;/*数据给p*/
p->next=NULL;/*队尾指向NULL为后续做准备*/
}
while
（1）
{intflag=0;
i=0;
while（qu[i].f==NULL）i++;/*找第一个非空队列*/
head=qu[i].f;
while（i<9）/*控制一次的收集*/
{j=i+1;
while（j<10&&qu[j].f==NULL）j++;
count++;
if（j>=10）break;
qu[i].r->next=qu[j].f;
flag=1;i=j;
}
if（flag==0）break;/*如果没有数据，退出循环*/
for（i=0;i<10;i++）qu[i].f=qu[i].r=NULL;
p=head;dd*=10;
while（p）
{head=p->next;
k=p->key/dd%10;/*取十位数进行比较*/
count++;
if（qu[k].f==NULL）qu[k].f=qu[k].r=p;
else
{qu[k].r->next=p;qu[k].r=p;}
qu[k].r->next=NULL;p=head;
}
}
p=qu[0].f;i=1;/*p指向第一个队列的头一个*/
while（p）
{qu[0].f=p->next;
R[i++].key=p->key;
free（p）;p=qu[0].f;
}
}
main（）
{clrscr（）;
printf（"\n------------------------date-----------------------\n"）;
getData（）;/*产生随机数*/
printData（）;
count=0;/*计数器初始化为0*/
quickSort（）;
getch（）;
printf（"---------------------quickSort---------------------\n"）;
printData（）;/*输出比较后的数据*/
printf（"count=%ld\n",count）;
getch（）;
count=0;/*计数器初始化为0*/
heapSort（）;
printf（"---------------------heapSort----------------------\n"）;
printData（）;/*输出比较后的数据*/
printf（"count=%ld\n",count）;
getch（）;
count=0;/*计数器初始化为0*/
radixSort（）;/*调用基数排序函数*/
printf（"---------------------radixSort---------------------\n"）;
printData（）;
printf（"count=%ld\n",count）;
getch（）;
}
五、调试过程：
错误1：
分析原因：
修改方法：
错误2：
分析原因：
修改方法：
六．实验结果：
随机产生150个数：
快速排序：
堆排序：
基数排序：
随机产生10个数：
七、总结：
通过这次实验我学会了基数，快速和堆排序的基本思想，排序原理以及它们之间的的特点，知道了什么情况下应该用什么样的排序方法。
升级会员 