资源描述：
《数据结构课程设计94676》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、数据结构课程设计报告课程设计题目：各种内部排序性能比较学生姓名:专业:班级:学号:指导教师:目录试验分析需求分析说明3总体设计3详细设计4试验内容4代码6程序测试22总结24一.需求分析说明：排序是数据处理中经常遇到的一种重要操作。然而排序的算法有很多，各有其优缺点和使用场合。本程序的设计的主要目的是通过比较各种内部排序（包括：选择法、冒泡法、直接插入法、快速法、两路合并法）的时间复杂度，即元素比较次数和移动次数，來分析各种算法优缺点和适合排列何种序列。达到在实际应用中选择合适的方法消耗最短的时间完成排序。二.总体设计:本程序主要包括六个功能：1、选择法排
2、序2、冒泡法排序3、一直接插入法排序4、快速法排序5、二分法排序6、希尔排序7、堆排序8、统计各种排序的时间复杂度因此在类Sort定义小主要包括这七个函数。以及需要用到的变量。主函数中包括产生待排序序列、提示用户选择排序方法或比较各种排序的时间复杂度。并使用while循环使用户可以连续选择想要程序做的操作，宜到选择退岀程序为止。Main()选择法排序select冒泡法排序bubble插入法排序straight快速法排序quickQsort()SUBJ1ENUE():输岀各菜单一＞产生随机数序列-＞提示用户选择菜单-若选择则重新输入数据进行排序，并再次选择排
3、序方法。-＞若选择2,则调用BISJNT()函数进行二分法排序，并输出各趟排序结果若选择3,贝IJ调用STINSORT()函数进行直接排序，并输出各趟排序结果-若选择4,则调用SHELL()函数进行希尔排序，并输出各趟排序结果-＞若选择5,则调用QUICK()函数进行快速法排序，并输出各趟排序结果-若选择6,则调用SELECT()函数进行选择排序，并输出各趟排序结果-＞若选择7,则调用BUBBLE()函数进行冒泡法排序，并输岀各趟排序结果若选择8,则调用HEAPSORT()函数进行堆排序，并输出各趟排序结果-若选择9,则调用系统函数exit()退出循坏，退
4、出程序。三、详细设计：一、函数voidSELECT()用选择法对序列排序并输出各趟排序结果；voidBUBBLE()用冒泡法对序列排序并输岀各趟排序结果；voidSTINSORT()用宜接插入法对序列排序并输出各趟排序结果；voidQUICK()用快速法对序列排序并输出各趟排序结果;voidHEAPSORT()用堆排序对序列排序并输出各趟排序结果；voidSHELL()用希尔法对序列排序并输出各趟排序结果；voidBIS」NT()用折半法对序列排序并输出齐趟排序结果。定义变量intCompar,intExch用于记录排序的元素比较、移动次数；选择排序：将初
5、始序列(A[0]—A[n・1])作为待排序序列，第一趟在待排序序列中找出最小值元素，与该序列中第一个元素交换，下一趟排序在序列3口]—厲》1])中进行,依次循坏，完成排序。该算法执行时间与元素的初始排列无关。不论初始序列如何，该算法都必须执行趟，每趟执行次元素Z间的比较。总的比较次数为n(n-1)/2；因此，此种排序的最好、最坏和平均情况的时间复杂度都为0(nA2)；需要移动元索次数为3(n-1)；该排序算法经过一趟排序后，就能确定一个元素的最终位置，是不稳定的排序方法。冒泡法排序:此种排序是通过交换两个元素实现的。第一趟在序列(A[0]—A[n/])中从
6、前往后进行两个相邻元索的比较，若后者小，则交换，比较次；第一趟排序结束后，最大元素被置于最后(即沉底)，下一趟排序只需在序列(A[0]—A[n・2])中进行；如果在某一趟排序屮没有交换元索，说明子序列已经有序，无需再往下进行。具体代码中通过定义变量last来确定排序的趟数。一进入while循环，last的值就被置为0,并且只有在for循坏中有元素的交换时才被修改为新值，如果某趟排序没有交换元素，则last保持为0,再rtli二last决定循环结束，排序完成。因此，冒泡排序最多执行rM趟，第i趟比较次，总共移动元素次数3n(n-1)/2,由此可看出，冒泡排序
7、比较偏爱基本有序的序列。直接插入法排序：将序列中第一个元素作为一个有序序列，将剩下的个元素插入该有序序列中，插入后保持该序列有序。在将一个元素插入到有序表中吋，首先将其存入临时变量temp中，然后从后往前查找插入位置，当temp小于表中元素时，就将该元素后移，继续比较移动，直到temp大于等于表中元索或者到了有序表中第一个元索时结束，这时就可将temp存入刚后移的兀素的位置了。次和
8、排序法必须执行廿趟，最好情况下,每趟排序只比较一次，移动两次。最坏情况下，最多比较i次，移动i+2次。快速排序：此排序算法是一个递归算法。定义函数Qsort(),实现具体排序过
9、程。每趟排序的结果是将当前序列分割为两个子序列：左边的元索全部小于
