“数据结构”课程设计报告（内部排序算法性能分析）学生姓名：指导教师：所在系：所学专业：年级：目录1、需求分析..................................................... - 1 -1.1、选题要求 (1)1.2、选题的意义及背景 (1)1.3、课程设计目标 (1)2、概要设计..................................................... - 2 -2.1、原始数据 (2)2.2、输出数据 (2)2.3、数据处理 (2)2.4、逻辑结构及物理结构 (3)2.5、系统的模块划分及模块功能 (3)2.5.1主程序模块....................................................................................................... - 3 -2.5.2可排序表单元模块........................................................................................... - 3 -2.6、模块的测试数据 (4)3、详细分析..................................................... - 5 -4、调试分析..................................................... - 6 -5、用户手册..................................................... - 9 -6、测试结果.................................................... - 10 -6.1测试用例及选择原因 (10)6.2测试结果 (10)7、总结........................................................ - 12 -8、参考文献.................................................... - 13 -9、小组人员分工................................................ - 13 -致谢......................................................... - 13 -1、需求分析1.1、选题要求对各种排序算法进行定量的性能分析。
1.2、选题的意义及背景排序是计算机程序设计中的一种重要操作。
它的功能是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。
内部排序的方法很多，但是就其全面性能而言，很难提出一种被认为是最好的方法，每一种方法都有各自的优缺点，适合在不同的环境下使用。
如果按排序过程中依据的不同原则对内部排序方法进行分类，则大致可分为插入排序，交换排序，选择排序，归并排序和记数排序等五类。
此实验通过对起泡排序、直插排序、选择排序、快速排序、归并排序这几种内部排序算法进行比较，能使我们更好的掌握这些排序的基本思想及排序算法。
通过该题目的设计过程，可以加深理解各种数据结构的逻辑结构、存储结构及相应上运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养我们的动手能力。
1.3、课程设计目标本课程设计对以下内部排序算法进行比较：起泡排序、直插排序、选择排序、快速排序、归并排序。
待排序表的元素关键字为整数，用不同的测试数据做测试比较。
比较的指标为关键字的比较次数和关键字的移动次数。
最后用图、表格数据汇总数据，以便对这些内部排序算法进行性能分析。
2、概要设计2.1、原始数据用户输入记录的个数，数据由随机数产生器生成。
2.2、输出数据产生的随机数分别用起泡排序、直插排序、选择排序、快速排序、归并排序这些排序方法进行排序，输出关键字的比较次数和移动次数。
2.3、数据处理主程序产生1组随机数起泡排序直插排序快速排序归并排序选择排序记录关键字的比较次数和移动次数将随机数保存在数组中循环50次输出关键字的比较次数、移动次数的平均值2.4、逻辑结构及物理结构以顺序表为存储结构（物理结构）typedef struct{int key; //关键字}ElemType;typedef struct{ElemType *elem;int length;//数据元素个数}SqList;2.5、系统的模块划分及模块功能MainSelect Sort Bubble Sort Insert Sort Quick Sort Merge SortOutput quick系统分为两个模块2.5.1主程序模块void main（）2.5.2可排序表单元模块A．选择排序void SelectSort(SqList &L)B.起泡排序void BubbleSort(SqList &L)C.直接插入排序void InsertSort(SqList &L)void BeforeSort()void display(int m,int n)D．快速排序int Partition(SqList &L,int low,int high)void QSort(SqList &L,int low,int high)void QuickSort(SqList &L)E．归并排序void MergeSort(SqList &L)2.6、模块的测试数据以关键字的数目分别为10，100，1000为例,作为测试数据。
3、详细分析（1）选择排序基本思想：在待排序的一组数据元素中，选出最小的一个数据元素与第一个位置的数据元素交换；然后在剩下的数据元素当中再找最小的与第二个位置的数据元素交换，循环到只剩下最后一个数据元素为止。
（2）起泡排序基本思想：相邻的两个元素进行比较，将小的调到前面，大的调到后面。
（3）直接插入排序待排序的记录放在数组R[0…n-1]中排序过程中某一时刻，R被划分成两个子区间R[0…i-1] (有序和)R[i…n-1](无序)。
直接插入的基本操作是将当前无序区的一个记录R[i]插入到有序区R[0…i-1]中适当的位置（4）快速排序基本思想：在待排序的数组的n个元素中取一个元素(一般取第一个)，将其移动到这样的位置：在其之前的元素的值都小于它，在其之后的元素都大于它，这样是一趟快速排序；然后对数组的两个部分进行同样的操作，直到每部分只有一个记录为止；总之，每趟使表的第一个元素放在适当位置，将表两分，再对两子表进行同样的递归划分，直至划分的子表长度为1！（5）归并排序基本思想：将两个或两个以上的有序表组成一个新的有序表。
4、调试分析（1）刚开始进行调试时，有些排序方法不能实现，我就对不能实现的排序进行分析，对产生的语法错误进行了及时的改正，以至所有的排序算法能够顺利的实现。
（2）考虑不周全，每种排序算法所使用的随机数并不相同，这样便使得得到的关键字的比较次数和移动次数不具有可比性。
改后的程序便解决了这个问题。
（3）从上面的显示可以看出，直插排序的移动次数为1（只有数据是正序的时候，才是为1），经检查程序存在问题。
随机数在经过选择排序后，已经变为正序的数据，后面的排序方法是对以上正序数的排序。
为此专门设置一个数组，存取随机数。
但是改后的程序出现了下面的状况。
编译正确，执行不了。
（4）上网查询执行不了的原因，网上是这样讲的：Windows子系统设置错误, 提示: )WA5FzPLwlibcmtd.lib(crt0.obj) : error LNK2001: unresolved external symbol _main *+oJ(e+4f{'{1]\Windows项目要使用Windows子系统, 而不是Console, 可以这样设置:*^'y#/D+gz !DF-%3|[Project] --> [Settings] --> 选择"Link"属性页, Qo!在Project Options中将/subsystem:console改成/subsystem:windowsT`H.k"Y{Xn?{t*{但是自己的机子的设置却改不了。
网上有人建议用CodeBlocks这个程序进行执行，安装这个程序，编译执行后，得到下面的结果。
有效的解决了上面的问题。
（5）在老师的指导下，找到了无法执行的原因。
主函数定义错误。
将void addlist(SqList &L)改为Void main(){ SqList L;问题解决。
5、用户手册（1）本程序的运行环境为DOS操作系统（2）进入演示程序后，即显示文本方式的用户界面。
（3）演示程序以人机对话的形式进行。
只要输入记录的个数，程序便产生50组随机数，显示通过选择排序、起泡排序、直插排序、快速排序、归并排序对随机数进行排序时，关键字的比较次数和移动次数的平均值，从而直观的比较各种内部排序算法的优劣。
6、测试结果6.1测试用例及选择原因记录数分别输入10、100、1000，之所以想用这三个记录数测试，是想测试用选择排序、起泡排序、直插排序、快速排序、归并排序这五种排序方法，在记录较小和较大时，关键字的比较次数和移动次数，用以直观的分析它们的性能。
6.2测试结果测试的结果如下表：（注：此数据为50组数据的平均值）记录数关键字选择排序起泡排序直插排序快速排序归并排序的个数10比较次数36 81 9 40 36 移动次数18 68 12 18 23 100 比较次数4851 9801 99 624 688 移动次数281 7394 1564 327 409 1000比较次数498501 998001 999 8487 9984 移动次数2974 749592 175354 4768 5433 6.3结论关键字选择排序起泡排序直插排序快速排序归并排序记录数比较次数较少最多最少较少较少较小移动次数较少最多较少较少较少比较次数较少最多最少较少较少较大移动次数最少最多较多较少较少由上表可以得出：（1）选择排序的比较次数较少且为定值，但由于它在排序过程中要先查询、再安置，所以性能上不够稳定。
（2）起泡排序的比较次数和移动次数在这五种排序方式中最多，所以起泡排序的排序性能相对于其他排序要低好多。
（3）直插排序的比较次数和移动次数相比较于其他几种排序次数要少，所以效率相比较而言较高，性能较高，且较稳定。