多种归并排序

多种归并排序 1、 问题 对一个数组进行排序，可以将之分解为n个已经排序的子问题，然后进行合并就可以得到了原问题的解。我们可以用分治法来解着这个问题。 通过对问题的分析，这个问题的解题符合分治法的条件: l 该问题的规模缩小到一定的程度就可以容易地解决; l 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质 l 利用该问题分解出的子问题的解可以合并为该问题的解; l 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 2、 根据问题分析，利用分治法解决问题的基本思路 分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题相同。递归的解这些子问题，然后将个子问题的解合并得到原问题的解。 分治法的基本: divide-and-conquer(P) { if ( | P | <= n0) adhoc(P); //解决小规模的问题 divide P into smaller subinstances P1,P2,...,Pk;//分解问题 for (i=1,i<=k,i++) yi=divide-and-conquer(Pi); //递归的解各子问题 return merge(y1,...,yk); //将各子问题的解合并为原问题的解 } 3、 算法设计 在这个问题中主要用到三个基本算法: 1、 把大的问题分解成小的问题:MergeSort; 2、 把两个较小的子问题合并成一个较大的问题:Merge; 3、 对已排序数组进行拷贝:Copy; 具体算法(C++语言): template void MergeSort(Type a[],int left,int right) { if(left void Merge(Type c[],Type d[],int left,int m,int right ) { int i=1eft, j=m+1; k=1eft; while((i<=m)&&(j<=right)) if(c[i]<=c[j]) d[k++]=c[i++]; else d[k++]=c[j++]; while(j<=right) d[k++]=c[j++]; while(i<=m) d[k++]=c[i++]; } template void Copy(Type a[],Type b[],int left,int right) { int i=left, for(;i<=right;i++) a[i++]=b[j++]; } 4、 算法的时间复杂度和空间复杂度分析 时间复杂度分析:Merge 和Copy 在 内可完成，因此合并排序算法对n 个元素进行排序，在 最坏的情况下所需的计算时间 满足: 解此递归方程可知 。由于排序问题的计算时间下界为 ，故合并排序算法是一个渐进最优算 法。 空间复杂度分析:在排序过程中需要与排序数组等长的数组来存放数组拷贝，所以空间复杂 度为: = ; 5、 算法实现 具体算法: #include #include #include using namespace std; template /* 为了便于维护，现在把排序封装在类ArraySort内 */ class ArraySort { private: int elem; //elem的值决定按升序还是降序 int len; //排序数组的长度 Type *b; //排序时用与交换的数组 Type *a; //用来存放要排序的数组; public: void set(Type c[],int k); //接收要排序的数组及数组长度 void Sort(); //进行排序 void MergeSort(int ,int ); void Merge(int ,int ,int); //进行合并 void Copy(int ,int); //复制一个数组到另一个数组 void ArPrint(); //输出数组元素 void ReturnCopy(Type c[]); //把已经排序数组返回给原数组 ~ArraySort(); ArraySort(int k=0){ elem=k; len=0; a=NULL; b=NULL; } }; template void ArraySort::set(Type c[],int k ) { int m; len=k; //len=c.length; a=new Type[len]; b=new Type[len]; if((a==NULL)||(b==NULL)) { cout<<"can't allocate more memory,terminating."<>m; if(m>=0&&m<=1) elem=m; else { cout<<"You input a illegal number!!"; cout<<" input the number 0 or 1:"< void ArraySort::Sort() { MergeSort(0,len-1); } template void ArraySort::Merge(int left,int m,int right) { int i=left, j=m+1, k=left; if(elem==0){ while((i<=m)&&(j<=right)) if(a[i]<=a[j]) b[k++]=a[i++]; else b[k++]=a[j++]; } else{ while((i<=m)&&(j<=right)) if(a[i]>=a[j]) b[k++]=a[i++]; else b[k++]=a[j++]; } while(i<=m) b[k++]=a[i++]; while(j<=right) b[k++]=a[j++]; } template void ArraySort::Copy(int left,int right) { for(int i=left;i<=right;i++) a[i]=b[i]; } template void ArraySort::ArPrint() { // int len=this.a.length; cout<<"The length of array is :"< void ArraySort::MergeSort(int left,int right) { if(left void ArraySort::ReturnCopy(Type c[]) { for(int i=0;i ArraySort::~ArraySort() { delete a; delete b; } void main() { //const int length=10; const int length=15; int i; // int c[length]={12,2,4,3,56,54,76,82,8,5}; int c[length]={1,9,3,4,6,78,15,34,56,0,74,14,10,21,49}; ArraySort as; as.set(c,length); cout<<"排序前的数组元素序列:"<