然后把递归改成栈(测过快不了多少,甚至感觉还慢了那么一点点,看来相对递归来说用栈能提高运行效率还是要看具体情况的),加了比较函数封装,变成了和标准库函数qsort的形式~
但由于里面赋值改成memcpy这样调用函数要额外的开销,时间从9秒变成了18秒到21秒之间~
qsort稳定在25秒到27秒之间,比3楼的要快(如果按3楼的方法改写成10楼的形式,那相对而言还要快得多),比10楼的要慢,嗯,附上代码比对图片,算是这样了~
程序代码：
#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("");
}
图片附件: 游客没有浏览图片的权限，请
登录 或
注册
但意外地发现用手机测qsort是29秒,sort_merge是51秒感觉应该和编译器对底层基础的实现有关
~
图片附件: 游客没有浏览图片的权限，请
登录 或
注册
[此贴子已经被作者于2018-5-20 14:13编辑过]
