数据结构内排序试验报告

1、实验目的1、了解内排序都是在内存中进行的。2、为了提高数据的查找速度，需要对数据进行排序。3、掌握内排序的方法。实验内容1、 设计一个程序exp10-l.cpp实现直接插入排序算法，并输出9,8,7,6,5,4,3,2,1,0的排序 过程。(1)源程序如下所示：/文件名:exp10-1.cpp#include <stdio.h>#define MAXE 20线性表中最多元素个数typedef int KeyType;typedef char InfoType10;typedef struct记录类型KeyType key;关键字项InfoType data;/其他数据项，类型为In

2、foType RecType;void InsertSort(RecType R,int n) /园R0.n-1按递增有序进行直接插入排序int i,j,k;RecType temp;for (i=1;i<n;i+) temp=Ri; j=i-1;/从右向左在有序区R0.i-1中找Ri的插入位置while (j>=0 && temp.key<Rj.key) Rj+1=Rj;/将关键字大于Ri.key的记录后移j-; Rj+1=temp;在 j+1 处插入 Riprintf("i=%d,”,i);/输出每一趟的排序结果printf("插入 %

3、d,结果为：",temp);for (k=0;k<n;k+)printf("%3d”,Rk.key);printf("n");void main()int i,k,n=10;KeyType a=(9,8,7,6,5,4,3,2,1,0);RecType RMAXE;for (i=0;i<n;i+)Ri.key=ai;printf("初始关键字：");/输出初始关键字序列for (k=0;k<n;k+)printf("%3d”,Rk.key);printf("n");InsertSort(

4、R,n);printf("最后结果：");/输出初始关键字序列for (k=0;k<n;k+)printf("%3d",Rk.key);printf("n");(2)运行的结果如下图所示：gTHrtjTTrnTHr- rnTHrrHTT亨顶匡WK岳Wh字项屋h 0 9士口士 口士口士口士 口士 呈口士 口士口teJThL 弟># 妒#*8 7 6 5 4 3 2 10 E y键入入入入入入入入入果an±>g3 _ g，_ g3 一一 J _ g 一 g 日五 nJi 口 s 34S6789 斥e 匠F .1

5、 i -H .ll.rlli;i -HIs耳 p8 7 6 S8 9 77 8 96 7 85 6 74 5 63 4 52 3 412 30 122 3 4 5 cont inue_4 326546 549545 947 896 785e?431032103210321032103210921089109 08 92、设计一个程序exp10-2.cpp实现希尔插入排序算法，并输出9,8,7,6,5,4,3,2,1,0的排序过程。(1)源程序如下所示：/文件名：exp10-2.cpp#include <stdio.h>#define MAXE 20线性表中最多元素个数typedef

6、 int KeyType;typedef char InfoType10;typedef struct记录类型(KeyType key;关键字项InfoType data;/其他数据项，类型为InfoType RecType;void ShellSort(RecType R,int n) /希尔排序算法(int i,j,d,k;RecType temp;d=n/2;/d 取初值 n/2while (d>0)for (i=d;i<n;i+)/将Rd.n-1分别插入各组当前有序区中(j=i-d;while (j>=0 && Rj.key>Rj+d.key)(

7、temp=Rj; /Rj与 Rj+d交换Rj=Rj+d;Rj+d=temp;j=j-d;printf("d=%d: ",d); 输出每一趟的排序结果for (k=0;k<n;k+)printf("%3d”,Rk.key);printf("n");d=d/2;递减增量dvoid main()(int i,k,n=10;KeyType a=9,8,7,6,5,4,3,2,1,0;RecType RMAXE;for (i=0;i<n;i+)Ri.key=ai;printf("初始关键字：");/输出初始关键字序列for

8、 (k=0;k<n;k+)printf("%3d",Rk.key);printf("n");ShellSort(R,n);printf("最后结果：");/输出初始关键字序列for (k=0;k<n;k+)printf("%3d",Rk.key);printf("nn");(2)结果如下图所示：初始关键字：9 8 7 6 54 3 2 1 0d=5：4 3 5! 1 W 9 8? 6 5d=2：0 1 7E 3 4 5 6? 89d=l： 0 1 :；3 4 5 67 6 9最后始果

9、；012 3 45 S 7 8 9P>*ess ahv keytn continue.3、设计一个程序expIC3.cpp实现冒泡排序算法，并输出9,8,7,6,5,4,3,2,1,0的排序过程。(1)源程序如下所示：/文件名:exp10-3.cpp#include <stdio.h>#define MAXE 20线性表中最多元素个数typedef int KeyType;typedef char InfoType10;typedef struct记录类型KeyType key;关键字项InfoType data;/其他数据项，类型为InfoType RecType;void

10、 BubbleSort(RecType R,int n)/冒泡排序算法int i,j,k;RecType temp;for (i=0;i<n-1;i+)for (j=n-1;j>i;j-)/比较,找出本趟最小关键字的记录if (Rj.key<Rj-1.key)temp=Rj; /Rj与Rj-1进行交换，将最小关键字记录前移Rj=Rj-1;Rj-1=temp;printf("i=%d,冒出的最小关键字：d,结果为：”,i,Ri.key); /输出每一趟 的排序结果for (k=0;k<n;k+)printf("%2d”,Rk.key);printf(&

11、quot;n");void main()int i,k,n=10;KeyType a=9,8,7,6,5,4,3,2,1,0;RecType RMAXE;for (i=0;i<n;i+) Ri.key=ai;printf("初始关键字：");/输出初始关键字序列for (k=0;k<n;k+)printf("%2d",Rk.key);printf("n");BubbleSort(R,n);printf("最后结果：");/输出初始关键字序列for (k=0;k<n;k+)printf("%2d",Rk.key); printf("n");(2)结果如下图所示：2345678986789S589222221111111100000000B二 rrrFrnPaFHHFHpH-'fTT-l- 3 巨k EK Eh 巨k-s隹h Ek 岳 EK 士 口 士口吉吉士 口士呈口士 口吉6 4步r-专*备r-£l.变步r-g变 * * *<" / * * J 5