数据结构实验报告-排序算法.pdf

数据结构实验报告-排序算法--

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

一、实验目的和要求

实验目的：

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（排序结束）
堆排序：43336182（初始状态）72
堆排序：
例：初始值61211108
1．把数据建成堆，n＝5,就从第三个数据开始，3,2,1个数据筛选过程如下图：

6612

121112111011

10810868

2．建立好了初始堆后，就要从最后一个元素开始，把第k个元素和根交换，然后把根筛
选一次
3．再从第--k个元素开始进行与跟交换这时，再进行筛选，直到所有的k<=0时堆排序完
毕。
基数排序：
分为两个部分，第一个分配位数，第二个收集。创建一个结构体数组用于分配时保存同
一关键位的元素。个位数字为低关键字位，十位数字为高关键字位。关键字位值的范围为
0—9，qu[i].f与qu[i].r为第i个队列的头指针和尾指针。将不qu[i].f不为空的链表相连，分
个位和十位先后进行收集。直到所有的关键字位都被分配完毕，收集完成后退出。

流程图:
（1）快速排序:

数据结构实验报告-排序算法--
数据结构实验报告-排序算法--

创建结构体数组:struct{intlow,high;}s[N0/2+1];

inttop=0,i,j,k;s[++top].low=1;s[top].high=n;

当top不为0时反复做

i=s[top].low;j=s[top--].high;k=partition(i,j);

k-1>i

yesno

s[++top].low=i;
s[top].high=k-1;

k+1<j

yesno

s[++top].low=k+1;
s[top].high=j;

调用到的partition(i,j)函数:

R[0]=R[i];

当i<j时反复做

当R[j].key>=R[0].key&&i<j时反复做

j--;count++;

R[i]=R[j];

当R[i].key<=R[0].key&&i<j时反复做

i++;count++;

R[j]=R[i];

R[i]=R[0];returni;

（2）堆排序:

数据结构实验报告-排序算法--
数据结构实验报告-排序算法--

intj

j=n/2;j--;直到j>=1时为止

sift(j,n)

j=n;j--;直到j>=2时为止

R[0]=R[1];R[1]=R[j];R[j]=R[0];sift(1,j