江苏大学数据结构课设

《江苏大学数据结构课设》由会员分享，可在线阅读，更多相关《江苏大学数据结构课设（26页珍藏版）》请在装配图网上搜索。

1、数据结构课程设计报告几种排序算法的演示班级：姓名：学号：完成日期：一需求分析1运行环境Microsoft Visual Studio 20082程序所实现的功能对直接插入排序、折半插入排序、冒泡排序、简单选择排序、快速排序、堆排序、归并 排序算法的演示，并且输出每一趟的排序情况。3程序的输入（包含输入的数据格式和说明）排序种类三输入排序数的个数的输入所需排序的所有数的输入4.程序的输出（程序输出的形式）主菜单的输出每一趟排序的输出，即排序过程的输出5测试数据，如果程序输入的数据量比较大，需要给出测试数据。二设计说明1算法设计思想交换排序（冒泡排序、快速排序）交换排序的基本思想是：对排序表中的数

2、据元素按关键字进行两两比较，如果发生逆序 （即排列顺序与排序后的次序正好相反），则两者交换位置，直到所有数据元素都排好序为 止。插入排序（直接插入排序、折半插入排序）插入排序的基本思想是:每一次设法把一个数据元素插入到已经排序的部分序列的合适 位置，使得插入后的序列仍然是有序的。开始时建立一个初始的有序序列，它只包含一个数 据元素。然后，从这个初始序列出发不断插入数据元素，直到最后一个数据元素插到有序序 列后，整个排序工作就完成了。选择排序（简单选择排序、堆排序）选择排序的基本思想是:第一趟在有n个数据元素的排序表中选出关键字最小的数据元 素，然后在剩下的n-1个数据元素中再选出关键字最小（整

3、个数据表中次小）的数据元素， 依次重复，每一趟（例如第i趟，i=1,，n-1）总是在当前剩下的n-i+1个待排序数据元 素中选出关键字最小的数据元素，作为有序数据元素序列的第i个数据元素。等到第n-1趟 选择结束，待排序数据元素仅剩下一个时就不用再选了，按选出的先后次序所得到的数据元 素序列即为有序序列，排序即告完成。归并排序（两路归并排序）两路归并排序的基本思想是：假设初始排序表有n个数据元素，首先把它看成是长度为 1的首尾相接的n个有序子表（以后称它们为归并项），先做两两归并，得n/2上取整个长度 为2的归并项（如果n为奇数，则最后一个归并项的长度为1）；再做两两归并， ，如 此重复，最后

4、得到一个长度为n的有序序列。2程序的主要流程图3程序的主要模块（要求对主要流程图中出现的模块进行说明）程序的主要模块主要分为主菜单模块和排序算法演示模块。主菜单主要功能：程序运行时，可使运行者根据提醒输入相关操作，从而进入不同的排序方法或者 退出。排序方法及输出根据运行者对排序的不同选择，进入排序过程a. 直接插入排序：根据直接排序的算法，输出排序过程b. 折半插入排序：根据折半插入的算法，输出排序过程c. 冒泡排序：根据冒泡排序算法，输出排序过程d. 简单选择排序：根据简单选择排序的算法，输出排序过程e. 快速排序：根据快速排序的算法，输出排序过程f. 堆排序：根据堆排序的算法，输出排序过程

5、g. 归并排序：根据归并排序的算法，输出排序过程4程序的主要函数及其伪代码说明模板类主要说明程序中用到的类的定义templatevclass typeclass sortlistprivate:int currentsize;/数据表中数据元素的个数public:type *arr;/存储数据元素的向量(排序表)sortlist():currentsize(0)arr=new typemaxsize; 构造函数sortlist(int n)arr=new typemaxsize;currentsize=n;void insert(int i,type x)arri=x;sortlist()de

