数据结构课程设计(内部排序算法性能分析)

《数据结构课程设计(内部排序算法性能分析)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、“数据结构”课程设计报告（内部排序算法性能分析）学生姓名：指导教师：所在系：所学专业：年级：-13-目录1、需求分析11.1、选题要求11.2、选题的意义及背景11.3、课程设计目标12、概要设计22.1、原始数据22.2、输出数据22.3、数据处理22.4、逻辑结构及物理结构32.5、系统的模块划分及模块功能32.5.1主程序模块32.5.2可排序表单元模块32.6、模块的测试数据43、详细分析54、调试分析65、用户手册96、测试结果106.1测试用例及选择原因106.2测试结果107、总结128、参考文献139、小组人员分工1

2、3致谢13-13-1、需求分析1.1、选题要求对各种排序算法进行定量的性能分析。1.2、选题的意义及背景排序是计算机程序设计中的一种重要操作。它的功能是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。内部排序的方法很多，但是就其全面性能而言，很难提出一种被认为是最好的方法，每一种方法都有各自的优缺点，适合在不同的环境下使用。如果按排序过程中依据的不同原则对内部排序方法进行分类，则大致可分为插入排序，交换排序，选择排序，归并排序和记数排序等五类。此实验通过对起泡排序、直插排序、选择排序、快速排序、归并排序这几种内部排序算法

3、进行比较，能使我们更好的掌握这些排序的基本思想及排序算法。通过该题目的设计过程，可以加深理解各种数据结构的逻辑结构、存储结构及相应上运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养我们的动手能力。1.3、课程设计目标本课程设计对以下内部排序算法进行比较：起泡排序、直插排序、选择排序、快速排序、归并排序。待排序表的元素关键字为整数，用不同的测试数据做测试比较。比较的指标为关键字的比较次数和关键字的移动次数。最后用图、表格数据汇总数据，以便对这些内部排序算法进行性能分析。-13-2、概

4、要设计2.1、原始数据用户输入记录的个数，数据由随机数产生器生成。2.2、输出数据产生的随机数分别用起泡排序、直插排序、选择排序、快速排序、归并排序这些排序方法进行排序，输出关键字的比较次数和移动次数。2.3、数据处理主程序产生1组随机数起泡排序直插排序快速排序归并排序选择排序记录关键字的比较次数和移动次数将随机数保存在数组中循环50次输出关键字的比较次数、移动次数的平均值-13-2.4、逻辑结构及物理结构以顺序表为存储结构（物理结构）typedefstruct{intkey;//关键字}ElemType;typedefstruct

5、{ElemType*elem;intlength;//数据元素个数}SqList;2.5、系统的模块划分及模块功能MainSelectSortBubbleSortInsertSortQuickSortMergeSortOutputquick系统分为两个模块2.5.1主程序模块voidmain（）2.5.2可排序表单元模块A．选择排序voidSelectSort(SqList&L)B.起泡排序voidBubbleSort(SqList&L)C.直接插入排序-13-voidInsertSort(SqList&L)voidBeforeSo

6、rt()voiddisplay(intm,intn)D．快速排序intPartition(SqList&L,intlow,inthigh)voidQSort(SqList&L,intlow,inthigh)voidQuickSort(SqList&L)E．归并排序voidMergeSort(SqList&L)2.6、模块的测试数据以关键字的数目分别为10，100，1000为例,作为测试数据。-13-3、详细分析（1）选择排序基本思想：在待排序的一组数据元素中，选出最小的一个数据元素与第一个位置的数据元素交换；然后在剩下的数据元素当中

7、再找最小的与第二个位置的数据元素交换，循环到只剩下最后一个数据元素为止。（2）起泡排序基本思想：相邻的两个元素进行比较，将小的调到前面，大的调到后面。（3）直接插入排序待排序的记录放在数组R[0…n-1]中排序过程中某一时刻，R被划分成两个子区间R[0…i-1](有序和)R[i…n-1](无序)。直接插入的基本操作是将当前无序区的一个记录R[i]插入到有序区R[0…i-1]中适当的位置（4）快速排序基本思想：在待排序的数组的n个元素中取一个元素(一般取第一个)，将其移动到这样的位置：在其之前的元素的值都小于它，在其之后的元素都大于它

8、，这样是一趟快速排序；然后对数组的两个部分进行同样的操作，直到每部分只有一个记录为止；总之，每趟使表的第一个元素放在适当位置，将表两分，再对两子表进行同样的递归划分，直至划分的子表长度为1！（5）归并排序基本思想：将两个或两个以上的有