/* 归并排序实现 coder:QPZ time:2014-12-03 */ #include <time.h> #include <stdlib.h> #include <iostream> using namespace std; class Mergesort{ private: int *Arr; int n; public: Mergesort(int n){ this->n=n; srand((unsigned)time(NULL)); Arr=(int*)malloc(n*sizeof(int)); for(inti=0;i < n;i++){ Arr[i]=rand()%100; }/*endfor*/ } void Msort(int left,int right); void Merge(int left,int right,int rigntEnd); void PrinArr(); ~Mergesort(){ free(Arr); } }; int main(void) { intn; cin>>n; classMergesort *p=new Mergesort(n); p->PrinArr(); p->Msort(0,n-1); p->PrinArr(); return0; } void Mergesort::PrinArr() { for(inti=0;i<n;i++){ cout<<Arr[i]<<" "; }/*endfor*/ cout<<endl; } void Mergesort::Msort(int left,int right){ intmiddle; if(left<right){ middle=(left+right)/2; //分割数集 Msort(left,middle); Msort(middle+1,right); //归并操作 Merge(left,middle+1,right); } } void Mergesort::Merge(int left,int right,intrightEnd) { int*TmpArry=(int *)malloc((rightEnd-left+1)*sizeof(int)); inttmp; inti; intLeft=left; intRight=right; /*比大小赋值,结束后接*/ for(tmp=0;Left<right&& Right<=rightEnd;) { if(Arr[Left]<=Arr[Right]){ TmpArry[tmp++]=Arr[Left++]; } else{ TmpArry[tmp++]=Arr[Right++]; }/*end if else*/ }/*endfor*/ while(Left<right){ TmpArry[tmp++]=Arr[Left++]; } while(Right<rightEnd){ TmpArry[tmp++]=Arr[Right++]; } /*Tmp赋值返回*/ for(i=0,Left=left;i< tmp;i++){ Arr[Left++]=TmpArry[i]; }/*end for*/ free(TmpArry); }