归并排序.cpp

五种排序算法

//归并
void Merge(int*a,int len1,int len2)
{
    int *a1=new int[len1+1],*a2=new int[len2+1],len=len1+len2;
    for (int i=0;i<len1;i++)
        a1[i]=a[i];
    for (int i=0;i<len2;i++)
        a2[i]=a[len1+i];
    a1[len1]=a2[len2]=INT_MAX;
    for (int i=0,j=0,k=0;k<len;k++)
        if (a1[i]<a2[j])a[k]=a1[i++];
        else a[k]=a2[j++];
    delete[] a1;delete[] a2;
}

//归并两有序数组a1,a2,结果放入a中
/*
template<typename T>
void Tmerge(T * a,T * a1,T * a2,T n1,T n2)
{
    int i=0,j=0,k=0;
    for(;k<n1+n2;k++)
    {
        if(i<n1&&j<n2)
        {
           if(a1[i]<=a2[j])
             a[k]=a1[i],i++;
           else
             a[k]=a2[j],j++;
        }
        else if(i<n1&&j>=n2)
            a[k]=a1[i],i++;
        else if(j<n1&&i>=n2)
            a[k]=a2[j],j++;
    }	
}
*/

//归并排序 分治思想 
void MergeSort(int*a,int len) //len表示数组的大小
{
    if (len>1)
    {
        int c=len/2;
        MergeSort(a,c);
        MergeSort(a+c,len-c);
        Merge(a,c,len-c);
    }
}

//二路归并排序
void Tmergesort(int * a,int size) 
{
    int i,j;
    for(i=1;i<size;i*=2)
    {
        for(j=0;j+2*i<=size;j=j+2*i)
           Merge(a+j,i,i);//归并长度为i的两个相邻串
        if(j+i-1<size)
           Merge(a+j,i,size-i-j);  
    }
}