6、lete arr; 析构函数void swap(type &x,type &y)数据元素x和y交换位置type temp=x;x=y;y=temp;void bubblesort。;/ 冒泡排序void quicksort(int low,int high);/快 快速排序void insertionsort();直接插入排序void binaryinsertsort(); 折半插入排序void selectsort();/ 简单选择排序void heapsort(); 堆排序void mergesort(sortlistvtype & table) 归并排序void filterdown(c

7、onst int start);/建 立最大堆void mergepass(sortlist&sourcetable,sortlist&mergedtableconst int len);一趟 归并void merge(sortlist&sourcetable,sortlist&mergedtableconst int left,const int mid,const int right);/ 两路归并算法;v2直接插入排序直接插入排序的基本思想：开始时把第一个数据元素作为初始的有序序列，然后从第二 个数据元素开始依次把数据元素按关键字大小插入到已排序的部分排序表的适当位置。当插 入第i(lv

8、iv=n)个数据元素时，前面的i-1个数据元素已经排好序，这时，用第i个数据元素 的关键字与前面的i-1个数据元素的关键字顺序进行比较，找到插入位置后就将第i个数据 元素插入。如此进行n-1次插入，就完成了排序。以下是在顺序表上实现的直接插入排序在顺序表上进行直接插入排序时，当插入第i(1iarr1.、 arri-2已经排好序，这时，用arri-1的关键字依次与arri-2,arri-3,.的关键字顺序进行比 较，如果这些数据元素的关键字大于arri-1的关键字，则将数据元素向后移一个位置，当 找到插入位置后就将arri-1插入，就完成了 arr0,arr1,.,arrn-1的排序。伪代码如下

9、template class type直接插入排序void sortlist:insertionsort()type temp;int j;for(int i=1;iv=currentsize-1;i+)temp=arri;j=i-1;while(j=0&tempvarrj)arrj+1=arrj;j-;arrj+1=temp;coutvv第vv+numvv趟排序结果为:；for(int t=O;tvcurrentsize;t+)coutarrt折半插入排序折半插入排序的基本思想：设在排序表中有n个数据元素arrO,arrl,.,arrn-l。其中， arrO,arrl,.,arrn-l是已经

10、排好序的部分数据元素序列，在插入arri时，利用折半查找方 法寻找arri的插入位置。折半插入排序方法只能在顺序表存储结构实现。伪代码如下：template vclass type折半插入排序void sortlistvtype:binaryinsertsort()type temp;int left,right;for(int i=1;i=left;k-) 向后移动arrk+1=arrk;arrleft=temp;coutvv第vv+numvv趟排序结果为:；for(int t=0;tvcurrentsize;t+)coutvvarrtvv;coutvvendl;num=0;冒泡排序冒泡排序

11、的基本思想是：设排序表中有n个数据元素。首先对排序表中第一，二个数据 元素的关键字arr0和arr1进行比较。如果前者大于后者，则进行交换；然后对第二，三个 数据做同样的处理;重复此过程直到处理完最后两个相邻的数据元素。我们称之为一趟冒泡， 它将关键字最大的元素移到排序表的最后一个位置，其他数据元素一般也都向排序的最终位 置移动。然后进行第二趟排序，对排序表中前n-1个元素进行与上述同样的操作，其结果使 整个排序表中关键字次大的数据元素被移到arrn-2的位置。如此最多做n-1趟冒泡就能把 所有数据元素排好序。伪代码如下： template vclass type 冒泡排序 void sort

12、listvtype:： bubblesort()int i=1;int finish=0;/0表示还没有排好序 while(ivcurrentsize &! finish)finish=l;排序结束标志置为，假定已经排好序for(int j=O;jvcurrentsize-i;j+) if(arrjarrj+1)/逆 序 swap(arrj,arrj+1);/相 邻元素交换位置 finish=0;排序结束标志置为，表示本趟发生了交换，说明还没有排好序i+;coutvv第vv+numvv趟排序结果为:;for(int t=0;tcurrentsize;t+) coutvvarrtvv ;cout

13、vvendl;num=0;简单选择排序(直接选择排序)直接选择排序的算法基本思想是：a) 开始时设i的初始值为0。b) 如果ivn-1,在数据元素序列arri arrn-1中，选出具有最小关键字的数据元素arrk；否 则算法结束。c) 若arrk不是这组数据元素中的第一个数据元素(i#k则将arrk与arri这两数据元素的 位置对调；d) 令i=i+1转步骤b)。伪代码如下：template vclass typevoid sortlistvtype:selectsort() 简单选择排序int k;for(int i=0;iv=currentsize-1;i+)k=i;for(int j=i

14、+1;jvcurrentsize;j+)if(arrjvarrk)k=j;/k指示当前序列中最小者的位置if(k!=i)最小关键字的数据元素位置不等于iswap(arri,arrk);coutvv第vv+numvv趟排序结果为:；for(int t=O;tvcurrentsize;t+)coutvvarrtvv;coutvvendl;num=0;v6快速排序快速排序(Quick Sort)又被称做分区交换排序，这是一种平均性能非常好的排序方法。 其算法基本思想是：任取排序表中的某个数据元素(例如取第一个数据元素)作为基准，按照 该数据元素的关键字大小，将整个排序表划分为左右两个子表：左侧子表中

