3.1. 问题描述
3.1.1 题目内容 设计程序实现六种方法的内部排序：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。并对各个内部排序算法进行实测比较。
3.1.2 基本要求 程序分别对六种常用的内部排序算法进行实测比较：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。待排序表的表长不小于100，其中数据要用随机数产生程序产生，要求用多组不同的输入数据进行比较，比较的指标为：有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次的移动）。
3.1.3 待测试数据 因为所产生的数据是随机数，所以只需要用户输入要产生的随机数的个数。所以可根据需要设置以下一组数： 5， 10， 50， 300， 1000， 7000， 20000， 50000。
3.2. 需求分析
3.2.1 程序的基本功能 首先用户输入要测试的随机数的个数，然后可以进行各个选项对数据进行不同的测试，程序能分别输出用起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序所用的移动关键字的步数，以便比较各个排序算法的效率。
3.2.2 输入值的形式和范围
程序设定输入的整型数据在100000之内。
3.2.3 输出形式
程序将产生的随机数以数组的形式储存，并在屏幕上依次输出，排序后得到的有序数组也同样依次输出，同时输出跟踪的来的总移动步数。
3.2.4 测试数据要求
在调试时，为了能方便判断得出的结果是否正确可使用数量小的随机数，如3、4、5。在调试确定算法能得出正确结果后测试数据要求每组随机数的个数应大于100，最好更长，这样才能更加容易得出各个排序算法在时间上的不同。
3.3. 概要设计
3.3.1 主程序流程及模块调用关系 （1）主程序流程图：
一. 产生随机数。
开始 程序 二. 各个排序算法
开始 输入产生随机数的个数 N 输入选择c
产生N个随机数并放入 一个数组中 C=1 C=3 C=5 C=2 结束 起泡排序处理直接插入排序处理简单选择排序处理C=4 C=6 Shell排序处理 快速排序处理堆排序处理 结束
图 3-1 程序流程图
（2）模块调用关系图见下页：
随机数产生模块 起泡排序模块 主程序直接插入排序模块
3.3.2 核心的粗线条伪码算法 设置一个类 class Algorithm{
…….. 将各个排序算法的函数作为类中的构造函数
…….. }A;
简单选择排序模块 快速排序模块 Shell排序模块 堆排序模块 图 3-2
Algorithm Sorting ( )
1. 输入随机数的个数N；
2. 调用随机数产生函数产生个N随机数并储存到 Array[1]~~Array[N]中. 3. 输入选择功能 4． switch(c) { case '1': 调用起泡法对所产生的随机数进行排序; case '2': 调用直接插入法对所产生的随机数进行排序; case '3': 调用简单选择法对所产生的随机数进行排序;
case '4': 调用快速排序法对所产生的随机数进行排序; case '5': 调用Shell排序对所产生的随机数进行排序; case '6': 调用堆排序对所产生的随机数进行排序; case '7': 产生下一组随机数据 case '8': 结束并 退出程序
3.4. 详细设计
3.4.1 实现概要设计的数据类型.
定义一个类，将每个算法都现在该类中： Class Algorithm{ Public: Bubblesort(){……….}
StraightInsertsort(){……….} Selectsort(){……….} Quiksort(){……….} Shellsort(){……….} Heapesort(){……….} }A;
3.4.2 每个操作的伪码算法. （1）.起泡法排序伪码算法：
Algorithm BubbleSort( ){
while(k>1)
{//i>1表明上一趟曾进行过记录交换
设定一个记录最后一次交换位置的整型int lastExchangeIndex=1; for(int j=1;j 将一趟排序中无序序列中最后一个记录的位置传递给k,做下一次循环 （2）.直接插入排序的伪算法： Algorithm InsertSort() for(int i=2;i<=L.length;++i) 判断如果第i个元素的值小于第i-1元素的值时 { 需将第i个元素插入有序子表 将 i元素复制为哨兵 for(int j=i-1;L.elem[0].key （3）.Shell排序伪算法 Algorithm ShellSort(){ 设置一个整型变量福初始值为5（ dlta=5; ） { 做运算dlta = dlta/3+1; 调用ShellInsert函数 }当设置的整型变量大于1; ShellInsert( ) //ShellInsert函数{ for(int i=dk+1;i<=L.length;++i) if(L.elem[i].key }while(j > 0&&L.elem[0].key < L.elem[j].key); //记录后移，查找插入位置 插入操作L.elem[j+dk]=L.elem[0]; } （4）. 快速排序伪算法： Algorithm QuikSort(){ 判断需要排序的数组长度，如果大于1{ 调用Partition函数，将Low 到Hight一分为二 分别调用QSort函数，分别对高低子表进行递归排序 } } Partition(sqlist &R,int low,int high) //划分函数{ //对记录子序列R[low....high]进行一趟快速排序，并返回枢轴记录所在位置， //使得在它之前的记录的关键字均不大于它的关键字，在它之后的记录的关键 //字均不小于它的关键字 将枢轴记录移至数组的闲置地方； 枢轴记录关键字； 从表的两端交替地向中间扫描； 将比枢轴记录小的记录移到底端 将比枢轴记录大的记录移到高端 枢轴记录移到正确位置（R.elem[low] = R.elem[0]） 返回枢轴的位置 return low } void QSort(sqlist &R,int low,int high) 函数对记录序列R[s....t]进行快速排序 { 如果子表长度大于1 { 调用Partition对R[s...t]进行一次划分，并返回枢轴位置 对底端子序列递归排序(QSort(R,low,pivotloc-1) ). 对高断子序列递归排序(QSort(R,pivotloc+1,high) ). } 3.4.3 主程序和其它模块的伪码算法. Algorithm main ( ) 1. 函数运行，并先后调用菜单函数和随机数产生函数 2. 进入while循环，再次调用菜单函数 3．进入如下一个Switch语句，对各个功能进行调用 switch(c) { case '1': 调用起泡法对所产生的随机数进行排序; case '2': 调用直接插入法对所产生的随机数进行排序; ………. case '6': 调用堆排序对所产生的随机数进行排序; case '7': 产生下一组随机数据 case '8': 结束并 退出程序 3.5. 调试分析 3.5.1 设计与调试过程中遇到的问题及分析、体会 在程序的最初调试中因为没有把握好各个函数之间的调用关系，因而出现了许多错误，比如得不到排序结果等，然后将所有排序的函数都写在了一个类中，这样，只要声明一次，以后就可以非常方便，准确的调用各个函数了。从中学会了类，对象在程序中的优越性，能更加灵活的掌握它的使用了。同样在每个具体的功能函数编写中也遇到了许多问题，比如快速选择排序的算法，在我没有非常理解它的算法思想时，往往写出的程序不能得出结果或得出错误的结果，但是在反复的对课本和其它书籍对问题阐述中理解，最终问题得到了很好的解决。 3.5.2 主要和典型算法的时间复杂度的分析 经过分析起泡法排序的时间复杂度为 O( n^2 )； 快速排序的时间复杂度为 O( n㏒2 n )； 直接插入排序的时间复杂度为 O( n^2 )； 简单选择排序的时间复杂度为 O( n^2 )； Shell排序的时间复杂度为 O( n^1.25 )； 堆排序的时间复杂度为 O(n㏒2 n )； 3.6. 使用说明 运行程序屏幕出现如图 3-3所示界面因为在使用各个排序功能前，必须存在一 组随机数据，所以系统首先提示输入要产生随机猪的个数，并注明，输入的数据不能大于100000。输入随机数的个数后，程序将自动产生N个随机数并在屏幕上显示出来，当用户按下任意键后，将进入如图3-6所示界面。 图 3-3 图 3-4 进入图3-6所示界面后，用户可以有8种选择，分别为1.用起泡法排序； 2.用直接插入发排序；3.用简单选择排序； 4.快速排序； 5. Shell排序； 6.堆排序； 7. 产生下一组随机数； 8. 退出程序。 图3-5 图3-6 当用户输入一个排序选项后，程序将产生的随机数进行排序，并输出关键字移动的步数，如图3-4。当用户想要测试下一组随机数时，可选择‘7’，这时程序提示用户输入新的随机数的个数如图3-5所示。选择功能‘8’则可安全退出程序。 3.7. 测试结果 通过以下对7组随机数的测定，我们可以比较大概得出各种排序算法的效率： 表 3.1 随机数 个数 200 500 1000 5000 10000 30000 50000 元素移动次数 起泡法 10111 62050 256068 6249389 24953767 226025897 626886792 直接插入法 193 494 993 4995 9993 29988 49991 简单选择法 197 490 992 4992 9990 29993 49983 快速排序法 7299 44121 251389 1984598 14882808 57451235 124510410 Shell排序法 282 737 1461 7420 14956 44772 74783 堆排序法 1471 4303 9575 59662 129267 434782 762254 因篇幅问题不能全部显示，请点此查看更多更全内容