数据结构课程设计排序算法集成

1、xx大学本科生课程设计论文题 目：排序算法集成学生姓名：学 号：专 业：计算机班 级： 指导教师： 2013年 5月20日xx大学课程设计任务书课程名称数据结构课程设计设计题目排序算法集成指导教师时间一、教学要求1. 掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力4. 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风二、设计资料及参数每个学生在教师提供的课程设计题目中任意选择一题，独立完成，题目选定后

2、不可更换。排序算法集成定义动态数组类（或类模板）以表示待排序数据，在此基础上实现多种排序算法。要求设计函数模板来实现下列排序算法：v 直接插入排序v 冒泡排序v 简单选择排序v 希尔排序v 快速排序v 堆排序 并设计主函数测试动态数组类（或类模板），测试各排序算法的函数模板。三、设计要求及成果1. 分析课程设计题目的要求2. 写出详细设计说明3. 编写程序代码，调试程序使其能正确运行4. 设计完成的软件要便于操作和使用5. 设计完成后提交课程设计报告四、进度安排资料查阅与讨论（1天）系统分析（2天）系统的开发与测试（5天）编写课程设计说明书和验收（2天）五、评分标准1. 根据平时上机考勤、表现

3、和进度，教师将每天点名和检查2. 根据课程设计完成情况，必须有可运行的软件。3. 根据课程设计报告的质量，如有雷同，则所有雷同的所有人均判为不及格。4. 根据答辩的情况，应能够以清晰的思路和准确、简练的语言叙述自己的设计和回答教师的提问六、建议参考资料1数据结构 （C语言版）严蔚敏、吴伟民 主编 清华大学出版社 2004.112数据结构课程设计案例精编（用C/C+描述），李建学 等 编著，清华大学出版社 2007.23.数据结构:用面向对象方法与C+语言描述，殷人昆 主编， 清华大学出版社 2007.6目 录目 录3引言4一算法的设计思想4二算法的流程图4三算法的设计与分析53.1建

4、立数组53.2 算法思想53.3主要函数63.4主要函数声明63.5 主要变量说明10四程序源代码11五运行结果与分析（测试）18六总结（收获与体会）20七参考文献21引 言本课程设计主要解决几种不同排序方法以及在各种不同排序的过程中某一趟的具体排序结果。通过观察各种排序的具体排序过程，加深对不同排序方法的认识，加深对不同排序算法的掌握。一算法设计的思想数据结构是与数据相关的一门重要学科，不论是想通过升学考试还是想把程序编得有水平，都要对这门学科下一点功夫才行。而课程设计是让我们更好的掌握这门学科的重要方式。排序是计算机程序中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列重新排列

5、成一个按关键字有序的序列 。而内部排序中包括各种不同的排序，本课程设计主要讨论的是插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序。 完成这几种排序最主要的就是弄好不同排序的算法，只有深刻的认识了这不同排序的算法，才能了解不同排序的优点与缺点。通过对不同排序算法的分析，了解它们的优劣特点。据对题目的分析，首先要根据插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序的不同算法，写出实现各个排序算法的函数。然后通过在主函数中对不同排序的子函数的调用来实现对某个序列的具体排序。内部排序的方法很多，但就其全面性而言，很难提出一种被认为是最好的方法，每一种方法都有各自的优缺点，适合不同的环

6、境。通常，在排序的过程中需进行两种基本操作：（1）比较两个关键字的大小；（2）将记录从一个位置移动至另一位置。前一个操作对大多数排序方法来说都是必要的，而后一个操作可以通过改变记录的存储方式来予以避免。二算法的流程图如图2.1建立数组设计main函数建立各排序函数结束开始图2.1 主要设计思想流程图三算法的设计与分析3.1建立数组在程序中建立一个数组data ，用于存储程序运行中的数据。3.2算法思想（1）插入排序 插入排序的主要算法思想是将一个记录插入到已排好的有序表中，从而得到一个新的、记录数增1的有序表。（2）希尔排序 希尔排序的基本思想是先将整个待排记录列分割成若干子序列分别进行直接插