15、所有数据元素 的关键字都小于基准数据元素的关键字。右侧子表中所有数据元素的关键字都大于或等于基 准数据元素的关键字，基准数据元素则排在这两个子表中间(这也是该数据元素最终应安放 的位置)，然后分别对这两个子表重复施行上述方法的快速排序，直到所有的子表长度为1, 则排序结束。伪代码如下：template vclass type/快速排序void sortlistvtype:quicksort(int low,int high)/在待排序区间1 ow,high上，递归地进行快速排 序int i=1ow,j=high;type temp=arr1ow;取区间第一个位置为基准位置if(ij)whi1e

16、(ij)whi1e(ij &temparrj)j-;if(ij)swap(arri,arrj);i+;whi1e(i=arri)i+; if(i堆排序(包括建立最大堆和堆排序两个过程)堆排序算法的基本思想是：a. 对排序表中的数据元素，利用堆的调整算法形成初始堆。b. 输出堆顶元素。c. 对剩余元素重新调整形成堆。d. 重复执行第b、c步，直到所有数据元素被输出。(1)建立最大堆的伪代码如下：template vclass type建立最大堆void sortlistvtype:filterdown(const int start)向下调整使从start开始到currentsize-1为止的子

17、表成为最大堆int i=start,j=2*i+1;/j 为 i 的左孩子int tablesize=currentsize;type temp=arri;while(j=currentsize-1)if(jcurrentsize-1 & arrj=arrj)break;elsearri=arrj;i=j;j=2*j+1;arri=temp;堆排序如果建立的堆满足最大堆的条件，则堆的第一个数据元素arr0具有最大的关键字，将arr0 与arrn-1 对调，把具有最大关键字的数据元素交换到最后，再对前面的n-1个数据元素使 用堆的调整算法，重新建立最大堆，结果把具有次最大关键字的数据元素又上浮到

18、堆顶，即 arr0的位置，再对调arr0和arrn-2,，如此反复执行n-1 次,最后得到全部排序好的数 据元素序列。伪代码如下：template vclass type堆排序void sortlistvtype:heapsort()int tablesize=currentsize;for(int i=(currentsize-2)/2;i=0;i-)filterdown(i);初始建堆for(int i=currentsize-1;i=1;i-)swap(arr0,arri);/堆顶元素和最后一个元素交换currentsize-;filterdown(O);/ 重建最大堆coutvv第vv

19、+numvv趟排序结果为:； for(int t=0;tvtablesize;t+)coutvvarrtvv9coutvvendl;num=0;currentsize=tablesize;归并排序(包括归并算法，一趟归并算法和归并排序) 归并算法其基本思想是：设有两个有序表A和B,其数据元素个数(表长)分别为n和m,变量i 和j分别是表A和表B的当前检测指针；设表C是归并后的新有序表，变量k是它的当前 存放指针。开始时i、j、k都分别指向A、B、C三个表的起始位置；然后根据Ai与Bj 的关键字的大小，把关键字小的数据元素放到新表Ck中；且相应的检测指针(i或j)和 存放指针k增加1如此循环，当

20、i与j中有一个已经超出表长时，将另一个表中的剩余部分 照抄到新表CkCm+n中。下面的归并算法中，两个待归并的有序表首尾相接存放在数组sourcetable.arr中，其中第一 个表的下标范围从left到mid，另一个表的下标范围从 mid+1到right。前一个表中有 mid-left+1个数据元素,后一个表中有right -mid个数据元素。归并后得到的新有序表有right -mid个数据元素。归并后得到的新有序表存放在另一个辅助数组mergedtable.arr中，其下 标范围从left到righto伪代码如下：template voidsortlistvtype:merge(sortl

21、istvtype &sourcetable,sortlistvtype &m ergedtableconstintleft,const int mid,const int right)int i=left,j=mid+1,k=left;指针初始化/i是前一段的当前元素位置，j是后一段的当前元素位置，k是辅助数组的当前位置 while(iv=mid&jv=right)if(sourcetable.arri=sourcetable.arrj)mergedtable.arrk=sourcetable.arri;i+;k+; elsemergedtable.arrk=sourcetable.arrj;

22、j+;k+; if(i=mid)for(int p=k,q=i;qv=mid;p+,q+)mergedtable.arrp=sourcetable.arrq把前一段复制至U mergedtableelsefor(int p=k,q=j;q=right;p+,q+)mergedtable.arrp=sourcetable.arrq把后一段复制至U mergedtable 一趟归并算法设数组sourcetable.arr0到sourcetable.arrn-1中的n个数据元素已经分为一些长度为len的 归并项，将这些归并项两两归并，归并成一些长度为2len的归并项，结果放到mergedtable.

23、arr 中。如果n不是2len的整数倍，则一趟归并到最后，可能遇到两种情况：剩下一个长度为len的归并项和一个长度不足len的归并项，可用一次merge算法，将它们 归并成一个长度小于2len的归并项。只剩下一个归并项，其长度小于或等于len，可将它直接复制到数组mergedtable.arr 中。伪代码如下：template vclass typetemplate void sortlistvtype:mergepass(sortlistvtype &sourcetable,sortlistvtype &m ergedtableconst int len)int i=0;while(i+2*

24、lenv=currentsize-l) 表示至少有个子序列merge(sourcetable,mergedtable,i,i+len-1,i+2*len-1);i+=2*len;if(i+lenv=currentsize-1)若只有最后两个子序列merge(sourcetable,mergedtable,i,i+len-1,currentsize-1);else/若只有最后一个子序列for(int j=i;jv=currentsize-1;j+)mergedtable.arrj=sourcetable.arrj;if(len=currentsize-1)if(numvcurrentsize)c

25、outvv第vv+numvv趟排序结果为:；for(int t=0;tcurrentsize;t+)coutmergedtable.arrt=n， 因此在则趟归并中while循环不执行，只做把temptable.arr中的数据元素复制到table.arr 的工作。伪代码如下：template void sortlist:mergesort(sortlist & table )按数据元素关键字非递减的顺序对排序表table中数据元素进行递归排序sortlist temptable;int len=1;while(lenvcurrentsize)mergepass(table,temptable,

26、len);len*=2;mergepass(temptable,table,len);len*=2;num=0;v9主函数主要功能是显示主菜单，以及对各种排序的调用 伪代码如下：三上机结果及体会int main()/ 主函数time_t timestart,timeend;double timeused;double timestart,timeend,timeused;int c=1;char ch;int n1=0;while(c!=0)coutendl;cout*coutendl;cout= 排=endl;cout2.冒泡排序cout1.直接插入排序endl;cout5.折半插入排序6简

27、单选择排序7.堆排序0.退出排序程序endl;3.快速排序 4.归并排序endl;coutendl;coutendl;coutn请选择所需排序法：；cinch;if(ch=0)cout退出系统!=0&ch=7)coutn;coutn请输入n个数：;sortlisttable(n);for(int i=O;icishuber;table.insert(i,cishuber);switch(ch)case T:coutn直接插入排序法过程演示nendl;timestart=GetTickCount();/(double)clock(); 程序段开始前取得系统运行时间(ms)Sleep(lOOO);

28、table.zhicha();timeend=GetTickCount();/(double)clock(); 程序段结束后取得系统运行时间(ms) timeused=timeend-timestart;/(double)(timeend-timestart)/CLK_TCK;cout直接插入排序用时为:timeusedms;break;system(pause);break;case 2:coutn冒泡排序法过程演示nendl;timestart=GetTickCount();/(double)clock(); 程序段开始前取得系统运行时间(ms)Sleep(1000);table.maop

29、ao();timeend=GetTickCount();/(double)clock(); 程序段结束后取得系统运行时间(ms) timeused=timeend-timestart;/(double)(timeend-timestart)/CLK_TCK;cout冒泡排序用时为:timeusedms;break;system(pause);break;case 3:coutn快速排序法过程演示nendl;timestart=GetTickCount();/(double)clock(); 程序段开始前取得系统运行时间(ms)Sleep(1000);table.kuaisu(0,n-1);ti

30、meend=GetTickCount();/(double)clock(); 程序段结束后取得系统运行时间(ms) timeused=timeend-timestart;/(double)(timeend-timestart)/CLK_TCK;cout快速排序用时为:timeusedms;break;system(pause);break;case 4:coutn=归并排序法过程演示=nendl;timestart=GetTickCount();/(double)clock(); 程序段开始前取得系统运行时间 (ms)Sleep(lOOO);table.mergesort(table);tim

31、eend=GetTickCount();/(double)clock(); 程序段结束后取得系统运行时间(ms) timeused=timeend-timestart;/(double)(timeend-timestart)/CLK_TCK;cout归并排序用时为:timeusedms;break;system(pause);break;case 5:coutn =折半插入排序法过程演示=nendl; timestart=GetTickCount();/(double)clock(); 程序段开始前取得系统运行时间(ms) Sleep(1000);table.binaryinsertsort(

32、);timeend=GetTickCount();/(double)clock(); 程序段结束后取得系统运行时间(ms) timeused=timeend-timestart;/(double)(timeend-timestart)/CLK_TCK;cout折半插入排序用时为:timeusedms;break;system(pause);break;case 6:coutn=简单选择排序法过程演示=nendl;timestart=GetTickCount();/(double)clock(); 程序段开始前取得系统运行时间 (ms)Sleep(1000);table.selectsort()

33、;timeend=GetTickCount();/(double)clock(); 程序段结束后取得系统运行时间(ms) timeused=timeend-timestart;/(double)(timeend-timestart)/CLK_TCK;cout简单选择排序用时为:timeusedms;break;system(pause);break;case 7:coutn=堆排序法过程演示=nendl;timestart=GetTickCount();/(double)clock(); 程序段开始前取得系统运行时间(ms)Sleep(lOOO);table.heapsort();timeen

34、d=GetTickCount();/(double)clock(); 程序段结束后取得系统运行时间(ms) timeused=timeend-timestart;/(double)(timeend-timestart)/CLK_TCK;cout堆排序用时为:timeusedms;break;system(pause);break; system(pause);return 0;1运行情况主菜单=排序法选择=1-直接插入排序2 冒泡排序快速排序 衣归并排序5 -折半插入排序6 -简单选择排序7 -堆排序0 -退岀排序程序请选择所需排序法：直接插入排序请输入排序的数的个数：5请输人5个数：10 9

35、 8 7 6直接插入排序法过程演示= =12 3 4第第第善一二一二一二一二.111肖一世肖一也堀为为为为弔 nPa.- -丿 LUFBhshsF 二予. 士口士 口士口士口匚 J.LLI61.:寸H10 8 ? 6910768910678910：1030ms冒泡排序请输入排序的数的个数：5请输入石个数：10 Y 8 7石=冒泡排序法过程演示=快速排序请输入排序的数的个数：5请输入吕个数：10 9 8 7 6快速排序法过程演示=走走走走朿5 6 7 81-1为为为昭 mP mP rtP my 斗. LllFsFsFEk 士口士口士口吉 序序序序 _ _ _. 一二.-二.一二.：698：698

36、：678：6781030ms10101010归并排序请输入排序的数的个数：5请输入5个数：佃9 8 7石=归井排序法过程演示趟排宦審|扣9 10 7 8 6 底结集为汐8910 6序结 0=6?8910弓用时为:1029ms折半插入排序请输入排序的数的个数：5请输入弓个数：10 9 8 7 6=折半插入排序法过程演示=. . 一二一二一二 二-111 12 3 44伪为伪为 HFHpHFHF-匚丿 LUFBFBFBF 二予. 士口士 口士 口士 口匚丿 序序序序炜.LLI6V-/.10101010简单选择排序请输入排序的数的个数：5请输入5个数：10 9 8 7 6简单选择排序法过程演示1 2

37、 3 4 .第第第第简6 6 6 6 _Qr:._Qr:._Qr:._Qr:.0t nrrnrrrrnrr-丿 luw.efef 二予. 士口士 口士口士口匚 J 序序序序轴.LLLI987789789789：1030ms10101010堆排序请输入排序的数的个数：5 请输入5个数：10 9 8 7 6堆排序法过程演示1H8 66 98 9101010108 9退出排序四、源代码#include#include#includeusing namespace std;const int maxsize=100;int cishu=0;定义全局变量，为每一趟的输出做准备int x=0;templa

38、teclass sortlistprivate:int momentsize;/数据表中数据元素的个数public:type *arr;存储数据元素的向量(排序表) sortlist():momentsize(0) 无参的构造函数arr=new typemaxsize;sortlist(int n)/带参的构造函数arr=new typemaxsize;momentsize=n;void insert(int i,type x)arri=x;sortlist()delete arr;/ 析构函数void swap(type &x,type &y)数据元素x和y交换位置type temp=x;x

39、=y;y=temp;void maopao();/ 冒泡排序void kuaisu(int low,int high); 快速排序void zhicha();/直接插入排序void binaryinsertsort();/ 折半插入排序void selectsort();/ 简单选择排序void heapsort();/ 堆排序void mergesort(sortlist & table); 归并排序void filterdown(const int start);/建立最大堆void mergepass(sortlist&sourcetable,sortlist&mergedtable,c

40、onst int len);一趟归并void merge(sortlist&sourcetable,sortlist&mergedtable,const int left,const int mid,const int right);/两路归并算法； template class type/ 直接插入排序void sortlist:zhicha()type temp;int b;for(int a=l;a=0&temparrb)arrb+1=arrb;b-;arrb+1=temp;cout第+cishu趟排序结果为:;for(int t=0;tmomentsize;t+) coutarrt;c

41、outendl;cishu=0; template / 折半插入排序void sortlist:binaryinsertsort()type temp;int left,right;for(int b=1;bmomentsize;b+)left=0;right=b-1;temp=arrb;/ 所要插入的数; while(left=right) 找插入位置 int mid=(left+right)/2; if(temp=left;k-) 向后移动arrk+1=arrk; arrleft=temp;cout第+cishu趟排序结果为:；for(int t=0;tmomentsize;t+)cout

42、arrt;coutendl;cishu=0;template class type/ 冒泡排序void sortlist: maopao()int a=1;int finish=0;/ 0表示还没有排好序while(amomentsize &! finish)finish=1;/排序结束标志置为，假定已经排好序for(int b=0;barrb+l) 逆序swap(arrb,arrb+1);/相邻元素交换位置 finish=0;/排序结束标志置为,表示本趟发生了交换，说明还没有排好序a+;cout第+cishu趟排序结果为:；for(int t=0;tmomentsize;t+)coutarr

43、t;coutendl;cishu=0;template void sortlist:selectsort() 简单选择排序int k;for(int a=0;amomentsize-1;a+)k=a;for(int b=a+1;bmomentsize;b+)if(arrbarrk)k=b;/k指示当前序列中最小者的位置if(k!=a)/最小关键字的数据元素位置不等于iswap(arra,arrk);cout第+cishu趟排序结果为:;for(int t=0;tmomentsize;t+) coutarrt;coutendl;cishu=0; template class type/ 快速排序

44、void sortlist:kuaisu(int low,int high)/在待排序区间low,high上，递归地进行快速排序int i=low,j=high;type temp=arrlow;/取区间第一个位置为基准位置if(ij)while(ij)while(ij &temparrj)j-; if(ij)swap(arri,arrj);i+; while(i=arri)i+; if(ij)swap(arri,arrj);j-;arri=temp;/将基准元素就位cout第+x 趟排序结果为:;for(int t=0;tmomentsize;t+)coutarrt;coutendl;kua

45、isu(low,i-l);在左子区间递归进行快速排序 kuaisu(i+1,high);/在右子区间递归进行快速排序 template / 建立最大堆void sortlist:filterdown(const int start)/向下调整使从start开始到momentsize-1为止的子表成为最大堆int a=start,b=2*a+1;/j 为i 的左孩子int tablesize=momentsize;type temp=arra;while(b=momentsize-1)if(bmomentsize-1 & arrb=arrb)break;elsearra=arrb;a=b;b=2

46、*b+l;arra=temp;template class typevoid sortlist:heapsort()int tablesize=momentsize;for(int i=(momentsize-2)/2;i=0;i-)filterdown (i);初始建堆for(int i=momentsize-1;i=1;i-)swap(arr0,arri);/堆顶元素和最后一个元素交换momentsize-;filterdown(O);/ 重建最大堆cout第+cishu趟排序结果为:；for(int t=0;ttablesize;t+)coutarrt;coutendl;cishu=0;

47、momentsize=tablesize;inttemplate / 归并排序voidsortlist:merge(sortlist&sourcetable,sortlist&m ergedtable,constint left,constmid,const int right)int i=left,j=mid+1,k=left; 指针初始化i是前一段的当前元素位置，j是后一段的当前元素位置，k是辅助数组的当前位置while(i=mid&j=right)if(sourcetable.arri=sourcetable.arrj)mergedtable.arrk=sourcetable.arri;

48、i+;k+; elsemergedtable.arrk=sourcetable.arrj;j+;k+; if(i=mid)for(int p=k,q=i;q=mid;p+,q+)mergedtable.arrp=sourcetable.arrq;/把前一段复制至 到 mergedtableelsefor(int p=k,q=j;q=right;p+,q+)mergedtable.arrp=sourcetable.arrq;/把后一段复制至 到 mergedtabletemplate class typevoid sortlist:mergepass(sortlist&sourcetable,s

49、ortlist&mergedtable,const int len) int i=0;while(i+2*len=momentsize-l) 表示至少有个子序列merge(sourcetable,mergedtable,i,i+len-1,i+2*len-1);i+=2*len;if(i+len=momentsize-1)若只有最后两个子序列merge(sourcetable,mergedtable,i,i+len-1,momentsize-1);else/若只有最后一个子序列for(int j=i;j=momentsize-1;j+)mergedtable.arrj=sourcetable.

50、arrj;if(len=momentsize-1)if(cishumomentsize)cout第+cishu趟排序结果为:；for(int t=0;tmomentsize;t+)coutmergedtable.arrt;coutendl;template void sortlist:mergesort(sortlist & table )按数据元素关键字非递减的顺序对排序表table中数据元素进行递归排序sortlist temptable;int len=1;while(lenmomentsize)mergepass(table,temptable,len);len*=2;mergepas

51、s(temptable,table,len);len*=2;cishu=0;int main()/ 主函数/time_t timestart,timeend;double timeused;double timestart,timeend,timeused;int c=1;char ch;int n1=0;while(c!=0)coutendl;cout*coutendl;coutendl;coutcout1.直接插入排序2.冒泡排序endl;3.快速排序 4.归并排序endl;cout5.折半插入排序6简单选择排序7.堆排序0.退出排序程序endl;coutendl;coutendl;coutn请选择所需排序法：；cinch;if(ch=0)cout退出系统!=O&ch=7)coutn;cout