用归并法对数组排序

#include<stdio.h>

#include<stdlib.h>

#include<stdarg.h>

#include<time.h>

typedef void (*SORT_FUN)( void*,size_t,size_t,int (*)( const void*,const void* ) );

void sort_test( SORT_FUN );

int comp( const void*,const void* );    //比较函数

void init_srand( long* );

void test1( size_t,SORT_FUN,... );

void test2( size_t,unsigned,SORT_FUN );

void test3( unsigned,unsigned,unsigned,SORT_FUN );

void check( int*,size_t );

void merge_sort( void*,size_t,size_t,int (*)( const void*,const void* ) );

static void _merge( char*,const char*,const char*,const char*,size_t,\

                   int (*)( const void*,const void* ));

void print( const int [],size_t size );

int main( void )

{    

    puts("Test qsort:\n");

    sort_test(qsort);

    puts("\nTest merge_sort:\n");

    sort_test(merge_sort);

    getchar();

    return 0;

}

int comp( const void* p,const void* q )

{

    return *( int* )p-*( int* )q;

}

void sort_test( SORT_FUN sort_fun )

{

    size_t i;

    time_t start;

    init_srand(NULL);

    start=time(NULL);

    test1(1,sort_fun,0);        //测试1个数

    test1(2,sort_fun,1,2);    //测试顺序两个数

    test1(2,sort_fun,2,1);    //测试逆序两个数

    test1(5,sort_fun,1,1,1,1,1);    //测试输入重复数

    test1(5,sort_fun,1,2,3,4,5);    //测试顺序5个数

    test1(5,sort_fun,5,4,3,2,1);    //测试逆序5个数

    test1(5,sort_fun,1,2,1,1,2);    //测试重复数

    test1(5,sort_fun,3,2,1,5,4);    //测试一般序列

    test1(5,sort_fun,-3,-2,-1,-5,-4);    //测试负数

    puts("ACROSS TEST1"); 

    for (i=1;i!=10001;++i)  //从1个数据到10000个数据每个数据段覆盖1次

        test2(i,1,sort_fun);

    puts("ACROSS TEST2");

    test3(1,1000000,10,sort_fun);  //随机产生1~1000000元素个数,测试10次

    puts("ACROSS TEST3");

    printf("The test of time is %g s\n",difftime(time(NULL),start));

}

void init_srand( long* data )

{

    srand(( unsigned )time(data));

}

#include<string.h>

#include<assert.h>

void test1( size_t len,SORT_FUN sort_fun,... )

{

    va_list ap;

    int* a=( int* )malloc(len*sizeof (*a));

    size_t i;

    assert(a);

    va_start(ap,sort_fun);

    for (i=0;i!=len;++i)

        a[i]=va_arg(ap,int);

    va_end(ap);

    sort_fun(a,len,sizeof (int),comp);

    check(a,len);    //检查数据是否存在bug

    free(a);

}

void test2( size_t len,unsigned count,SORT_FUN sort_fun )

{   

    int* buf=( int* )malloc(len*sizeof (*buf));

    assert(buf);

    do

    {

        size_t i;

        for (i=0;i!=len;++i)

            buf[i]=rand()%100;

        sort_fun(buf,len,sizeof (int),comp);

        check(buf,len);    //检查数据是否存在bug

    }while (--count);

    free(buf);

}

void test3( unsigned low,unsigned height,unsigned count,SORT_FUN sort_fun )

{

    size_t i;

    if (low>height)

    {

        fprintf(stderr,"TEST3 DATA RANGE ERROR\n");

        exit(EXIT_FAILURE);

    }

    for (i=0;i!=count;++i)

    {

        const size_t len=rand()%(height-low+1)+low;

        test2(len,1,sort_fun);

    }

}

void check( int* a,size_t len )

{

    size_t i;

    if (len<2)

        return ;

    for (i=0;i!=len-1;++i)

        assert(a[i]<=a[i+1]);

}

typedef struct Stack

{

       size_t low;

    size_t height;

    unsigned deep;

       int flag; 

}Stack,*P_Stack;

#include<math.h>

void merge_sort( void* _a,size_t size,size_t n_size,int (*comp)( const void*,const void* ) )

{   

    char* buf=NULL;

    char* a=( char* )_a;

    P_Stack stack=NULL;

    P_Stack base=NULL;

    P_Stack top=NULL;

    if (size==0)

        return ;

    buf=( char* )malloc(size*n_size);

    assert(buf);

    memcpy(buf,a,size*n_size);

    base=stack=( P_Stack )malloc(( size_t )(log(size)+10)*sizeof (Stack));

    assert(stack);

    stack->flag=0; 

    top=base+1;   

    top->low=0;

    top->height=size;

    top->deep=1;

    top->flag=0;

#define __STACK_PUSH( top,_low,_height )    \

    do    \

    {    \

        ((top)+1)->low=(_low);    \

        ((top)+1)->height=(_height);    \

        ((top)+1)->deep=(top)->deep+1;    \

        ((top)+1)->flag=0;    \

        ++(top);    \

    }while (0);

#define __STACK_POP( top )    \

    do    \

    {    \

        --(top);    \

        ++(top)->flag;    \

    }while (0);

    while (top!=base)

    {

        const size_t low=top->low;

        const size_t mid=(top->low+top->height)/2;

        const size_t height=top->height;

        if (low==height-1)

        {

            __STACK_POP(top);

            continue;

        }

        if (top->flag==0)

        {

            __STACK_PUSH(top,low,mid);

            continue;

        }

        if (top->flag==1)

        {

            __STACK_PUSH(top,mid,height);

            continue;

        }

        if (top->deep&1)

            _merge(a+low*n_size,buf+low*n_size,buf+mid*n_size,buf+height*n_size,n_size,comp);

        else

            _merge(buf+low*n_size,a+low*n_size,a+mid*n_size,a+height*n_size,n_size,comp);

        __STACK_POP(top);

    }

    free(buf);

#undef __STACK_PUSH

#undef __STACK_POP

}

static void _merge( char* buf,const char* p,const char* q,const char* p_height,size_t n_size,\

                   int (*comp)( const void*,const void* ) )

{

    const char* const p_mid=q;

    char* p_buf=buf;

    while ((p!=p_mid)&&(q!=p_height))

        if (comp(p,q)>0)

        {

            memcpy(p_buf,q,n_size);

            p_buf+=n_size;

            q+=n_size;

        }

        else

        {

            memcpy(p_buf,p,n_size);

            p_buf+=n_size;

            p+=n_size;

        }

     if (p!=p_mid)

           memcpy(p_buf,p,p_mid-p);

        else

           memcpy(p_buf,q,p_height-q);

}

void print( const int a[],size_t size )

{

    size_t i;

    for (i=0;i!=size;++i)

        printf("%-4d",a[i]);

    puts("");

}