数据结构课程设计报告---各种内排序性能比较

《数据结构课程设计报告---各种内排序性能比较》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构课程设计报告题目：各种内排序性能比较学生姓名：学号：班级：指导教师：2011-6-1319目录1、需求分析说明............................21.1所需完成的任务及要求1.2程序实现的功能2、总体设计................................32.1总体设计说明2.2总体流程图2.3各主程序详细流程图3、详细设计................................73.1使用的算法思想3.2各个算法的效率简析4、实现部分................................84.1

2、程序算法的代码5、程序测试...............................155.1程序运行的主界面5.2各算法运行界面6、总结...................................18191、需求分析说明排序是数据处理中经常遇到的一种重要操作。然而排序的算法有很多，各有其优缺点和使用场合。本程序的设计的主要目的是通过比较各种内部排序（包括：插入法排序、起泡法、选择法、快速法、合并法排序）的时间复杂度，即元素比较次数和移动次数，来分析各种算法优缺点和适合排列何种序列。达到在实际应用中选择合适的方法消耗最短的时间完成排序。1.1所

3、需完成的任务及要求任务：1)用程序实现插入法排序、起泡法、选择法、快速法、合并法排序；2)输入的数据形式为任何一个正整数，大小不限。要求：排序后的数组是从小到大的；1.2程序实现的功能（1）使用随机函数实现数组初始化，生成多组元素个数不同的数组；（2）用列表打印出每种排序下的各趟排序结果；（3）打印使用各种排序算法以后元素比较和交换的次数；（4）设计合理的打印列表来打印。191、总体设计（从总体上说明该题目的框架，用文字和图表说明）2.1总体设计说明采用插入气泡，选择，快速，合并的方法实现各种排序算法，并且在实现过程中插入适当变量来实现计数元素交换次数和比较

4、次数的统计。对于每一趟比较之后元素顺序以及最后的结果使用单独的函数来实现，形成单独的一个模块；2.2总体流程图2.3各主程序详细流程图①主函数流程图：Suiji();menu();开始输入selectSelectexit(0);0insertsort(R,k);bubblesort(R1,k);selectsort(R2,k);quicksort(R3,0,k-1,k);mergesort(R4,k);12345结束19②插入法函数流程图开始inta=0,b=0,k=0;inti=1;i=i假真temp

5、=r[j];j--;r[j+1]=temp;b++;i++结束19③起泡法函数流程图开始intflag=1,a=0,b=0,k=0inti=1;i=i真r[j]

6、m!=i假真b++;t=r[i];r[i]=r[m];r[m]=t;k++;showout(r,n);i++结束191、详细设计3.1使用的算法思想（1）对主界面的menu菜单，在主函数里面用switch语句调用各个模块的功能调用；（2）在插入法时，其算法思想是：将第一个元素作为单独的一个数组独立出来，对剩下的元素，逐个与前面的数组从后往前进行比较，一旦发现当前的元素大于或是等于前面已经排序好的元素中某个元素，则在这个元素之后插入即可；（3）在起泡法时，其算法思想是：将待排序的数组从后往前，依次比较相邻的两个元素，如果发现逆序则交换序列，使得数值、比较小的元

7、素逐渐往前排列，在这个算法时要用flag作为标记位，用来判断元素是否交换，用以减少不必要的交换次数；（4）对于选择法，其排序思想是:从第一个元素开始，并且标记当前元素的位置，比较后面所有的元素，找到其中最小的元素，也标记当前元素的位置，然后把两个标记位的元素进行交换，前面的标记位不断地向后移动，直到最后一个元素的位置，则排序完成；（5）对于快速法，其算法思想是：一般取数组中的第一个元素为基准，通过一趟排序将待排序元素分为左右两个子序列，左子序列的所有元素都小于或等于右子序列的所有元素，然后将左右两个序列按照与此相同的原理进行排序，直至整个序列有序为止，排序完

8、成。（6）对于合并法，其排序思想是：将两个有序子区间