武汉理工大学-《数据结构》课程论文-中国好学长系列之小灰灰的爸爸

1、附件1：学 号： 课 程 设 计题 目交换排序的设计与实现学 院计算机科学与技术学院专 业软件工程专业班 级中国好学长系列姓 名小灰灰的爸爸指导教师夏红霞2013年元月25日课程设计任务书学生姓名： 专业班级： 指导教师： 夏红霞 工作单位：计算机科学与技术学院 题 目: 交换排序的设计与实现初始条件：理论：学习了数据结构课程，掌握了基本的数据结构和常用的算法；实践：软件工程系实验室提供计算机及软件开发环境。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1、系统应具备的功能：（1）随机产生1000个整数（2）实现冒泡排序、双向冒泡排序和快速排序（3）比较各种

2、交换排序的优劣2、数据结构设计；3、主要算法设计；4、编程及上机实现；5、撰写课程设计报告，包括：（1）设计题目；（2）摘要和关键字（中文和英文）；（3）正文，包括引言、需求分析、数据结构设计、算法设计、程序实现及测试、设计体会等；（4）结束语；（5）参考文献。时间安排： 2013年元月21日25日 （第21周） 元月21日 查阅资料元月22日 系统设计，数据结构设计，算法设计元月23日-24日 编程并上机调试，验收程序元月25日 撰写报告、提交报告 指导教师签名： 2013年元月21日系主任（或责任教师）签名： 2013年元月21日交换排序的设计与实现摘要：设计一个程序，要求能够产生1000

3、个随机数，分别用冒泡排序、双向冒泡排序和快速排序三种方法对它们进行排序并比较各种交换排序法的优劣。关键字： 随机数 交换排序 数据结构 算法 abstract：Design a program, can generate 1000 random numbers, respectively using bubble sort, bidirectional bubble sort and quick sort of three methods to sort them out and compared the pros and cons of various exchange sort.Keywo

4、rds：Random numbers Exchange sort Data structure Algorithm1引言1.1冒泡排序法首先将第一个关键字和第二个关键字进行比较，若为逆序，则将两关键字交换，然后比较第二个和第三个关键字，依此类推，直至第n-1个和第n个关键字相比较，结果使最大的关键字被安置到最后一个位置上，此为一趟起泡排序。然后开始第二趟起泡排序，其结果是将次大的关键字被安置到第n-1个位置上，以此类推，直至序列有序。1.2双向冒泡排序法双向冒泡排序法是在冒泡排序法的基础上改进的，首先它在将最大关键字安置在最后一个位置上后也将最小关键字安置在第一个位置，然后开始第二趟起泡排序，

5、以此类推直至序列有序，由于它让序列的两个方向同时进行排序，故称双向冒泡排序。1.3快速排序法快速排序法是一种效率很高的排序方法，适用于排序问题的规模很大但对于稳定性不作要求的情况。它的设计方法是分治法，基本思想是：在待排序列中选择一个对象作为枢轴，然后进行一趟快速排序，将序列分割为两个子序列，一个子序列的所有对象都不大于枢轴，一个都不小于枢轴。然后便对这两序列重复上面的操作，依此类推，直至所有对象都被确定了位置，即序列有序。2 需求分析本系统应具有三个功能：产生随机整数，对关键字进行排序和记录排序所比较和调换的次数。2.1产生随机数产生随机数 系统要求产生1000个整数，故采用随机函数rand

