//                             merge sort in C++//                         并归排序算法和优化后的算法//作者：Andyhou#include <iostream>using namespace std; const int THRESHOLD=9;class intCompare{public: static bool it(int x,int y) {  return x<y; } static bool gt(int x,int y) {  return x>y; } static bool eq(int x,int y) {  return x==y; }}; template<class Elem,class Compare>class Merge{private: Elem* array; int arraySize; void inssort(Elem A[],int n); void swap(Elem A[],int i,int j);public: void mergesort1(Elem A[],Elem temp[],int left,int right); void mergesort2(Elem A[],Elem temp[],int left,int right); void print(Elem A[],int n);}; template<class Elem,class Compare>void Merge<Elem,Compare>::inssort(Elem array[],int n){ for(int i=1;i<n;i++)  for(int j=0;j<=i;j++)  {   if(Compare::gt(array[i],array[j]))     swap(array,i,j);  }} template<class Elem,class Compare>void Merge<Elem,Compare>::swap(Elem A[],int i,int j){ int temp=A[i]; A[i]=A[j]; A[j]=temp;} template<class Elem,class Compare>void Merge<Elem,Compare>::print(Elem A[],int n){ cout<<"Print all number: "; for(int i=0;i<n;i++)  cout<<A[i]<<"  "; cout<<endl;} //一般的并归算法。template<class Elem,class Compare>void Merge<Elem,Compare>::mergesort1(Elem A[],Elem temp[],int left,int right){ int mid=(left+right)/2; if(left==right) return; mergesort1(A,temp,left,mid); mergesort1(A,temp,mid+1,right); for(int i=left;i<=right;i++)  temp[i]=A[i]; int i1=left; int i2=mid+1; for(int curr=left;curr<=right;curr++) {  if(i1==mid+1)   A[curr]=temp[i2++];  else if(i2>right)   A[curr]=temp[i1++];  else if(Compare::it(temp[i1],temp[i2]))   A[curr]=temp[i1++];  else   A[curr]=temp[i2++]; }}//优化后的并归排序算法template<class Elem,class Compare>void Merge<Elem,Compare>::mergesort2(Elem A[],Elem temp[],int left,int right){  if((right-left+1)<=THRESHOLD)//过小的排序可以采用插入排序较为理想。 {  inssort(&A[left],right-left+1);  return ; } int i,j,k,mid=(right+left)/2; if(left==right) return; mergesort2(A,temp,left,mid); mergesort2(A,temp,mid+1,right); for(i=mid;i>=left;i--)  temp[i]=A[i]; for(j=1;j<=right-mid;j++)   //从两头向中间靠省去判断没有比完的元素。  temp[right-j+1]=A[j+mid]; for(i=left,j=right,k=left;k<=right;k++) {  if(Compare::gt(temp[i],temp[j]))   A[k]=temp[i++];  else   A[k]=temp[j--]; }} int main(){ Merge<int,intCompare> A; int n; int tempA[50]; cout<<"Enter the sum of number!"; cin>>n; int* Array=new int[n]; for(int i=0;i<n;i++)  cin>>Array[i]; A.print(Array,n); A.mergesort1(Array,tempA,0,n-1); A.print(Array,n); A.mergesort2(Array,tempA,0,n-1); A.print(Array,n); delete[] Array; return 0;} 注：              这是并归算法和优化后的算法实现。  

评论