7、入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。（3）冒泡排序函数 冒泡排序首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序则将两个记录交换，然后比较第二个记录和第三个记录的关键字，依次类推。（4）选择排序函数 选择排序的基本思想是：每一趟在n-i+1(i=1,2,n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。（5）堆排序 先将一个序列进行建堆，然后将大顶堆的第一个元素和最后一个元素对换（或将小顶堆的最后一个元素和第一个元素对换），再对除最后一个元素的序列进行求大顶堆（或对除第一个元素的序列进行求小顶堆），依次类推。 3.3 主要函数（

8、1）插入排序函数void insertion_sort(int,int);/*插入排序*/（2）希尔排序函数void shell_sort(int,int);/*希尔排序*/（3）冒泡排序函数void bubble_sort(int,int);/*冒泡排序*/（4）选择排序函数void select_sort(int,int);/*选择排序*/（5）将数据调整为堆的函数void adjust(int,int);/*将数据调整为堆树*/3.4主要函数声明插入排序插入排序的主要算法思想是将一个记录插入到已排好的有序表中，从而得到一个新的、记录数增1的有序表。 void insertion_sort

9、(int data,int size)/*插入排序*/int base,compare,temp,i,j=0; for(base=1;base<size;base+)/*当数据小于第一个时，则插于前方，否则与后面数据对比找出插入位置*/ temp=database; compare=base; j+; while(compare>0 && datacompare-1>temp) datacompare=datacompare-1; compare-; datacompare=temp; printf("第%d 趟排序:" ,j); for(

10、i=0;i<size;i+) printf("%d ",datai); printf("n"); printf("n最终排序结果:");for(i=0;i<size;i+) printf("%d ",datai);printf("n");希尔排序希尔排序的基本思想是先将整个待排记录列分割成若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。void shell_sort(int data,int size)/*希尔排序*/int i,j

11、,k,incr,temp,num=0;incr=size/2;printf("n");while(incr>0)for(i=incr+1;i<size;i+)j=i-incr;while(j>0) if(dataj>dataj+incr)/*比较每部分的数据大小顺序不对则交换*/ temp=dataj; dataj=dataj+incr; dataj+incr=temp; j=j-incr;else j=0;num+;printf("n第%d 趟排序:",num);for(k=1;k<size;k+) printf(&quo

12、t;%d ",datak);incr=incr/2;printf("n最终排序结果：");for(i=1;i<size;i+) printf("%d ",datai);printf("n");冒泡排序冒泡排序首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序则将两个记录交换，然后比较第二个记录和第三个记录的关键字，依次类推。void bubble_sort(int data,int size)/*冒泡排序*/int i,j,flag,k,temp,num=0; for(i=0;i<size-1;i+)

13、 flag=0; for(j=0;j<size-1;j+)/*让数据两两比较，将小的置于前*/ if(dataj>dataj+1) flag=1; temp=dataj; dataj=dataj+1; dataj+1=temp; num+; printf("n第%d趟排序：",num); for(k=0;k<size;k+) printf("%d ",datak); printf("n"); printf("n最终排序结果：");for(i=0;i<size;i+) printf("

14、;%d ",datai); printf("n"); if(flag!=1) break; 选择排序选择排序的基本思想是：每一趟在n-i+1(i=1,2,n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。void select_sort(int data,int size)/*选择排序*/int base,compare,min,temp,i,num=0; for(base=0;base<size-1;base+)/*将目前数据与后面数据中最小的对调*/ min=base; for(compare=base+1;compare<size;c

15、ompare+) if(datacompare<datamin) min=compare; temp=datamin; datamin=database; database=temp; num+; printf("第%d趟排序：",num); for(i=0;i<size;i+) printf("%d ",datai); printf("n"); printf("n最终排序结果：");for(i=0;i<size;i+) printf("%d ",datai); printf(

16、"n");3.5主要变量说明 Int data :整型数组，用于储存序列 Int size:整型变量，用于记录序列长度 Int temp:整型变量，用于交换元素 Int m,n,k,i,j,num:一般整型变量四程序源代码#include<stdio.h> void insertion_sort(int,int);/*插入排序*/void shell_sort(int,int);/*希尔排序*/void bubble_sort(int,int);/*冒泡排序*/void select_sort(int,int);/*选择排序*/void adjust(int,i

17、nt);/*将数据调整为堆树*/void insertion_sort(int data,int size)/*插入排序*/int base,compare,temp,i,j=0; for(base=1;base<size;base+)/*当数据小于第一个时，则插于前方，否则与后面数据对比找出插入位置*/ temp=database; compare=base; j+; while(compare>0 && datacompare-1>temp) datacompare=datacompare-1; compare-; datacompare=temp; pr

18、intf("第%d 趟排序:" ,j); for(i=0;i<size;i+) printf("%d ",datai); printf("n"); printf("n最终排序结果:"); for(i=0;i<size;i+) printf("%d ",datai); printf("n");void shell_sort(int data,int size)/*希尔排序*/ int i,j,k,incr,temp,num=0; incr=size/2; print

19、f("n"); while(incr>0) for(i=incr+1;i<size;i+)j=i-incr; while(j>0) if(dataj>dataj+incr)/*比较每部分的数据大小顺序不对则交换*/ temp=dataj; dataj=dataj+incr; dataj+incr=temp; j=j-incr; else j=0; num+; printf("n第%d 趟排序:",num); for(k=1;k<size;k+) printf("%d ",datak); incr=incr

20、/2; printf("n最终排序结果："); for(i=1;i<size;i+) printf("%d ",datai); printf("n");void bubble_sort(int data,int size)/*冒泡排序*/int i,j,flag,k,temp,num=0; for(i=0;i<size-1;i+) flag=0; for(j=0;j<size-1;j+)/*让数据两两比较，将小的置于前*/ if(dataj>dataj+1) flag=1; temp=dataj; dataj=

21、dataj+1; dataj+1=temp; num+; printf("n第%d趟排序：",num); for(k=0;k<size;k+) printf("%d ",datak); printf("n"); printf("n最终排序结果："); for(i=0;i<size;i+) printf("%d ",datai); printf("n"); if(flag!=1) break; void select_sort(int data,int size)/

22、*选择排序*/int base,compare,min,temp,i,num=0; for(base=0;base<size-1;base+)/*将目前数据与后面数据中最小的对调*/ min=base; for(compare=base+1;compare<size;compare+) if(datacompare<datamin) min=compare; temp=datamin; datamin=database; database=temp; num+; printf("第%d趟排序：",num); for(i=0;i<size;i+) pr

23、intf("%d ",datai); printf("n"); printf("n最终排序结果："); for(i=0;i<size;i+) printf("%d ",datai); printf("n");void adjust(int i,int n)/*将数据调整为堆树*/int data20,j,k,done=0; k=datai; j=2*i; while(j<=n)&&(done=0) if(j<n)&&(dataj<dataj

24、+1)j+; if(k>=dataj)done=1; else dataj/2=dataj; j=2*j; dataj/2=k;void main()int data20; int size=0,m=0,i,j,num,k,temp,n=0; printf("n请输入初始关键字（输入0结束）:n"); do scanf("%d",&datasize); m+; while(datasize+!=0); printf("你输入的初始关键字为：");for(j=0;j<m-1;j+)printf("%d &q

25、uot;,dataj);printf("n排序方法：n");printf("n1、插入排序n");printf("n2、希尔排序n");printf("n3、冒泡排序n");printf("n4、选择排序n");printf("n5、堆排序n");printf("n请选择排序方法：n");scanf("%d",&num);switch(num)case 1: printf("*插入排序*n"); for(i=

26、0;i<50;i+)printf("-");printf("n"); insertion_sort(data,-size); for(i=0;i<50;i+)printf("-");printf("n"); break;case 2:printf("*希尔排序*n");for(m=0;m<50;m+)printf("-"); shell_sort(data,-size);for(i=0;i<50;i+)printf("-");pri

27、ntf("n"); break;case 3:printf("*冒泡排序*n");for(i=0;i<50;i+)printf("-");printf("n"); bubble_sort(data,-size); for(i=0;i<50;i+)printf("-");printf("n"); break;case 4:printf("*选择排序*n");for(i=0;i<50;i+)printf("-");prin

28、tf("n"); select_sort(data,-size); for(i=0;i<50;i+)printf("-");printf("n"); break;case 5:size=size-1;printf("*堆排序*n");for(i=0;i<50;i+)printf("-");for(i=size/2;i>0;i-) adjust(i,size);printf("n堆：");for(k=1;k<size;k+)printf("%d ",datak);for(i=size-2;i>0;i-)temp=datai+1; datai+1=data1; data1=temp;/*将树根和最后的节点交换*/ adjust(1,i);/*再重新调整为堆树*/ n+; printf("n第%d趟排序：",n); for(k=1;k<size;k+) printf("%d "