内部排序算法实现与性能分析课程设计.

第1页共14页目录1、问题描述：.......................................................21.1题目内容:....................................................21.2基本要求:....................................................21.3测试数据:....................................................22、需求分析：.......................................................22.1程序的基本功能:..............................................22.2输入值、输出值以及输入输出形式:..............................22.3各个模块的功能要求：.........................................23、概要设计：.......................................................33.1所需的ADT，每个程序中使用的存储结构设计说明.................33.2主程序流程以及模块调用关系...................................33.3每个模块的算法设计说明（流程图）.............................43.3.1气泡排序：.............................................43.3.2直插排序...............................................53.3.3选择排序...............................................63.3.4希尔排序...............................................73.3.5快速排序...............................................84、详细设计：.......................................................94.1函数调用关系图...............................................95、各个算法实现的源程序：...........................................95.1、冒泡排序及其主要算法.......................................95.2、直接插入排序及其主要算法..................................105.3、选择排序及其主要算法......................................105.4、希尔排序及其主要算法......................................116、调试分析：......................................................127、使用说明：......................................................138、测试结果：......................................................149、主要参考文献....................................................14第2页共14页1、问题描述：1.1题目内容:内部排序算法实现与性能分析1.2基本要求:（1）数据结构定义（2）利用随机函数产生30000个随机整数，利用插入排序、起泡排序、选择排序、快速排序、希尔等排序方法进行排序，并统计每一种排序上机所花费的时间,对各种排序算法做分析比较.1.3测试数据:由函数随机产生的数据，由于是随机产生的，所以在此不一一写出。2、需求分析：2.1程序的基本功能:输入30000个随机整数，对这些数进行多种方法进行排序，并对这些排序做比较，在屏幕上输出每种排序方法所比较的次数，交换的次数，和时间复杂度。2.2输入值、输出值以及输入输出形式:由于程序中所需的数据都是有函数随机生成的整形数，不需要用户自己输入，用户只需要对演示程序中的一些提示做一些必要的选择以便于程序的执行。程序输出的是对六种排序做的一些比较，即输出六种排序各排序过程中所比较的数据的个数，交换的数据的次数，和排序完成所用的时间。六种排序依次在计算机终端上显示，便于用户观察。2.3各个模块的功能要求：一、随机函数：产生随机数二、选择排序函数：对随机数进行选择排序三、起泡排序函数：对随机数进行气泡排序四、直接插入函数：对随机数进行直接插入排序五、希尔排序函数：对随机数进行希尔排序六、快速排序函数：对随机数进行快速排序七、主函数第3页共14页3、概要设计：3.1所需的ADT，每个程序中使用的存储结构设计说明typedefstruct{intkey;}ElemType;//元素类型typedefstruct{ElemType*elem;intlength;}SqList;//顺序表类型3.2主程序流程以及模块调用关系主函数main（）初始化变量x,i;;初始化线性表SqListL;Showthemenu显示主界面五种排序运行后打印结果五种排序用时的比较，不打印排序后的结果第4页共14页3.3每个模块的算法设计说明（流程图）3.3.1气泡排序：开始初始变量i=1，j=1i小于L.lengthj小于L.lengthL.elem[j].key大于L.elem[j+1].key交换第j个和第j+1个元素j++YYY结束N第5页共14页3.3.2直插排序开始初始变量i=2,ji=L.lengthY如果第i位比第i-1位的值小L.elem[0].key=L.elem[i].keyYj=i-1NN如果第0位比第j位的值小记录后移j=j-1L.elem[j+1].key=L.elem[0].keyY结束第6页共14页3.3.3选择排序开始初始变量i=1,j,kIlengthJ=i+1Y如果i位置上的值=k位置上的交换数值位置Yj=j+1i=i+1结束NN第7页共14页3.3.4希尔排序开始Y结束N初始化变量i,d=L.length/2,j,w=0w小于di=1,i小于L.lengthj=i+dJ小于L.length第i个元素大于第j个元素交换第i个元素第j个元素d变为原来的一半YYY第8页共14页3.3.5快速排序开始结束NYY初始化变量pivotkey,low,highLow小于high第high个元素大于pivotkey第low个元素小于pivotkey第low个元素与第high个元素交换第high个元素与第low个元素交换high--Low++Y第9页共14页4、详细设计：4.1函数调用关系图5、各个算法实现的源程序：5.1、冒泡排序及其主要算法voidqipao(SqList&L)//起泡{start_t=clock();inti=1,j;while(iL.length){for(j=1;jL.length;j++){if(L.elem[j].keyL.elem[j+1].key){L.elem[0].key=L.elem[j].key;L.elem[j].key=L.elem[j+1].key;L.elem[j+1].key=L.elem[0].key;}开始界面各排序输出结果起泡排序直插排序选择排序希尔排序快速排序各种排序用时比较起泡排序用时直插排序用时选择排序用时希尔排序用时快速排序用时第10页共14页}i++;}5.2、直接插入排序及其主要算法voidInsertSort(SqList&L)//直接插入{start_t=clock();inti,j;for(i=2;i=L.length;i++){if(L.elem[i].key=L.elem[i-1].key)//“”，需将L.r[i]插入有序子序列{L.elem[0].key=L.elem[i].key;//复制为哨兵j=i-1;while(L.elem[0].keyL.elem[j].key){L.elem[j+1].key=L.elem[j].key;//记录后移j--;}L.elem[j+1].key=L.elem[0].key;//插入到正确位置}}5.3、选择排序及其主要算法voidSelectSort(SqList&L)//选择{inti,j,k,;for(i=1;iL.length;i++)//选择第i小的记录，并交换到位{for(j=i+1;jL.length;j++){if(L.elem[j].key=L.elem[k].key){L.elem[0].key=L.elem[i].key;L.elem[i].key=L.elem[k].key;L.elem[k].key=L.elem[0].key;//与第i个记录交换}}第11页共14页5.4、希尔排序及其主要算法voidxier(SqList&L)//希尔排序并打印结果{start_t=clock();inti,d=L.length/2,j,w=0,k,yd=0,bj=0;//间长为dwhile(wd){for(i=1;i=L.length;i++)//第i个与第i+d个相比较{j=i+d;if(j=L.length){if(L.elem[i].keyL.elem[j].key){k=j;bj++;if(i!=k){L.elem[0].key=L.elem[i].key;L.elem[i].key=L.elem[k].key;L.elem[k].key=L.elem[0].key;}}}}d=d/2;//间隔变为原来的一半}5.5、快速排序及其主要算法intPartition(SqList&L,intlow,inthigh)//快速排序{intpivotkey;L.elem[0]=L.elem[low];yd1++;pivotkey=L.elem[low].key;//用子表的第一个记录作曲轴记录while(lowhigh)//从子表的两端交替的向中间扫描{yd1++;while(lowhigh&&L.elem[high].key=pivotkey)--high;第12页共14页L.elem[low]=L.elem[high];//将比轴记录小的记录交换到低端while(lowhigh&&L.elem[low].key=pivotkey)L.elem[high]=L.elem[low];//将比轴记录大的记录交换到高端}L.elem[low]=L.elem[0];returnlow;//返回曲轴所在位置}voidQSort(SqList&L,intlow,inthigh){//对顺序表L.r[low..high]做快速排序intpivotloc;inti=1;if(lowhigh)//长度大于一{pivotloc=Partition(L,low,high);//将L.r[low..high]一分为二QSort(L,low,pivotloc-1);//对低字表递归排序QSort(L,pivotloc+1,high);//对高字表递归排序}}voidQuickSort(SqList&L){//对顺序表L做快速排序intj;BeforeSort();QSort(L,1,L.length);for(j=1;j=L.length;j++)printf(%d,L.elem[j]);display(yd1,bj