数据结构课程设计排序算法演示系统

1、1. 设计目的随着计算机技术的发展，各种排序算法不断的被提出。排序算法在计算机科学中有非常重要的意义，且应用很广泛。在以后的发展中排序对我们的学习和生活的影响会逐渐增大，很有必要学习排序知识。此次课程设计一方面使自己掌握排序的知识，另一方面锻炼一下团队合作开发系统的能力。2.1 设计内容和要求设计内容：（1）实现各种内部排序。包括直接插入排序，希尔排序，冒泡排序，快速排序，直接选择排序，归并排序，堆排序。（2）待排序的元素的关键字为整数或（字符）。可用随机数据和用户输入数据作测试比较。比较的指标为有关键字参加的比较次数和关键字的移动次数(关键字交换以3次计)。（3）演示程序以人机对话的形式进行

2、。每次测试完毕显示各种比较指标值的列表，以便比较各种排序的优劣。3. 本设计所采用的数据结构typedef struct int key;RecType;4. 功能模块详细设计4.1 详细设计思想主函数：#include#include#include #define L 8 /排序元素个数#define FALSE 0#define TRUE 1typedef struct int key; RecType;RecType RL;int num; int sum;int sun; /定义排序趟数的全局变量 /主函数int main() Seqlist S; int i,k; char ch1

3、,ch2,q; printf(ntt 排序算法演示系统nntt请输入%d个待排序的数据：,L);for(i=1;i=L;i+) scanf(%d,&Si.key); getchar(); printf(tt); ch1=y; while(ch1=y) printf(n); printf(ntt 菜 单 n); printf(ntt*n); printf(ntt 1-更新排序数据 2-直接插入排序 n); printf(ntt 3-希 尔 排 序 4-冒 泡 排 序 n); printf(ntt 5-快 速 排 序 6-直接选择排序 n); printf(ntt 7-堆 排 序 8-归 并 排

4、序 n); printf(ntt * 0-退 出 * n); printf(ntt*n); printf(ntt请选择:); scanf(%c,&ch2); getchar(); for(i=1;i=L;i+) Ri.key=Si.key; switch(ch2) case 1: printf(ntt请输入%d个待排序数据ntt,L); for(i=1;i=L;i+) scanf(%d,&Si.key); getchar(); printf(tt); printf(ntt数据输入完毕！); break; case 2: Insertsort(); break; case 3: Shellsor

5、t(); break; case 4: Bubblesort(); break; case 5: printf(ntt原始数据为（按回车键开始排序）：ntt); for(k=1;k=L;k+) printf(%5d,Rk.key); getchar(); printf(n); num=0;sun=0;sum=0; Quicksort(1,L); printf(ntt排序最终结果是：ntt); for(k=1;k=L;k+) printf(%5d,Rk.key); printf(ntt比较次数是：%dntt,sum);printf(ntt交换次数是：%dntt,sun); break; case

6、 6: Selectsort(); break; case 7: Heap(); break;case 8: Mergesort(); break; case 0: ch1=n; break; default: system(cls);/清屏 printf(ntt对不起，您输入有误，请重新输入！n); break; if(ch2!=0) if(ch2=2|ch2=3|ch2=4|ch2=5|ch2=6|ch2=7|ch2=8) printf(nntt排序完毕！); printf(ntt按回车键继续！); q=getchar(); if(q!=n) getchar(); ch1=n; retur

7、n 1;/系统主界面4.1.1 冒泡排序核心思想 依次比较相邻的两个数，将小数放在前面，大数放在后面，第一轮比较后，最大的数便被放到了最后；第二轮操作前n-1个数据（假设有n个数据），依然是依次比较相邻的两个数，将小数放在前面，大数放在后面，倒数第二个数便是第二大的数；同理第i轮操作前n-i+1的数据（假设i取值是从1开始的），则n-i+i位置上的数据为第i大的数据。一共有n-1轮，第i轮比较中共比较n-i次比较。核心代码void Bubblesort() int i,j,k,x=0,y=0,m=0; int exchange=TRUE;/标志位exchange初始化为TRUE 1 print

