数据结构课程设计--内部排序算法的比较.doc

数据结构课程设计中国海洋大学数据结构课程设计题目：内部排序算法的比较姓名：李吉倩学号：020332010046 系年级：计算机科学与技术2010级完成时间：2012.8-2012.911数据结构课程设计中国海洋大学实验报告1、 需求分析1. 本程序对以下六种常用的内部排序进行实测比较：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。2.待排序表的元素的关键字为整数，雍正徐、逆序和随机数产生器产生的随机数做测试比较。比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换记为3次移动）。3.程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”下，用户可由键盘输入产生随机数的种子，计算机终端显示各内部排序的比较参数。4.最终对结果做出简单分析，包括对各组数据得出结果波动大小给予解释。二、概要设计1.可排序表的抽象数据类型定义：ADT OrderableList数据对象：D = ai |ai IntegerSet,i = 1,2,n,n = 0数据关系：R1 = |ai-1,ai D.i = 2,n基本操作：SelectListType(c)操作结果：打印提示信息，请用户选择待排序表的类型，顺序型、 逆序型还是随机数组。BubbleSort(&L)操作结果：进行起泡排序，返回排序后的顺序表InsertSort(&L)操作结果：进行插入排序，返回排序后的顺序表SelectSort(&L)操作结果：进行选择排序，返回排序后的顺序表QuickSort(&L)操作结果：进行快速排序，返回排序后的顺序表ShellSort(&L)操作结果：进行希尔排序，返回排序后的顺序表HeapSort(&L)操作结果：进行堆排序，返回排序后的顺序表SelectSortMethod(&L,c1)操作结果：打印提示信息，请用户选择排序方法，起泡排序、插入排序、选择排序、快速排序、希尔排序还是堆排序 OutPut(L)操作结果：打印排序中关键字的比较次数和移动次数 ADT OrderableList2. 本程序包含两个模块：1）.主程序模块 int mian()初始化； 用户选择待测表的类型； 输入选择，用switch语句判断； While（“命令” ！= “退出”） 接受命令； 处理命令； ）可排序表单元模块-实现可排序表的抽象数据类型 各模块之间的调用关系： 主程序模块 可排序表单元模块三、详细设计1.根据题目要求何可排序表的基本操作特点，可排序表采用证书顺序表存储结构，并实现在头文件SqList.H。/*基本操作的函数原型*#define MAXSIZE 20 /用作示例的顺序表的最大长度typedef int KeyType; /定义关键字为整数类型typedef int InfoType; /定义其他数据项也为整数类型int time_key_compare = 0; /定义全局变量，关键字比较次int time_key_move = 0; /数和移动次数均为0typedef structKeyType key; /关键字项InfoType otherinfo; /其他数据项RedType; /记录类型typedef structRedType rMAXSIZE + 1; /r0闲置或用做哨兵int length; /顺序表长度SqList; /顺序表类型/*基本操作*bool LT(KeyType a,KeyType b)/比较两个KeyType类型变量的大小time_key_compare +; /比较次数+1if(a b)return true; /,返回trueelse return false; /否则，返回false /LTvoid copyKey(RedType &a,RedType &b) /将RedType类型变量b复制给a a = b;time_key_move +; /关键字移动次数+1/copyKeyvoid swap(RedType &a,RedType &b) /将RedType型变量a和b进行交换操作RedType c; /定义RedType型变量cc = a;a = b;b = c;time_key_move += 3; /关键字移动次数+3/swap/*直接插入排序*void InsertSort(SqList &L) /对顺序表L做直接插入排序for(int i = 2; i = L.length; +i)if(LT(L.ri.key,L.ri - 1.key) /“”，需将L.ri插入有序子表 copyKey(L.r0 ,L.ri); /复制为哨兵copyKey(L.ri ,L.ri - 1);for(int j = i - 2;LT(L.r0.key,L.rj.key); -j) copyKey(L.rj + 1 ,L.rj); /记录后移copyKey(L.rj + 1 ,L.r0); /插入到正确的位置/InsertSort/*希尔排序*void shellInsert(SqList &L,int dk) /对顺序表L做一希尔插入排序。/1.前后记录位置的增量式是dk，而不是1；/2.r0只是暂存单元，不是哨兵。当 j= 0时，插入位置已找到for(int i = dk + 1;i 0 & LT(L.r0.key,L.rj.key); j-= dk) copyKey(L.rj + dk ,L.rj); /记录后移copyKey(L.rj + dk ,L.r0); /插入/ShellInsertvoid ShellSort(SqList &L,int dlta,int t) /按增量序列dlta0t - 1对顺序表L作希尔排序for(int k = 0;k 1)int lastExchangeIndex = 1;for(int j = 1;j i ;j +)if(LT(L.rj + 1.key,L.rj.key) /小于成立进行交换swap(L.rj + 1,L.rj);lastExchangeIndex = j;i = lastExchangeIndex;/BubbleSort/*简单选择排序*/int SelectMinKey(SqList L,int i) /在L.ri.L.length中选择key最小的记录 for(int j = i ;j = L.length; +j) if(LT(L.rj.key,L.ri.key)i = j;return i; /返回最小记录下标void SelectSort(SqList &L) /对顺序表做简单选择排序for(int i = 1;i L.length; +i) /选择第i小的记录，并交换到位int j = SelectMinKey(L,i); /令j为L.ri.L.length中选择key最小的记录if(i != j)swap(L.rj,L.ri); /与第i记录进行交换/SelecteSort/*快速排序*/int Partition(SqList &L,int low,int high) /交换顺序表L中字表rlowhigh的记录，枢轴记录到位 ，并 /返回其所在位置，此时在他之前（后）的记录均不大（小）与它。 copyKey(L.r0,L.rlow);/用字表的第一个纪录作枢轴记录 KeyTypepivotkey=L.rlow.key; /枢轴记录关键字 while(low high) /从表的两端交替向中间扫描while(lowhigh& !LT(L.rhigh.key,pivotkey) -high; copyKey(L.rlow,L.rhigh); /将比枢轴记录小的记录移到低端while(lowhigh & !LT(pivotkey,L.rlow.key)+low; copyKey(L.rhigh,L.rlow); /将比枢轴记录大的记录移到高端 copyKey(L.rlow,L.r0); /枢轴记录到位return low; /返回枢轴位置/Partitionvoid QSort(SqList &L,int low,int high) /对顺序表L中的子序列L.rlowhigh做快速排序if(low 1int pivotloc = Partition(L,low,high); /将L.rlowhigh一分为二QSort(L,low,pivotloc - 1); /对低子表递归排序，pivotloc是枢轴位置QSort(L,pivotloc + 1,high); /对高子表递归排序/QSortvoid QuickSort(SqList &L) /对顺序表L做快速排序QSort(L,1,L.length);/QuickSort/*堆排序*/void HeapAdjust(SqList &L,int s,int m) /已知L.rs.m中记录的关键字除L.rs.key之外均满足定义， /本函数调整H.rs的关键字，使H.rs.m成为一个大顶对RedType rc = L.rs;for(int j = 2 * s;j = m;j *= 2) /沿key较大的孩子结点向下帅选if(j 0;-i) /把L.r1.H.length建成大顶堆HeapAdjust(L,i,L.length);for( i = L.length;i 1; -i)swap(L.r1,L.ri); /将堆顶记录和当前未经排序的子序列 / L.r1i中最后一个记录进行交换HeapAdjust(L,1,i - 1);/将L.r1.i-1重新调整为大顶堆/HeapSort2.主函数和其他辅助函数的伪码算法#include /产生随机数所需的库函数/*主函数*/int main() int arryMAXSIZE + 1; /存放排序前数组 int typeChoice; /根据提示键入的类型选择序号 int methodChoice; /根据提示键入的方法选择序号 int seed; /用于产生随机数的种子 PrintArrayMenu(); /打印选择待排序表的类型菜单 switch(typeChoice) case 1:选择的是顺序表，初始化链表并打印 break;case 2:选择的是逆序表，初始化链表并打印 break;case 3:选择的是随机数表srand(seed); /初始化随机数，并利用rand（）产生随机数并打印break;default:break; cout L.length; /打印待排序数组的长度 PrintMenu(); /打印排序方法选择菜单 while(methodChoice!= 7) getChoice(L,choice); /根据选择的方法堆表进行排序操作并打印相关信息 for( j = 1;j = MAXSIZE; j +) /将链表恢复至未排序时状态 L.rj.key = arryj;return 0;/*根据选择排序*/void getChoice(SqList &L,int c) /根据选择进行排序并输出相关信息 int Array3 = 5,3,1; /希尔排序所需增量数组 switch(c)case 1:InsertSort(L); / 直接插入排序 outPut(L); /输出关键字比较次数和移动次数break;case 2:ShellSort(L,Array,3); /希尔排序outPut(L); /输出关键字比较次数和移动次数break;case 3:BublleSort(L); /起泡排序outPut(L); /输出关键字比较次数和移动次数break;case 4:SelectSort(L); /简单选择排序outPut(L); /输出关键字比较次数和移动次数break;case 5:QuickSort(L); /快速排序outPut(L); /输出关键字比较次数和移动次数break;case 6:HeapSort(L); /堆排序outPut(L); /输出关键字比较次数和移动次数break;case 7:排序结束default:break;3. 函数的调用关系图反映了程序的层次结构 InsertSort 顺序表 ShellSort 主程序 BublleSort 逆序表 getTypeChoice getMethodChoice SelectSort 随机数表 QuickSort HeapSortsrand rand4、 排序算法结果比较测试直接插入排序希尔排序起泡排序简单选择排序快速排序堆排序表长顺序表19/051/019/0209/0190/76121/11820逆序表209/228110/108190/570209/30200/76105/10020随即表1134/147105/85184/345209/51105/76115/10920随即表2106/119119/101174/261209/45114/72118/10920随即表399/108107/84165/240209/42107/74119/11820随即表4123/134117/98176/312209/48104/82109/10620随即表5140/153105/85189/363209/51119/72107/10120随即表624962887/249728725153988/514622649981281/7485866450004999/29976226064/75760235476即表725067619/250776025161759/515379949952164/7517286050004999/29964225821/76130235408即表824951520/249614935183866/517613149904576/7482456350004999/29970223755/75818235241即表925231354/252413275240599/523273249959846/7566406550004999/29982216797/75786235488即表1024940230/249502195166043/515819849952854/7479069350004999/29967210437/76844235432各种表长和测试组数进行了测试，程序运行正常。分析实测得到的数值，六种排序算法的特点小结如下