6、来实现，在主函数头文件中包含time.h和stdlib.h。系统中采用srand函数来对随机函数rand进行初始化，产生的随机数用一维数组来存储。2.2对关键字排序用冒泡排序法、双向冒泡排序法和快速排序法分别对关键字排序 2.3比较三种交换排序的优劣本实验要求比较三种交换排序的优劣，其主要评判标准是时间复杂度。数据结构中理论的分析了它们排序所用时间，而此实验用具体数据论证。3 数据结构设计3.1流程图3.2 算法设计3.2.1产生1000个随机数srand(time(NULL); /随机产生1000个1000以内的正整数 printf(随机产生1000个整数n); for(int i=0;i1

7、000;i+) ai=rand()%1000; /保证产生的整数在1000内，并存于数组a printf(%d ,ai); for(m=0;m1000;m+) bm=am; /将数组a复制到数组b,ccm=am; 3.2.2冒泡排序 对于n个关键字的起泡排序，共要进行n-1趟的排序，第i趟要对n-i+1个关键字进行排序，即key0到keyn-i，可知共有两层循环。在每一次的排序中，都定义一个临时变量temp，用以作为关键字交换时的临时存储单元。Void bubble_sort(int array) /冒泡排序法排列1000个数并记录比较和调换次数 int temp,i,j;int m=0,p=

8、0;for(j=0;j999;j+)for(i=0;iarrayi+1)temp=arrayi;arrayi=arrayi+1;arrayi+1=temp;+m; +p; printf(冒泡排序结果:n); for(j=0;j1000;j+)printf(%d ,arrayj);printf(n);3.2.3记录冒泡排序法的对调次数与比较次数printf(n*n);printf(nntt冒泡排序的对调次数：%d nn,m);printf(tt冒泡排序的比较次数：%d nn,p);3.2.4双向冒泡排序 对于n个关键字的冒泡排序，共要进行n-1趟的排序，第i趟要对n-i+1个关键字进行排序，即k

9、ey0到keyn-i，且每次正向排序后马上反向排序，可知共有两层循环。在每一次的排序中，都定义一个临时变量t，用以作为关键字交换时的临时存储单元。void maopao(int source,int n) /双向冒泡排序法排列1000个数并记录比较和调换次数 int start=0,end=n-1; int i,k=0,l=0; while(start=end)/*如果还有元素没有确定其位置*/ for(i=start;isourcei+1) int t; t=sourcei; sourcei=sourcei+1; sourcei+1=t; +k; +l; end-;/*找到最大数*/ for

10、(i=end;istart;i-)/*寻找剩余元素的最小元素*/ if(sourceisourcei-1) int t; t=sourcei; sourcei=sourcei-1; sourcei-1=t; +k; +l; start+;/*找到一个最小数*/ printf(双向冒泡排序结果:n); for(int j=0;j1000;j+) printf(%d ,sourcej); printf(n);3.2.5记录双向冒泡排序法的对调次数与比较次数printf(n*n);printf(nntt双向冒泡排序的对调次数：%dnn,k);printf(tt双向冒泡排序的比较次数：%dnn,l);

11、3.2.6快速排序快速排序中需要选取一个枢轴，枢轴不需要随着关键字移动，故可将它暂寄在temp，还需要定义两个指针l和r。排序分两个函数实现，一个是递归形式的快速排序，另一个是一趟快速排序。在对由枢轴分割的子序列进行排序时，依赖于前者对后者的调用来实现，后者完成具体的排序过程。void q_sort(int R, int l, int r,int &a,int &b) /快速排序法排列1000个数并记录比较和调换次数 int temp;int i=l,j=r;if(li&Rjtemp) -j;if(ij) Ri=Rj; +i; +a; +b; while(ij&Ritemp) +i; if(i

12、j)Rj=Ri;-j;+a; +b;Ri=temp;q_sort(R,l,i-1,a,b);q_sort(R,i+1,r,a,b);printf(快速排序结果:n); for(int j=0;j1000;j+) printf(%d ,cj); printf(n);3.2.7记录快速排序法的对调次数与比较次数printf(n*n);printf(nntt快速排序的对调次数：%dnn,change);printf(tt快速排序的比较次数：%dnn,compare); 4 程序实现及测试4.1源代码#include #include #include void bubble_sort(int arr

13、ay) int temp,i,j;int m=0,p=0;for(j=0;j999;j+)for(i=0;iarrayi+1)temp=arrayi;arrayi=arrayi+1;arrayi+1=temp;+m; +p; printf(冒泡排序结果:n); for(j=0;j1000;j+)printf(%d ,arrayj);printf(n);printf(n*n);printf(nntt冒泡排序的对调次数：%d nn,m);printf(tt冒泡排序的比较次数：%d nn,p); void maopao(int source,int n) int start=0,end=n-1; i

14、nt i,k=0,l=0; while(start=end)/*如果还有元素没有确定其位置*/ for(i=start;isourcei+1) int t; t=sourcei; sourcei=sourcei+1; sourcei+1=t; +k; +l; end-;/*找到最大数*/ for(i=end;istart;i-)/*寻找剩余元素的最小元素*/ if(sourceisourcei-1) int t; t=sourcei; sourcei=sourcei-1; sourcei-1=t; +k; +l; start+;/*找到一个最小数*/ printf(双向冒泡排序结果:n); f

15、or(int j=0;j1000;j+) printf(%d ,sourcej); printf(n); printf(n*n);printf(nntt双向冒泡排序的对调次数：%dnn,k);printf(tt双向冒泡排序的比较次数：%dnn,l); void q_sort(int R, int l, int r,int &a,int &b) int temp;int i=l,j=r;if(li&Rjtemp) -j;if(ij) Ri=Rj; +i; +a; +b; while(ij&Ritemp) +i; if(ij)Rj=Ri;-j;+a; +b;Ri=temp;q_sort(R,l,i

16、-1,a,b);q_sort(R,i+1,r,a,b); int main(void) int a1000,b1000,c1000; int change=0,compare=0; int m; srand(time(NULL); printf(随机产生1000个整数n); for(int i=0;i1000;i+) ai=rand()%1000; printf(%d ,ai); for(m=0;m1000;m+) bm=am;cm=am; printf(nn*nn); bubble_sort(a); maopao(b,1000); q_sort(c,0, 999,change,compare

17、); printf(快速排序结果:n); for(int j=0;j1000;j+) printf(%d ,cj); printf(n);printf(n*n);printf(nntt快速排序的对调次数：%dnn,change);printf(tt快速排序的比较次数：%dnn,compare); return 0; 4.2运行结果产生1000个随机数冒泡排序的结果冒泡排序的理论比较次数为n（n-1）/2=1000*(1000-1)/2=499500这与运行得出的实际值相符合双向冒泡排序的理论比较次数为n（n-1）/2=1000*(1000-1)/2=499500这与运行得出的实际值相符合快速排

18、序法的理论比较次数为n(log(2)n)/2=1000*log(2)1000/2=4985这与实际运行得出的值相近比较三种排序方法可知，冒泡排序和双向冒泡排序的调换次数和比较次数是一样的，而快速排序法则明显优于其他两种交换排序方法，其效率约为前两者的100倍。本程序由于所要排序的数较多，要用到随机函数，产生足够多的随机数；要比较两种交换排序的优劣，则要记录各种排序法所比较和调换的次数以便比较。5设计体会这个程序的设计看似简单，但实际操作起来却很麻烦，编出的程序常常无法运行，且很难找出错误，修改了很多次才能正常运行，由于这次的课程设计，我更加体会到了要将理论运用于实践是有难度的，以后要多多上机编写程序而不能总是理论上明白就行。