有没有兴趣玩下排序算法
排序是基础算法，快排算法曾经是很多大公司的入职必考，现在很多编程语言的函数库把排序作为标准函数，大多程序员已经不需要自己写排序函数了。毫无疑问，经过多年发展，排序算法已经达到最优，基于比较型复杂度是O(nlogn)，非比较型的可达O(n)。好多编程民科总是自以为发明了宇宙无敌的排序算法，却不知道，你所想的别人早就做过了。
即使如此，排序算法作为入门算法，仍然有学习的必要，在个性表达上，仍然有优化加速的空间。
为了让大家直观地看到自己排序函数的优劣，我已经写好框架，各位只要在main函数前面按“void 函数名(double *,int)”的格式写好自己的排序函数，然后在main函数里的f数组中按格式“(int)函数名,函数说明,”顺序添加，程序就能自动执行你的排序函数，并最终指出你的排序速度是c qsort的多少倍（f数组0元素不要占用，它是专用于c qsort的）。
期待各位的优秀排序算法！
程序代码：#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define maxlen 10000000 //一千万个数据参与排序
struct sort_fun
{
int fun; //排序函数地址
char info[50]; //排序函数说明
};
int test_sort(double *a,int len)
{//本函数测试数组元素是否有序，有序返回true，无序则返回false
int i;
for(i=1;i<len&&a[i]>=a[i-1];i++); //测试是否为降序
if(i!=len)for(i=1;i<len&&a[i]<=a[i-1];i++); //不是降序则测试是否为升序
return i==len;
}
int cmpp(const void *a, const void *b)
{//c中qsort回调函数用的
double c, d;
c = *(double*)a;
d = *(double*)b;
return c>d?1:-1;
}
void c_qsort(double *a,int len)
{//c qsort函数
qsort(a, len, sizeof(double), cmpp);
}
void sort2(double *a, int n)
{//分治法排序
int i, j, k;
double *b;
if (n < 2)return;
sort2(a, n / 2);
sort2(a + n / 2, n - n / 2); //递归分段排序，也可不用递归，用循环完成分段。
b = (double *)malloc(sizeof(double)*n); //申请空间
for (i = k = 0, j = n / 2; i < n / 2 && j < n;)
{
if (a[i] < a[j])b[k++] = a[i++];
else b[k++] = a[j++];
}
for (; i < n / 2;)b[k++] = a[i++];
for (; j < n;)b[k++] = a[j++]; //两段有序数组合并，需要额外空间
for (i = 0; i < n; i++)a[i] = b[i]; //还原合并后的排序结果
free(b); //释放空间
}
void main()
{
struct sort_fun f[]=
{
(int)c_qsort," c qsort函数",
(int)sort2,"wmf2014分治法",
/*
下面可添加自定义排序函数
格式：(int)自定义排序函数名,排序算法说明(不超过50个字符),
*/
};
int i,j,k,m,n = maxlen;
double *aa,*bb;
void (*sort_f)(double *,int); //定义一个函数指针
aa=(double *)malloc(sizeof(double)*n);
bb=(double *)malloc(sizeof(double)*n);
for (i = 0; i < n; i++)
{
k = rand() % 10 < 5 ? -1 : 1;
aa[i]= k * (double)rand()*rand() / (rand() % 100000 + 15);
}
//生成maxlen个随机double数，aa是原始乱序数组，每次复制到bb中排序
printf("排序总数：%d个。\n",n);
for(i=0;i<sizeof(f)/sizeof(struct sort_fun);i++)
{
k=clock(); //开始计时
for(j=0;j<n;j++)bb[j]=aa[j]; //复制原始乱序数据到bb
sort_f=(void(*)(double *,int))f[i].fun; //强制转换为函数指针
sort_f(bb,n); //开始排序
if(!i)m=clock()-k;
printf("%s",f[i].info);
if(!test_sort(bb,n))printf(",排序错误");
else printf(",排序正确");
printf(",用时：%7d毫秒，速度是qsort的%.2f倍。\n",clock()-k,(double)m/(clock()-k));
}
free(aa);
free(bb);
system("pause");
}[此贴子已经被作者于2020-3-11 19:57编辑过]
？
