福建农林大学实验报告
系（教研室）计算机专业：：姓名：实验时间：学号：年级：实验室号：_指导教师签字：实验课程：计算机号：成绩：
快速、基数）实验五（快速、堆、基数）排序算法的设计
一、实验目的和要求
实验目的：
1深刻理解排序的定义和各种排序方法的特点，并能灵活运用。2掌握常用的排序方法，并掌握用高级语言实现排序算法的方法。3了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的性能的分析方法。
实验要求：
要求彻底弄懂排序的物理存储结构，并通过此试验为以后的现实使用打下基础。
二、实验内容和原理
（1）实验内容：）实验内容：设计快速排序，堆排序和基数排序的算法。（2）实验原理）实验原理：快速排序：在待排序的
个数据中，任取一个数据为基准，经过一次排序后以基准数据把全部数据分为两部分，所有数值比基准数小的都排在其前面，比它大的都排在其后，然后对这两部分分别重复这样的过程，直到全部到为为止。堆排序：对待排序的
个数据，依它们的值大小按堆的定义排成一个序列，从而输出堆顶的最小值数据（按最小值跟堆排序），然后对剩余的数据再次建堆，便得到次小的，如此反复进行输出和建堆，直到全部排成有序列。基数排序：LSD法：先按最低关键字位k1对待排序数据中的
个值进行排序，按k1值把待排序文件中的
个记录分配到具有不同k1值的若干个堆，然后按k1值从小到大的次序收集在一起，下次再按高一位关键子位k2的值进行分配和收集，如此不断地按更高一位关键字位进行分配和收集，直到用k
分配和收集之后，整个数据按多关键字位有序。
三、实验环境
硬件：（1）学生用微机（2）多媒体教室或远程教学（3）局域网环境软件：（1）Wi
dowsXP中文操作系统（2）TurboC30
四、算法描述及实验步骤
1
f1、算法描述
快速排序算法描述：用两个变量ij分别指向待排序列的第一个记录和最后一个记录；先将第一个记录保存到R0中，然后j从最后一个记录起向前扫描，直到找到RjkeyR0key的记录时，将RJ移到Ri中，i自i1向后扫描直到找到满足RikeyR0key时Ri移到Rj中；就这样j自j1从后向前扫描一次移入一个Rj于Ri中，自i1向后扫描一次移入一个Ri于Rj中，i反复交替地扫描和移到记录直到ij时把R0给Ri中，他把整个待排序区间分割为两个更小的序列，再将以上过程，直到区间为大小为1时，排序结束。堆排序算法描述：堆排序分为建r