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

《数据结构实验报告-排序算法.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、实验五（快速、堆、基数）排序算法的设计一、实验目的和要求实验目的：1.深刻理解排序的定义和各种排序方法的特点，并能灵活运用。2.掌握常用的排序方法，并掌握用高级语言实现排序算法的方法。3.了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的性能的分析方法。实验要求：要求彻底弄懂排序的物理存储结构，并通过此试验为以后的现实使用打下基础。二、实验内容和原理：（1）实验内容：设计快速排序，堆排序和基数排序的算法。（2）实验原理：快速排序：在待排序的n个数据中，任取一个数据为基准，经过一次排序后以基准数据把全部数据分为两部分，所有数值比基准数小的都排在其前面，比它大的

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

3、序。三、实验环境硬件：（1）学生用微机；（2）多媒体实验教室；（3）局域网环境；软件：（1）WindowsXP中文操作系统；（2）TurboC3.0；四、算法描述及实验步骤描述:（1）快速排序:例：初始关键字3673659713ijj向左扫描后3673659713ijR[j]移入R[i]1373659736iji向右扫描1373659736ijR[i]移入R[j]后1336659773iji向左扫描1336659773iji向左扫描1336659773iji向左扫描1336659773iji=j第一次结束1次排序结束后13366597732次排序结束后1336659

4、7733次排序结束后1336657397（排序结束）堆排序：4333618272（初始状态）堆排序：例：初始值612111081．把数据建成堆，n＝5,就从第三个数据开始，3,2,1个数据筛选过程如下图：6121110861211108121011682．建立好了初始堆后，就要从最后一个元素开始，把第k个元素和根交换，然后把根筛选一次3．再从第--k个元素开始进行与跟交换这时，再进行筛选，直到所有的k<=0时堆排序完毕。基数排序：分为两个部分，第一个分配位数，第二个收集。创建一个结构体数组用于分配时保存同一关键位的元素。个位数字为低关键字位，十位数字为高关键字位。关

5、键字位值的范围为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);s[++top].low=k+1;s[top].high=j;s[++top

6、].low=i;s[top].high=k-1;k-1>iyesnok+1=R[0].key&&i=1时为止sift(j,n)j=n;j--;直到j>=2时为止R[0]=R[1];R[1]=R[j];R[j]=R[0]

7、;sift(1,j-1);调用到的函数sift(j,n):intk=2*i;R[0]=R[i];当k<=m时反复做kR[k].keyyesnocount++R[i]=R[k];i=k;k=2*i;count++;break;k++R[k].key>R[0].keyYesnoR[i]=R[0];（3）基数排序:typedefstructnode{keytypekey;structnode*next;}ND;struct{ND*f,*r;}qu[10];ND*p,*head;inti,j,k;longdd=1;当值为1时反复做i=0;i