8、f(ntt原始数据为（按回车键开始排序）：ntt); for(k=1;k=L;k+) printf(%5d,Rk.key); getchar(); printf(n); for(i=1;iL&exchange=TRUE;i+)/外层对总的循环次数执行次数 exchange=FALSE; for(j=1;j=L+1-i;j+) /内层相邻记录的交换与比较 m+;/比较次数+ if(Rj.keyRj-1.key) R0.key=Rj.key; Rj.key=Rj-1.key; Rj-1.key=R0.key; exchange=TRUE;y+;/移动次数+ m-;/比较次数 if(exchange

9、) /输出语句 printf(tt第%d趟冒泡排序的结果为：ntt,i); for(k=1;k=L;k+) printf(%5d,Rk.key); getchar(); printf(n); printf(ntt比较次数是：tt); printf(%d,m); printf(ntt移动次数是：tt); printf(%d,y); printf(ntt排序最终结果是：ntt); for(i=1;i=L;i+) printf(%5d,Ri.key); 4.1.2 快速排序核心思想 首先检查数据列表中的数据数，如果小于两个，则直接退出程序。如果有超过两个以上的数据，就选择一个分割点将数据分成两个部分

10、，小于分割点的数据放在一组，其余的放在另一组，然后分别对两组数据排序。 通常分割点的数据是随机选取的。这样无论你的数据是否已被排列过，你所分割成的两个字列表的大小是差不多的。而只要两个子列表的大小差不多核心代码void Quicksort(int low,int high)/该程序为递归算法实现 int i=low,j=high,k; R0.key=Rlow.key; while(ij) while(ij&R0.key=Rj.key) /右侧扫描 j-; sum+; if(ij) Ri.key=Rj.key;/交换 i+;sun+; while(ij&Ri.keyR0.key)/左侧扫描 i+

11、; sum+; if(ij) Rj.key=Ri.key;/交换 j-; sun+; Ri.key=R0.key; num+; /输出语句包括排序的结果及次数 printf(tt第%d趟快速排序的结果为：ntt,num); for(k=1;k=L;k+) printf(%5d,Rk.key); getchar(); printf(n); if(lowi-1) Quicksort(low,i-1);/递归部分(左侧) if(j+1high) Quicksort(j+1,high);/递归部分(右侧)4.1.3 直接插入排序核心思想经过i-1遍处理后,L1.i-1己排好序。第i遍处理仅将Li插入L

12、1.i-1的适当位置，使得L1.i又是排好序的序列。要达到这个目的，我们可以用顺序比较的方法。首先比较Li和Li-1，如果Li-1 Li，则L1.i已排好序，第i遍处理就结束了；否则交换Li与Li-1的位置，继续比较Li-1和Li-2，直到找到某一个位置j(1ji-1)，使得Lj Lj+1时为止核心代码void Insertsort() int i,j,k,m=0,x=0; /初始化比较次数变量m，移动次数变量x printf(ntt原始数据为：ntt); for(k=1;k=L;k+) printf(%5d,Rk.key); getchar(); printf(n); /主要运行部分 for

