分治算法-归并排序

《分治算法-归并排序》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验报告格式如下：实验[1][归并排序]专业　　　　学号　姓名　　　　　　日期1实验目的可以利用分治算法来解决排序问题2实验内容将n个元素排成非递减顺序的序列，主要步骤是若n=1则排序终止，否则将这列元素分割成两个或是更多的子集3算法设计首先判断元素的个数，若果只有一个元素，则排序完成，如果元素的个数大于一，则进行下一步，如果给的所有元素后一项都大于前一项，或是前一项都大于后一项则排序完成，都则进行归并排序。就以二路归并为例，首先把所有元素分成大致元素个数相等的两个子集，把已经分好的在进行分，直至不能分为止，然后进行归并，两个元素分成一组，归并是把大的元素放在右边，在对已经归并的元素在进行归

2、并，直至完成排序4程序代码列出你用于实验过程中所使用的程序，必须能运行，并得到你所给出的计算结果。#include#include//这个函数将b[0]至b[right-left+1]拷贝到a[left]至a[right]templatevoidCopy(Ta[],Tb[],intleft,intright){intsize=right-left+1;for(inti=0;i

3、atevoidMerge(Ta[],Tb[],intleft,inti,intright){inta1cout=left,//指向第一个数组开头a1end=i,//指向第一个数组结尾a2cout=i+1,//指向第二个数组开头a2end=right,//指向第二个数组结尾bcout=0;//指向b中的元素for(intj=0;ja1end){b[bcout++]=a[a2cout++];continue;}//如果第一个数组结束，拷贝第二个数组的元素到bif(a2cout>a2en

4、d){b[bcout++]=a[a1cout++];continue;}//如果第二个数组结束，拷贝第一个数组的元素到bif(a[a1cout]voidMergeSort(Ta[],intleft,intright){T*b=newint[right-left+1];if(left

5、){inti=(left+right)/2;//取中点MergeSort(a,left,i);//左半边进行合并排序MergeSort(a,i+1,right);//右半边进行合并排序Merge(a,b,left,i,right);//左右合并到b中Copy(a,b,left,right);//从b拷贝回来}}intmain(){intn;cout<<"要给多少个数据排序:";cin>>n;int*a=newint[n];cout<<"请输入数据";for(inti=0;i>a[i];}MergeSort(a,0,n-1);//调用排序for

6、(intj=0;j