算法导论第二章问题研究2

书上习题2-1 在合并排序中对小数组采用插入排序。以下是我写的代码：

//合并排序+插入排序结合法
#include <iostream>
#include <time.h>
using namespace std;
int* INSERTION_SORT(int A[],int B[],int p,int q,int r);
void MERGE(int A[],int p,int q,int r);
void MERGE_SORT(int A[],int p,int r,int k);
void main()
{
    clock_t start, finish;    
    int duration;     
    //测量一个事件持续的时间         
    start = clock(); 

    const int n=10;
    int a[n],i;
    srand( (unsigned)time( NULL ) );
    for( i=0;i<n;i++)
    {       
        a[i]=rand()%101;  
    }
    cout<<"排序前："<<endl;
    for ( i=0;i<n;i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;
    MERGE_SORT(a,0,n,2);//K值应该最大为此数组元素个数的一半。
    cout<<"排序后："<<endl;
    for ( i=0;i<n;i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;

    finish = clock();    
    duration = (int)(finish - start) / CLOCKS_PER_SEC;     
    printf( "%f seconds\n", duration );    
}
void MERGE(int A[],int p,int q,int r)
{
    int n1=q-p+1,n2=r-q,i,j,flag=-1;
    int *L=new int[n1];
    int *R=new int[n2];
    L=INSERTION_SORT(A,L,p,q,n1);
    R=INSERTION_SORT(A,R,q+1,r,n2);
    i=0;j=0;
    L[n1]=flag;
    R[n2]=flag;
    for (int k=p;k<=r;k++)
    {
        if (L[i]==flag)
        {
            A[k]=R[j];
            j++;
        }
        else if (R[j]==flag)
        {
            A[k]=L[i];
            i++;
        }
        else if (L[i]>=R[j])
        {
            A[k]=L[i];
            i++;
        }
        else 
        {
            A[k]=R[j];
            j++;
        }
    }
}
int *INSERTION_SORT(int A[],int B[],int p,int q,int r)
{
    int key;

    for (int i=p,j=0;i<=q,j<r;i++,j++)
    {
        B[j]=A[i];
    }
    for (j=2;j<=r;j++)
    {
        key=B[j-1];
        int i=j-1;
        while (i>0&&B[i-1]<key)//a[i-1]<key 变为降序排列
        {
            B[i]=B[i-1];
            i=i-1;
        }
        B[i]=key;
    }
    return B;
}
void MERGE_SORT(int A[],int p,int r,int k)
{
    int q=(p+r)/k;//q=(p+r)/k
    if((q-p+1)<=k)//子数组长度≤k的时候就不再进行划分，而是对该子数组进行插入排序    
    {             //当p=0时，有k<=r/k =>k<=√r kmax=√r kmin=2
       return;
    } 
    else
    {
        MERGE_SORT(A,p,q,k);
        MERGE_SORT(A,q+1,r,k);
        MERGE(A,p,q,r);
    }
}

a)插入排序时间复杂度O(n^2)对于长度为k的子列表都有O(k^2),则n/k个为(k^2)*n/k=O(nk)

b)由于有n/k个子列表，那么共有log(n/k)+1层。每一层的代价是O(n)，因此总共的时间复杂度为O(nlog(n/k))；

c).标准的合并算法时间复杂度为O(nlog(n))，要使修改后的算法具有与标准合并排序算法一样的渐进运行时间，k的最大渐进值是logn，原来时间复杂度为O(nk + nlog(n/k))，现在变为了O(nlogn + nlog(n/logn))，忽略nlog(n/logn)的影响，这样即为O(nlogn)；

d)在实践中，k的值应为：当p=0时，有k<=r/k  k<=√r  kmax=√r  kmin=2