Morn是一个C语言的基础工具和基础算法库，包括数据结构、图像处理、音频处理、机器学习等，具有简单、通用、高效的特点。
https://github.com/jingweizhanghuai/Morn
更快的排序是写算法的人永远的主题之一。之前写了各种排序，后来都删掉了，现在的Morn里只保留了快速排序。
接口
本文的相关函数源码在：https://github.com/jingweizhanghuai/Morn/blob/master/src/math/morn_sort.c
升序排序
void mAscSortD64(D64 *data_in,int *index_in,D64 *data_out,int *index_out,int num);
void mAscSortF32(F32 *data_in,int *index_in,F32 *data_out,int *index_out,int num);
void mAscSortS32(S32 *data_in,int *index_in,S32 *data_out,int *index_out,int num);
void mAscSortU32(U32 *data_in,int *index_in,U32 *data_out,int *index_out,int num);
void mAscSortS16(S16 *data_in,int *index_in,S16 *data_out,int *index_out,int num);
void mAscSortU16(U16 *data_in,int *index_in,U16 *data_out,int *index_out,int num);
void mAscSortS8(S8 *data_in,int *index_in,S8 *data_out,int *index_out,int num);
void mAscSortU8(U8 *data_in,int *index_in,U8 *data_out,int *index_out,int num);
或者，可以使用：
void mAscSort(Type,Type* data_in,int *index_in,Type *data_out,int *index_out,int num);</pre>
其中，Type只支持D64（double），F32（float），S32（int），U32（unsigned int），S16（short），U16（unsigned short），S8（signed char） ，U8（unsigned char）八种类型。
data_in是数据的输入（待排序数据），data_out是数据的输出（排序后数据）。
data_out可以等于data_in，也就是输出覆盖输入。
data_out若设为NULL，则取其默认值为data_in，也即默认覆盖输入。
index_in是输入数据的顺序，index_out是输出数据的顺序，如果两者都取NULL，表示排序时不记录顺序。
index_in若取NULL，则表示使用默认的递增顺序，即0，1，2，3，……，num-1的顺序。
index_out可以等于index_in，也就是输出覆盖原输入顺序。
index_out若取NULL，则取默认值index_in，也即覆盖原输入顺序。
num是数据的个数。
例如：
printf("in :");
for(int i=0;i<10;i++) {data[i] = mRand(-100,100);printf("%d,",data[i]);}
mAscSort(S32,data,NULL,NULL,index,10);
printf("\nout :");
for(int i=0;i<10;i++) {printf("%d(%d),",data[i],index[i]);}</pre>
其运行结果为
in :5,45,-19,-73,61,-9,95,42,-73,-64,
out :-73(8),-73(3),-64(9),-19(2),-9(5),5(0),42(7),45(1),61(4),95(6),</pre>
降序排序
void mDescSortD64(D64 *data_in,int *index_in,D64 *data_out,int *index_out,int num);
void mDescSortF32(F32 *data_in,int *index_in,F32 *data_out,int *index_out,int num);
void mDescSortS32(S32 *data_in,int *index_in,S32 *data_out,int *index_out,int num);
void mDescSortU32(U32 *data_in,int *index_in,U32 *data_out,int *index_out,int num);
void mDescSortS16(S16 *data_in,int *index_in,S16 *data_out,int *index_out,int num);
void mDescSortU16(U16 *data_in,int *index_in,U16 *data_out,int *index_out,int num);
void mDescSortS8(S8 *data_in,int *index_in,S8 *data_out,int *index_out,int num);
void mDescSortU8(U8 *data_in,int *index_in,U8 *data_out,int *index_out,int num);
或者，可以用：
void mDescSort(Type,Type* data_in,int *index_in,Type *data_out,int *index_out,int num);</pre>
其参数与mAscSort相同，不再赘述。
例如：
printf("in :");
for(int i=0;i<10;i++) {data[i] = mRand(-100,100);printf("%d,",data[i]);}
mDescSort(S32,data,NULL,NULL,NULL,10);
printf( "\nout :");
for(int i=0;i<10;i++) {printf("%d,",data[i]);}</pre>
其运行结果为
in :91,-96,2,53,-8,82,-79,16,18,-5,
out :91,82,53,18,16,2,-5,-8,-79,-96,
性能
这里，把Morn的排序与C语言标准库函数里的qsort函数排序进行了性能对比。
int *data1=mMalloc(n*sizeof(int));
int *data2=mMalloc(n*sizeof(int));
for(int i=0;i<n;i++) {data1[i] = mRand(0-n,n);data2[i]=data1[i];}
printf("S32 qsort(num %d):\n",n);
int compare(const void *v1, const void *v2) {return ((*((int *)v1))-(*((int *)v2)));}
mTimerBegin();
qsort(data1,n,sizeof(int),compare);
mTimerEnd();
printf("S32 Morn sort(num %d):\n",n);
mTimerBegin();
mAscSort(S32,data2,NULL,NULL,NULL,n);
mTimerEnd();
mFree(data1);
mFree(data2);
其运行结果如下：
排序.PNG
这里比较了32位整数和64位浮点数的性能，测试的数据都是1000000个，可以看到Morn的排序比qsort明显更快。（这么比有一点儿不公平，qsort使用回调函数排序，虽然慢，但是有更广泛的应用。不过，如果你需要的只是数值排序，可能Morn是更好的选择）。
Morn：写C语言！快点！简单点！
https://github.com/jingweizhanghuai/Morn
网友评论