数据结构与数据库实验报告排序

1、实验数学系 2012 级日期 2013.05.03No. PB12001117 评分实验题目：排序实验目的：采用顺序结构，编程实现直接排序、排序、冒泡排序、堆排，操作过程。序等排序算法，进一步理解各种排序的算法实验分析：该实验整体思路清晰，主要算法为表的创建、各排序算法、排序的选择及排序后的输出。实验采用顺序结构，用数组来带排序的，数组类型为关键字和其他信息组成的结构体。带排序的表的定义如下：类型定义及typedefKeyType;typedef struct RecTypeKeyType key;char otherinfo100;RecType;#define MAXSIZE 100 ty

2、pedef struct SqlistRecType RMAXSIZE;length;Sqlist;算法分析：(1)、带排序的输入及 Sqlist 的建立。注意到 Sqlist 需要先申请空间。用一个for 循环读入并。具体实现算法如下：void CreateSqlist(Sqlist *L,i;L-length=n;prf(请依次输入各 for(i=1;iRi.key),&(L-Ri.otherinfo);(2)、直接排序。将待排序的Ri，到已排好序的表R1, R2 ,., Ri-1 中，得到一个新的、数增加 1 的有序表。 直到所有的都完为止。序列分设待排序的顺序存放在数组 R1n中，在排

3、序的某一时刻，将成两部分：R1i-1：已排好序的有序部分；Rin：未排好序的无序部分。具体实现算法如下：void StraightInsertSort(Sqlist *L)i,j;for(i=2;ilength;i+) L-R0=L-Ri;j=i-1;while(LT(L-R0.key,L-Rj.key) L-Rj+1=L-Rj;j-;L-Rj+1=L-R0;(3)、排序。先取一个正整数 d1(d1n)作为第一个增量，将全部 n 个分成d1 组，把所有相隔 d1 的放在一组中，即对于每个 k(k=1, 2, d1)，Rk,Rd1+k, R2d1+k , 分在同一组中，在各组内进行直接排序。这样

4、一次分组和排序过程称为一趟排序；取新的增量d2d1，重复分组和排序操作；直至所取的增量 di=1 为止，即所有放进一个组中排序为止。排序算法中需要定义一个数组存放增量，对每个增量如下：一趟排序的算法。具体实现算法void SPass(Sqlist *L,j,k;d)for(j=d+1;jlength;j+)L-R0=L-Rj;k=j-d;while(k0 & LT(L-R0.key,L-Rk.key) L-Rk+d=L-Rk;k=k-d;L-Rk+d=L-R0;void SSort(Sqlist *L)m,t,dk10;prf(请输入增量序列长度:n); scanf(%d,&t);prf(请输

5、入增量序列:n); for(m=0;mt;m+)scanf(%d,&dkm); for(m=0;mt;m+)SPass(L,dkm);(4)、冒泡排序。首先将 R1与 R2的关键字进行比较，若为反序，则交换两个记录；然后比较 R2与 R3的关键字，依此类推，直到 Rn-1与 Rn的关键字比较后为止，称为一趟冒泡排序。然后进行第二趟冒泡排序，对前n-1 个进行同样的操作。具体实现算法如下：void BubbleSort(Sqlist *L) j,k;for(j=0;jlength-1;j+) for(k=1;klength-j-1;k+)if(LT(L-Rk+1.key,L-Rk.key) L-

6、R0=L-Rk;L-Rk=L-Rk+1;L-Rk+1=L-R0;(5)、快速排序。通过一趟排序，将待排序分割成独立的两部分，其中一部分的关键字均比另一部分的关键字小，再用递归算法分别对这两部分进行下一趟排序，以达到整个序列有序。一趟快速排序的方法：从序列的两端交替扫描各个，将关键字小于基准关键字的依次放置到序列的前边；而将关键字大于基准关键字的从序列的最后端起，依次放置到序列的后边，直到扫描完所有的。设置指针 low，high，初值为第 1 个和最后一个的位置。设两个变量 i，j，初始时令 i=low，j=high，以 Rlow.key 作为基准(将 Rlow保存在R0中) 。从 j 所指位置

7、向前搜索：将 R0.key 与Rj.key 进行比较：若 R0.keyRj.key ：令 j=j-1，然后继续进行比较， 直到i=j 或R0.keyRj.key 为止；若 R0.keyRj.key ：Rj Ri，腾空 Rj的位置， 且令i=i+1；从 i 所指位置起向后搜索：将 R0.key 与 Ri.key 进行比较：若 R0.keyRi.key ：令 i=i+1，然后继续进行比较， 直到 i=j 或 R0.keyRi.key 为止；若 R0.keyR0=L-Ri;dolow,high)while(LQ(L-R0.key,L-Rj.key)&(ji)j-;if(ji)L-Ri=L-Rj;i+

8、;while(LQ(L-Ri.key,L-R0.key)&(ji) i+;if(ji)L-Rj=L-Ri;j-;while(i!=j);L-Ri=L-R0;return(i);void QuickSort(Sqlist *L,k; if(lowR0=L-Rs;for(k=2*s;k=m;k=2*k)m)if(kRk.key,L-Rk+1.key)k+;if(LT(L-R0.key,L-Rk.key) L-Rs=L-Rk;s=k;else break;L-Rs=L-R0;void HeapSort(Sqlist *L)j;for(j=L-length/2;j0;j-)HeapAdjust(L,j

9、,L-length); for(j=L-length;j1;j-)L-R0=L-R1;L-R1=L-Rj;L-Rj=L-R0;HeapAdjust(L,1,j-1);(7)、菜单建立。调用 switch 函数实现。源程序：#include#include #define MAXSIZE 100 #define LT(a,b) (a)(b)#define LQ(a,b) (a)length=n;prf(请依次输入各 for(i=1;iRi.key),&(L-Ri.otherinfo);void StraightInsertSort(Sqlist *L) i,j;for(i=2;ilength;i

10、+) L-R0=L-Ri;j=i-1;while(LT(L-R0.key,L-Rj.key) L-Rj+1=L-Rj;j-;L-Rj+1=L-R0;void SPass(Sqlist *L,j,k;d)for(j=d+1;jlength;j+)L-R0=L-Rj;k=j-d;while(k0 & LT(L-R0.key,L-Rk.key) L-Rk+d=L-Rk;k=k-d;L-Rk+d=L-R0;void SSort(Sqlist *L)m,t,dk10;prf(请输入增量序列长度:n); scanf(%d,&t);prf(请输入增量序列:n); for(m=0;mt;m+)scanf(%d

11、,&dkm); for(m=0;mt;m+)SPass(L,dkm);void BubbleSort(Sqlist *L) j,k;for(j=0;jlength-1;j+) for(k=1;klength-j-1;k+)if(LT(L-Rk+1.key,L-Rk.key) L-R0=L-Rk;L-Rk=L-Rk+1;L-Rk+1=L-R0;QuickOnePass(Sqlist *L,i=low,j=high; L-R0=L-Ri;dolow,high)while(LQ(L-R0.key,L-Rj.key)&(ji)j-;if(ji)L-Ri=L-Rj;i+;while(LQ(L-Ri.ke

12、y,L-R0.key)&(ji) i+;if(ji)L-Rj=L-Ri;j-;while(i!=j);L-Ri=L-R0;return(i);void QuickSort(Sqlist *L,k; if(lowR0=L-Rs;for(k=2*s;k=m;k=2*k)m)if(kRk.key,L-Rk+1.key)k+;if(LT(L-R0.key,L-Rk.key) L-Rs=L-Rk;s=k;else break;L-Rs=L-R0;void HeapSort(Sqlist *L)j;for(j=L-length/2;j0;j-)HeapAdjust(L,j,L-length); for(j

13、=L-length;j1;j-)L-R0=L-R1;L-R1=L-Rj;L-Rj=L-R0;HeapAdjust(L,1,j-1);void main()Sqlist *L; i,j,n;L=(Sqlist *)malloc(sizeof(Sqlist);prf(请输入 scanf(%d,&n); CreateSqlist(L,n);长度:n);prf(-菜单n);prf(1直接排序n);prf(2-排序n);prf(3冒泡排序n);prf(4快速排序n);prf(5堆排序n);prf(请选择:n);scanf(%d,&i); switch(i)case 1:StraightInsertSort(L);break;case 2:SSort(L);break;case 3:case 4:case 5:BubbleSort(L);break;QuickSort(L,1,n);break; HeapSort(L);break;for(j=1;jRj.key,L-Rj.otherinfo); free(L);运行结果：调试分析与体会：1、 开始时建立表的算法无法完