没有合适的资源?快使用搜索试试~ 我知道了~
算法与数据结构实验五 (快速、堆、基数)排序算法的设计
5星 · 超过95%的资源 需积分: 16 11 下载量 123 浏览量
2011-05-24
23:16:47
上传
评论
收藏 137KB DOC 举报
温馨提示
试读
11页
(1)实验内容: 设计快速排序,堆排序和基数排序的算法。 (2)实验原理: 快速排序:在待排序的n个数据中,任取一个数据为基准,经过一次排序后以基准数据把全部数据分为两部分,所有数值比基准数小的都排在其前面,比它大的都排在其后,然后对这两部分分别重复这样的过程,直到全部到为为止。堆排序:对待排序的n个数据,依它们的值大小按堆的定义排成一个序列,从而输出堆顶的最小值数据(按最小值跟堆排序),然后对剩余的数据再次建堆,便得到次小的,如此反复进行输出和建堆,直到全部排成有序列。基数排序:LSD法:先按最低关键字位k1对待排序数据中的n个值进行排序,按k1值把待排序文件中的n个记录分配到具有不同k1值的若干个堆,然后按k1值从小到大的次序收集在一起,下次再按高一位关键子位k2的值进行分配和收集,如此不断地按更高一位关键字位进行分配和收集,直到用kn分配和收集之后,整个数据按多关键字位有序。
资源推荐
资源详情
资源评论
福建农林大学金山学院实验报告
系: 计算机系 专业: 计算机科学与技术 年级: 08
级
姓名: 学号: 实验室号 607 计算机号 A3
实验时间: 2010- 6-2 指导教师签字: 成绩:
实验五 (快速、堆、基数)排序算法的设计
一、 实验目的和要求
实验目的:
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)描述:先定义 key 的类型以及数组 r[ ]的范围。
1、快速排序:设两个指示器变量 i 和 j,分别指向待排序区间的第一个记录和最后一个
记录;先将第一个记录移到暂存变量 x 中,然后 j 从区间的最后一个记录起向前扫描,直
到找到满足 a[j].key<x.key 的记录时,将 a[j]移入 a[i]中;再令 i 自 i+1 起向后扫描,直到找
到满足 a[i].key>x.key 的记录时,将 a[i]移入 a[j]中;就这样 j 自 j-1 从后向前扫描一次移入
一个 a[j]于 a[i]中,i 自 i+1 从前向后扫描一次移入一个 a[i]于 a[j]中,反复交替地扫描和移
入记录;直到 i=j 时把 x 移入 a[i]中(区间中第一个记录应在的位置),它把整个待排序区
间分割为相互独立的两个更小的区间。对于待排序的 a[ ]利用一次分割区间排序算法时,
令 l=1 和 h=n 即可完成第一趟排序;由此得到两个更小的区间 a[1,…,i-1]和 a[i+1,
…,n],继续利用算法 hoare 分割为更小的 4 个区间;如此一直进行下去,直到都分割为只
有一个记录是排序结束。
2、堆排序:先建立调整堆的函数:定义临时工作单元 x 以及局部变量 j,把待筛记录 a[i]送
临时工作单元 x 中,j 初始化为 2i 即指向待筛记录的左孩子。接着进行逐层向下筛选,如果
a[j].key>a[j+1].key,让 j 指向左孩子;如果 a[j].key<x.key,向下筛选,得 a[i].key=a[j].key,
令 i=j 为继续向下筛做准备,否则 j=m+1 即筛选结束,准备退出循环。把 x 移入 a[i]中。
再进行堆排序:定义循环变量 i,v 以及用于记录交换的临时工作单元 x;n-1 次输出堆顶记
录并调整堆,使得 a[i].key=a[i-1].key,调用筛选算法建立初始堆 heap(a,i,n)。v-2 次输出堆
顶记录并调整堆,把 a[1]移入 x 中,a[v]移入 a[1]中,x 移入 a[v]中,调用筛选算法重建堆。
3、基数排序:先定义分离关键字倒数第 i 位有效数字的算法,可根据基数的位数来调整关
键字位的范围。在进行基数排序算法:算法中待排序 a[ ]中以静态链表方式存储,第一个
结点为 a[0];f[0..9]和 e[0..9]分别为基数的队头和队尾指针数组,p 始终指向待排序单链表
的第一个结点,在经过 d 趟分配和收集后,返回指向排序结果单链表的第一个结点的指针
值 p。
(2)算法流程图:
快速排序:分区处理函数: 非递归的快速排序:
N
Y
Y N N
Y
Begin
i=l; j=h;
x.key=a[i].key;
(i<j)&&(a[j].key>=x.key
)
j=j-1;
a[i].key=a[j].key;
i=i+1;
(i<j)&&(a[j].key<=x.key
)
top==
0
l=0;h=n-1;
tag=1;top=0;
l<
h
i=hoare(a,l,h);
top=top+1;
s[top][0]=i+1;
s[top][1]=h;h=h-1;
tag=0
l=s[top][0];
h=s[top][1];
top=top-1;
递归的快速排序:
N
Y Y
N
堆排序:调整堆的函数: 基数排序:分离关键字倒数第 i 位有效数字的算法
堆排序算法实现:
Y
N
Y
N
Y Y
N
Y
N
Y
N
Y
i=i+1;
a[j].key=a[i].key;
j=j-1;
a[i].key=x.key;
return(i);
i<j
tag==1
int i;
l<h
i=hoare(a,l,h);
quick2(a,l,i-1);
quick2(a,i+1,h);
End
begin
j<=m
j<m
a[j].key>a[j+1].k
ey
j=j+1
a[j].key<x.ke
y
a[i].key=a[j].key;
i=j; j=2*i;
j=m+1
a[i].key=x.key
i
a[i].key=r[i-
1].key;
a[i].point=i+1;
x=m%10
i=1
x=m%100
x=m%1000
x=m%10000
Begin
j=0
f[j]=0; e[j]=0;
i=i+1
i=1
j<=1
0
i<=
d
i<=
n
a[n].point=0; p=1;输出 d ,
输出基数排序结果
k=yx(a[p].key,i)
p!
=0
剩余10页未读,继续阅读
资源评论
- taoyi35132013-11-29里面有好几种算法,还有相应的算法流程图,比较详细
hgyyj
- 粉丝: 0
- 资源: 6
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 基于springboot+vue实现的在线考试系统+源代码+文档
- RTL8723DS 2022 版本 Linux驱动,android驱动 支持4.0-10x
- 要玩NDS的遊戲,必須要先下載三個bios檔案到你的檔案資料夾
- 各类型数据库4月排名,基于排名网站数据爬虫json结果
- 基于springboot+vue实现的在线考试系统+源代码+文档
- 淮北市杜集区人才补贴+生活补贴
- JAVA-JSP技术文档
- 课内实验02-决策表(共享单车月卡).docx
- 基于【React + Node+SpringBoot】疫情数据查看系统的设计与实现【源码+lw+部署+讲解】
- 基于【React + Node】云课堂系统设计与实现【源码+lw+部署+讲解】
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功