mergesort.cpp

哈夫曼编码和译码 觉得自己有用的话就下把 我自己觉的还不错

#include <iostream.h>
#include "stdio.h"
void inssort1(int A[],int n);
int time2=0;//时间复杂度
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);//对于较小的数组，调用内排序
              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 <<"请输入元素个数：" <<endl;
           cin >>n;
       left=0;
       right=n-1;
       cout <<"请输入数组元素:" <<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);//进行归并排序
       cout <<"进行排序后的结果:" <<endl;
       for(int k=0;k<n;k++)
       {
              cout <<A[k] <<" ";
       }
       cout <<endl;
       time=time1+time2;
       cout <<"时间复杂度为： ";
       cout <<time <<endl;
       char answer;
       cout <<"是否要打印排序前的数组?(y/n)" <<endl;
       cin >>answer;
       if(answer=='y')
       {
              for(int ii=0;ii<n;ii++)
                     cout <<B[ii] <<" ";
       }
       cout <<endl;
       getchar();
       sort();
}