13、(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; x+; m+; /输出语句包括排序的结果及次数 printf(tt第%d趟直接插入排序的结果为：ntt,m); for(k=1;k=L;k+) printf(%5d,Rk.key); getchar(); printf(n); printf(n); printf(ntt比较次数是：tt); printf(%d,m); printf(ntt移动次数是：tt); printf(%d,x); printf(ntt排序最终结果是

14、：ntt); for(i=1;i=L;i+) printf(%5d,Ri.key); 4.1.4 希尔排序核心思想 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2d1重复上述的分组和排序，直至所取的增量dt=1(dtdt-ld2d1)，即所有记录放在同一组中进行直接插入排序为止。核心代码void Shellsort() int i,j,gap,x,k,y=0,m=0; /初始化比较次数变量m，移动次数变量y printf(ntt原始数据为：ntt); for(k=1;k0) fo

15、r(i=gap+1;i0) if(Rj.keyRj+gap.key) x=Rj.key;/交换语句 Rj.key=Rj+gap.key; Rj+gap.key=x; j=j-gap; y+;/移动次数+ else j=0; gap=gap/2; m+;/比较次数+ /输出语句包括排序的结果及次数 printf(tt第%d趟希尔排序的结果为：ntt,m); for(k=1;k=L;k+) printf(%5d,Rk.key); getchar(); printf(n); printf(ntt比较次数是：tt); printf(%d,m); printf(ntt移动次数是：tt); printf(

16、%d,y); printf(ntt排序最终结果是：ntt); for(i=1;i=L;i+) printf(%5d,Ri.key); printf(n); 4.1.5 直接选择排序核心思想 第一次从R0Rn-1中选取最小值，与R0交换，第二次从R1Rn-1中选取最小值，与R2交换，.， 第i次从Ri-1Rn-1中选取最小值，与Ri-1交换，.，第n-1次从Rn-2Rn-1中选取最小值，与Rn-2交换,总共通过n-1次,得到一个按排序码从小到大排列的有序序列.核心代码void Selectsort() int i,j,k,h,x=0,y=0; printf(ntt原始数据为（按回车键开始排序）：

17、ntt); for(k=1;k=L;k+) printf(%5d,Rk.key); getchar(); printf(n); for(i=1;iL;i+) h=i; for(j=i+1;j=L;j+) x+; /比较次数 if(Rj.keyRh.key) h=j; /确定最小值 if(h!=i) R0.key=Ri.key; Ri.key=Rh.key; Rh.key=R0.key; y+; /移动次数 printf(tt第%d趟选择排序的结果为：ntt,i); for(k=1;k=L;k+) printf(%5d,Rk.key); getchar(); printf(n); /输出语句包括

18、排序的结果及次数 printf(ntt比较次数：%d,x); printf(ntt移动次数：%d,y); printf(ntt排序最终结果是：ntt); for(i=1;i=L;i+) printf(%5d,Ri.key); printf(n); 4.1.6 堆排序核心思想 堆排序是一树形选择排序，在排序过程中，将R1.N看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。将原始记录序列建成一个堆，成为初始堆，并输出堆顶元素；调整剩余的记录序列，使之成为一个新堆，再输出堆顶元素；如此反复进行，当堆中只有一个元素时，整个序列的排序结束，输出的序列

19、便是原始序列的非递减有序序列。在堆排序的过程中，主要负责两方面的工作：一是如何将原始记录序列构造成一个堆，即建立初始堆；二是输出堆顶元素后，如何将剩余记录整理成一个新堆。核心代码/建堆void CreateHeap(int root,int index,int *x,int *y) int j,temp,finish; j=2*root; /j指向左孩子 temp=Rroot.key; finish=0; while(j=index&finish=0) if(jindex) if(Rj.key=Rj.key) finish=1; else Rj/2.key=Rj.key; (*y)+; j=j

20、*2; *x = *x+2; Rj/2.key=temp; (*y)+;/堆排序void Heapsort() int i,j,temp,k,x=0,y=0; for(i=(L/2);i=1;i-) /建立初始堆 CreateHeap(i,L,&x,&y); x=0; y=0; for(i=L-1,k=1;i=1;i-,k+) /将堆中根节点和最后一个节点交换 temp=Ri+1.key; Ri+1.key=R1.key; R1.key=temp; CreateHeap(1,i,&x,&y); printf(tt第%d趟堆排序的结果为：ntt,k); for(j=1;j=L;j+) print

21、f(%5d,Rj.key); getchar(); printf(n); printf(ntt比较次数是：%dtt,x); printf(ntt移动次数是：%dtt,y);void Heap() int i; printf(ntt原始数据为（按回车键开始排序）：ntt); for(i=1;i=L;i+) printf(%5d,Ri.key); getchar(); printf(n); Heapsort(); printf(ntt排序最终结果是：ntt); for(i=1;i=L;i+) printf(%5d,Ri.key); printf(n);4.1.7 归并排序核心思想将有n个记录的原始

22、序列看作n个有序子序列，每个子序列的长度为1，然后从第一个子序列开始，把相邻的子序列两两合并，得到n/2个长度为2或1的子序列（当子序列个数为奇数时，最后一组合并得到的序列长度为1），把这一过程称为一次归并排序，对第一次归并排序后的n/2个子序列采用上述方法继续顺序成对归并，如此重复，当最后得到的长度为n的一个子序列时，该子序列便是原始序列归并排序后的有序序列。核心代码void Merge(int low,int mm,int high,int *x,int *y)/两个有序序列的合并 int i=low,j=mm+1,p=0; RecType *R1; /i对第一个开始到结尾，j从第二个开始到结尾 R1=new RecTypehigh-low+1; if(!R1) printf(内存不足！); while(i=mm&j=high)/两序列从起始位置开始将小的元素放入到R1中 R1p+=(Ri.key=Rj.key)?Ri+:Rj+; (*x)+; (*y)+; while(i=mm