内部排序算法的性能分析

《内部排序算法的性能分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构课程设计报告设计题目：内部排序算法的性能分析专业通信工程班级0803学生潘志威学号2008115020312指导教师孙玉霞起止时间2011-2-21~2011-2-27湖北师范学院2011年第一学期16目录1需求分析21.1、选题要求21.2、选题的意义及背景21.3、课程设计目标32概要设计32.1原始数据32.2输出数据32.3数据处理43算法描述53.1逻辑结构及存储结构53.2系统的模块划分及模块功能53.2.1主程序模块53.2.2可排序表单元模块63.3程序代码64调试分析15测试结果25.1测试用例及选择原因25.2测

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

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

4、法进行性能分析。2概要设计2.1原始数据用户输入记录的个数，数据由随机数产生器生成。2.2输出数据产生的随机数分别用起泡排序、直插排序、选择排序、快速排序、归并排序这些排序方法进行排序，输出关键字的比较次数和移动次数。162.3数据处理主程序产生1组随机数起泡排序直插排序快速排序堆排序选择排序记录关键字的比较次数和移动次数将随机数保存在数组中循环50次输出关键字的比较次数、移动次数的平均值163算法描述3.1逻辑结构及存储结构以顺序表为存储结构typedefstruct{KeyTypekey;}DataType;3.2系统的模块划分及模块功

5、能mainSelectSortBubbleSortInsertSortQuickSortHeapSortOutput系统分为两个模块3.2.1主程序模块voidmain()163.2.2可排序表单元模块冒泡排序：voidBubbleSort(DataTypea[],intn)插入排序：voidInsertSort(DataTypea[],intn)直接选择排序：voidSelectSort(DataTypea[],intn)快速排序：voidQuickSort(DataTypea[],intlow,inthigh)希尔排序：voidShel

6、lSort(DataTypea[],intn,intd[],intnumOfD)堆排序：voidCreatHeap(DataTypea[],intn,inth)3.3程序代码16头文件：typedefintKeyType;typedefstruct{KeyTypekey;}DataType;staticlongintcount1=0,count2=0;/*冒泡排序*/voidBubbleSort(DataTypea[],intn){inti,j,flag=1;DataTypetemp;for(i=1;i

7、ag=0;for(j=0;ja[j+1].key){count2++;flag=1;temp=a[j];count1++;16a[j]=a[j+1];count1++;a[j+1]=temp;count1++;}}}}/*插入排序*/voidInsertSort(DataTypea[],intn){inti,j;DataTypetemp;for(i=0;i-1&&temp.key

8、=a[j];count1++;j--;}a[j+1]=temp;count1++;}}/*选择排序*/voidSelectSort(DataTypea[],intn){inti,