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

xx大学本科生课程设计论文题目：排序算法集成学生姓名：学号：专业：计算机班级：指导教师：2013年5月20日xx大学课程设计任务书课程名称数据结构课程设计设计题目排序算法集成指导教师时间2013.5.20-2013.5.30一、教学要求1.掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风二、设计资料及参数每个学生在教师提供的课程设计题目中任意选择一题，独立完成，题目选定后不可更换。排序算法集成定义动态数组类（或类模板）以表示待排序数据，在此基础上实现多种排序算法。要求设计函数模板来实现下列排序算法：直接插入排序冒泡排序简单选择排序希尔排序快速排序堆排序并设计主函数测试动态数组类（或类模板），测试各排序算法的函数模板。三、设计要求及成果1.分析课程设计题目的要求2.写出详细设计说明3.编写程序代码，调试程序使其能正确运行4.设计完成的软件要便于操作和使用5.设计完成后提交课程设计报告四、进度安排资料查阅与讨论（1天）系统分析（2天）系统的开发与测试（5天）编写课程设计说明书和验收（2天）五、评分标准1.根据平时上机考勤、表现和进度，教师将每天点名和检查2.根据课程设计完成情况，必须有可运行的软件。3.根据课程设计报告的质量，如有雷同，则所有雷同的所有人均判为不及格。4.根据答辩的情况，应能够以清晰的思路和准确、简练的语言叙述自己的设计和回答教师的提问六、建议参考资料1．《数据结构（C语言版）》严蔚敏、吴伟民主编清华大学出版社2004.112．《数据结构课程设计案例精编（用C/C++描述）》，李建学等编著，清华大学出版社2007.23.《数据结构:用面向对象方法与C++语言描述》，殷人昆主编，清华大学出版社2007.6目录目录...........................................................................................................................................3引言..................................................................................................................................................4一．算法的设计思想.......................................................................................................................4二．算法的流程图...........................................................................................................................4三．算法的设计与分析...................................................................................................................53.1建立数组.......................................................................................................................53.2算法思想........................................................................................错误!未定义书签。3.3主要函数.......................................................................................................................63.4主要函数声明...............................................................................错误!未定义书签。3.5主要变量说明..............................................................................................................10四．程序源代码.............................................................................................................................11五．运行结果与分析（测试）.....................................................................................................18六．总结（收获与体会）.............................................................................................................20七．参考文献.................................................................................................................................21引言本课程设计主要解决几种不同排序方法以及在各种不同排序的过程中某一趟的具体排序结果。通过观察各种排序的具体排序过程，加深对不同排序方法的认识，加深对不同排序算法的掌握。一．算法设计的思想数据结构是与数据相关的一门重要学科，不论是想通过升学考试还是想把程序编得有水平，都要对这门学科下一点功夫才行。而课程设计是让我们更好的掌握这门学科的重要方式。排序是计算机程序中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列重新排列成一个按关键字有序的序列。而内部排序中包括各种不同的排序，本课程设计主要讨论的是插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序。完成这几种排序最主要的就是弄好不同排序的算法，只有深刻的认识了这不同排序的算法，才能了解不同排序的优点与缺点。通过对不同排序算法的分析，了解它们的优劣特点。据对题目的分析，首先要根据插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序的不同算法，写出实现各个排序算法的函数。然后通过在主函数中对不同排序的子函数的调用来实现对某个序列的具体排序。内部排序的方法很多，但就其全面性而言，很难提出一种被认为是最好的方法，每一种方法都有各自的优缺点，适合不同的环境。通常，在排序的过程中需进行两种基本操作：（1）比较两个关键字的大小；（2）将记录从一个位置移动至另一位置。前一个操作对大多数排序方法来说都是必要的，而后一个操作可以通过改变记录的存储方式来予以避免。二．算法的流程图如图2.1图2.1主要设计思想流程图三．算法的设计与分析3.1建立数组在程序中建立一个数组data[]，用于存储程序运行中的数据。3.2算法思想（1）插入排序插入排序的主要算法思想是将一个记录插入到已排好的有序表中，从而得到一个新的、记录数增1的有序表。（2）希尔排序希尔排序的基本思想是先将整个待排记录列分割成若干子序列分别进建立数组设计main函数建立各排序函数结束开始行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。（3）冒泡排序函数冒泡排序首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序则将两个记录交换，然后比较第二个记录和第三个记录的关键字，依次类推。（4）选择排序函数选择排序的基本思想是：每一趟在n-i+1(i=1,2,…,n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。（5）堆排序先将一个序列进行建堆，然后将大顶堆的第一个元素和最后一个元素对换（或将小顶堆的最后一个元素和第一个元素对换），再对除最后一个元素的序列进行求大顶堆（或对除第一个元素的序列进行求小顶堆），依次类推。3.3主要函数（1）插入排序函数voidinsertion_sort(int[],int);/*插入排序*/（2）希尔排序函数voidshell_sort(int[],int);/*希尔排序*/（3）冒泡排序函数voidbubble_sort(int[],int);/*冒泡排序*/（4）选择排序函数voidselect_sort(int[],int);/*选择排序*/（5）将数据调整为堆的函数voidadjust(int,int);/*将数据调整为堆树*/3.4主要函数声明①插入排序插入排序的主要算法思想是将一个记录插入到已排好的有序表中，从而得到一个新的、记录数增1的有序表。voidinsertion_sort(intdata[],intsize)/*插入排序*/{intbase,compare,temp,i,j=0;for(base=1;basesize;base++)/*当数据小于第一个时，则插于前方，否则与后面数据对比找出插入位置*/{temp=data[base];compare=base;j++;while(compare0&&data[compare-1]temp){data[compare]=data[compare-1];compare--;}data[compare]=temp;printf(第%d趟排序:,j);for(i=0;isize;i++)printf(%d,data[i]);printf(\n);}printf(\n最终排序结果:);for(i=0;isize;i++)printf(%d,data[i]);printf(\n);}②希尔排序希尔排序的基本思想是先将整个待排记录列分割成若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。voidshell_sort(intdata[],intsize)/*希尔排序*/{inti,j,k,incr,temp,num=0;incr=size/2;printf(\n);while(incr0){for(i=incr+1;isize;i++){j=i-incr;while(j0)if(data[j]data[j+incr])/*比较每部分的数据大小顺序不对则交换*/{temp=data[j];data[j]=data[j+incr];data[j+incr]=temp;j=j-incr;}elsej=0;}num++;printf(\n第%d趟排序:,num);for(k=1;ksize;k++)printf(%d,data[k]);incr=incr/2;}printf(\n最终排序结果：);for(i=1;isize;i++)printf(%d,data[i]);printf(\n);}③冒泡排序冒泡排序首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序则将两个记录交换，然后比较第二个记录和第三个记录的关键字，依次类推。voidbubble_sort(intdata[],