1035 插入与归并 (25 分)

#include<stdio.h>
int cmp(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;
}
int isInsertionSort(int a[101], int b[101], int N)
{
    int i, len, flag;
    for(i=N-1; i>=0; i--)
    {
        if(a[i] != b[i])
        {
            len = i;
            break;
        }
    }
    for(i=1; i<=len; i++)
    {
        if(b[i] < b[i-1])
        {
            flag = 0;
            break;
        }
        else
            flag = 1;
    }

    return flag;

}

void InsertionSort(int a[101], int b[101], int N)
{
    int i, flag;
    for(i=N-1; i>=0; i--)
    {
        if(a[i] != b[i])
        {
            flag = i;
            break;
        }
    }

    for(i=1; i<=flag+1; i++)
    {
        int j = i;
        int temp;
        while(j>0 && b[j] < b[j-1])
        {
            temp = b[j];
            b[j] = b[j-1];
            b[j-1] = temp;
            j--;
        }
    }
    printf("Insertion Sort\n");
    for(i=0; i<N; i++)
    {
        printf("%d", b[i]);
        if(i<N-1)
            printf(" ");
    }
    //printf("aaa");

}

void MergeSort(int b[101], int N)
{
    printf("Merge Sort\n");
    int i,j,k;
    int kuai=1, flag=0;
    for(i=0; i<N; i++)
    {
        kuai *=2;
        for(j=0; j<N; j=j+kuai)
        {
            for(k=0; k<kuai; k++)
            {
                if(b[k] < b[k-1])
                {
                    //kuai = kuai / 2;
                    flag = 1;
                    break;
                }
            }
            if(flag)
                break;
        }
        if(flag)
            break;
    }
    //printf("%d\n", kuai);
    kuai*=2;
    int x = N/kuai;
    for(i=0; i<x; i++)
        qsort(&b[i*kuai],kuai,sizeof(int),cmp);
    for(i=0; i<N; i++)
    {
        printf("%d", b[i]);
        if(i<N-1)
            printf(" ");
    }

}

int main()
{
    int N, i, flag;
    int a[101], b[101];
    char c[20];
    scanf("%d", &N);

    for(i=0; i<N; i++)
        scanf("%d", &a[i]);
    for(i=0; i<N; i++)
        scanf("%d", &b[i]);
    if(isInsertionSort(a, b, N))
        InsertionSort(a, b, N);
    else
        MergeSort(b, N);



}