《(完整word版)数据结构实验9：排序子系统.doc》由会员分享，可在线阅读，更多相关《(完整word版)数据结构实验9：排序子系统.doc（30页珍藏版）》请在金锄头文库上搜索。
1、(完整word版)数据结构实验9：排序子系统实验9：排序子系统1实验目的（1）掌握常用排序方法的基本思想。（2）通过实验加深理解各种排序算法。（3）通过实验掌握各种排序方法的时间复杂度分析。（4）了解各种排序方法的优缺点及适用范围。2实验内容（1）编写直接插入排序程序。（2）编写希尔排序程序。（3）编写冒泡排序程序。（4）编写快速排序程序。（5）编写选择排序程序。（6）编写归并排序程序。（7）编写堆排序程序。（8）程序执行时，要求能显示每一趟的排序结果。（9）设计一个选择式菜单，以菜单方式选择上述排序程序。 排 序 子 系 统 * * 1-更新排序数据 * * 2-直接插入排序 * * 3-希
2、 尔 排 序 * * 4-冒 泡 排 序 * * 5-快 速 排 序 * * 6-选 择 排 序 * * 7-归 并 排 序 * * 8-堆 排 序 * * 0-返 回 * *请选择菜单号（0-8）：3实验程序 #include#include#include#define L 8#define FALSE 0#define TURE 1typedef structint key;char otherinfo;RecType;typedef RecType SeqlistL+1;int num;Seqlist R;void Insertsort();void Bubblesort();void
3、 QuickSort(int low,int high);void Shellsort();void Selectsort();void Mergesort();int Partition(int i,int j);void Heap();void main()Seqlist S;int i,k;char ch1,ch2,q;printf(nt请输入%d个待排序数据（按【Enter】键分隔）：nt,L);for(i=1;i=L;i+)scanf(%d,&Si.key); getchar();printf(t);printf(nt排序数据已经输入完毕！);ch1=y;while(ch1=y|ch
4、1=Y)printf(n);printf(ntt 排 序 子 系 统 );printf(ntt*);printf(ntt* 1-更新排序数据 *);printf(ntt* 2-直接插入排序 *);printf(ntt* 3-希 尔 排 序 *);printf(ntt* 4-冒 泡 排 序 *);printf(ntt* 5-快 速 排 序 *);printf(ntt* 6-选 择 排 序 *);printf(ntt* 7-归 并 排 序 *);printf(ntt* 8-堆 排 序 *);printf(ntt* 0-返 回 *);printf(ntt*);printf(ntt请选择菜单号（0-8
5、）：);scanf(%c,&ch2);getchar();for(i=1;i=L;i+)Ri.key=Si.key;switch(ch2)case 1:printf(nt请输入%d个待排序数据（按【Enter】键分隔）：nt,L);for(i=1;i=L;i+)scanf(%d,&Si.key);getchar();printf(t);printf(nt排序数据已经输入完毕！);break;case 2:Insertsort();break;case 3:Shellsort();break;case 4:Bubblesort();break;case 5:printf(nt原始数据为（按【En
6、ter】键开始排序）：);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);num=0;QuickSort(1,L);printf(nt排序的最终结果是：);for(k=1;k=L;k+)printf(%5d,Rk.key);printf(n);break;case 6:Selectsort();break;case 7:Mergesort();break;case 8:Heap();break;case 0:ch1=n;break;default:printf(nt输入出错！);if(ch2!=0)if(ch2=2|ch2=3|ch2
7、=4|ch2=5|ch2=6|ch2=7|ch2=8)printf(nt排序输出完毕！);printf(nnt按回车键返回。);q=getchar();if(q!=xA)getchar();ch1=n;void Insertsort()int i,j,k,m=0;printf(nt原始数据为（按【Enter】键开始排序）：);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);for(i=2;i=L;i+)if(Ri.keyRi-1.key)R0=Ri;j=i-1;while(R0.keyRj.key)Rj+1=Rj;j-;Rj+1=R0
8、;m+;printf(t第%d趟排序结果为（按【Enter】键继续）：,m);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);printf(nt排序的最终结果是：);for(i=1;i=L;i+)printf(%5d,Ri.key);printf(n);void Shellsort()int i,j,gap,x,m=0,k;printf(nt原始数据为（按【Enter】键开始排序）：);for(k=1;k0)for(i=gap+1;i0)if(Rj.keyRj+gap.key)x=Rj.key;Rj.key=Rj+gap.key;Rj
9、+gap.key=x;j=j-gap;elsej=0;gap=gap/2;m+;printf(t第%d趟排序结果为（按【Enter】键继续）：,m);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);printf(nt排序的最终结果是：);for(i=1;i=L;i+)printf(%5d,Ri.key);printf(n);void Bubblesort()int i,j,k;int exchange;printf(nt原始数据为（按【Enter】键开始排序）：);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);for(i=1;i=i+1;j-)if(Rj.keyRj-1.key
