/*歸并排序：Mergesort.cpp*/

 

#include <iostream.h>

#include "stdio.h"

void inssort1(int A[],int n);

int time2=0;//時(shí)間復(fù)雜度

extern int time1;

void sort();

void mergesort(int A[],int temp[],int left,int right)

{     if((right-left)<=32)

       {

              inssort1(&A[left],right-left+1);//對(duì)于較小的數(shù)組，調(diào)用內(nèi)排序

              return;

       }

       int i,j,k,mid=(left+right)/2;

       if(left==right) return;

       mergesort(A,temp,left,mid);

       mergesort(A,temp,mid+1,right);

       for(i=mid;i>=left;i--)

       {

              temp[i]=A[i];

              time2++;

       }

       for(j=1;j<right-mid;j++)

       {

              temp[right-j+1]=A[j+mid];

              time2++;

       }

       for(i=left,j=right,k=left;k<=right;k++)

       {

              if(temp[i]<=temp[j])

              {

                     A[k]=temp[i++];

                     time2++;

              }

              else

              {

                     A[k]=temp[j--];

                     time2++;

              }

       }

 

 

}

 

void msort()

{

       int n,left,right;

       int time;

       int A[80];

       int B[80];

       int temp[80];

    cout <<"請(qǐng)輸入元素個(gè)數(shù)：" <<endl;

           cin >>n;

       left=0;

       right=n-1;

       cout <<"請(qǐng)輸入數(shù)組元素:" <<endl;

       for(int i=0;i<n;i++)

       {

              cin >>A[i];

       }

       for(int j=0;j<n;j++)

       {

              B[j]=A[j];

       }

       mergesort(A,temp,left,right);//進(jìn)行歸并排序

       cout <<"進(jìn)行排序后的結(jié)果:" <<endl;

       for(int k=0;k<n;k++)

       {

              cout <<A[k] <<" ";

       }

       cout <<endl;

       time=time1+time2;

       cout <<"時(shí)間復(fù)雜度為： ";

       cout <<time <<endl;

       char answer;

       cout <<"是否要打印排序前的數(shù)組?(y/n)" <<endl;

       cin >>answer;

       if(answer=='y')

       {

              for(int ii=0;ii<n;ii++)

                     cout <<B[ii] <<" ";

       }

       cout <<endl;

       getchar();

       sort();

}