各种内部排序性能比较数据结构课程设计.docVIP

PAGE 2 数据结构 课程设计报告 课程设计题目：各种内部排序性能比较 学生姓名： 专 业： 班 级： 学 号： 指导教师： 年 月 日 目录 试验分析 需求分析说明 3 总体设计 3 详细设计 4 试验内容 4 代码 6 程序测试 22 总结 24 需求分析说明： 排序是数据处理中经常遇到的一种重要操作。然而排序的算法有很多，各有其优缺点和使用场合。本程序的设计的主要目的是通过比较各种内部排序（包括：选择法、冒泡法、直接插入法、快速法、两路合并法）的时间复杂度，即元素比较次数和移动次数，来分析各种算法优缺点和适合排列何种序列。达到在实际应用中选择合适的方法消耗最短的时间完成排序。 总体设计： 本程序主要包括六个功能： 1、选择法排序 2、冒泡法排序 3、直接插入法排序 4、快速法排序 5、二分法排序 6、希尔排序 7、堆排序 8、统计各种排序的时间复杂度 因此在类Sort定义中主要包括这七个函数。以及需要用到的变量。 主函数中包括产生待排序序列、提示用户选择排序方法或比较各种排序的时 间复杂度。并使用while循环使用户可以连续选择想要程序做的操作，直到选择退出程序为止。 选择法排序select → 选择法排序select 冒泡法排序bubble → 冒泡法排序bubble Main（）插入法排序straight → Main（） 插入法排序straight Qsort（）快速法排序quick → → Qsort（） 快速法排序quick Merge（）二分法排序 binary → → Merge（） 二分法排序 binary 希尔排序 Shell → 希尔排序 Shell 堆排序 堆排序 Heap SUB_MENUE(): 输出各菜单→产生随机数序列→提示用户选择菜单 →若选择1，则重新输入数据进行排序，并再次选择排序方法。 →若选择2，则调用BIS_INT（）函数进行二分法排序，并输出各趟排序结果 →若选择3，则调用STINSORT（）函数进行直接排序，并输出各趟排序结果 →若选择4，则调用SHELL（）函数进行希尔排序，并输出各趟排序结果 →若选择5，则调用QUICK（）函数进行快速法排序，并输出各趟排序结果 →若选择6，则调用SELECT（）函数进行选择排序，并输出各趟排序结果 →若选择7，则调用BUBBLE（）函数进行冒泡法排序，并输出各趟排序结果 →若选择8，则调用HEAPSORT（）函数进行堆排序，并输出各趟排序结果 →若选择9，则调用系统函数exit（）退出循环，退出程序。 详细设计： 一、函数 void SELECT () 用选择法对序列排序并输出各趟排序结果； void BUBBLE ()用冒泡法对序列排序并输出各趟排序结果； void STINSORT ()用直接插入法对序列排序并输出各趟排序结果；void QUICK ()用快速法对序列排序并输出各趟排序结果；void HEAPSORT()用堆排序对序列排序并输出各趟排序结果；void SHELL()用希尔法对序列排序并输出各趟排序结果；void BIS_INT()用折半法对序列排序并输出各趟排序结果。 定义变量int Compar，intExch用于记录排序的元素比较、移动次数； 选择排序： 将初始序列（A[0]—A[n-1]）作为待排序序列，第一趟在待排序序列中找出最小值元素，与该序列中第一个元素交换，下一趟排序在序列（A[1]—A[n-1]）中进行，依次循环，完成排序。 该算法执