有没有兴趣玩下排序算法
排序是基础算法,快排算法曾经是很多大公司的入职必考,现在很多编程语言的函数库把排序作为标准函数,大多程序员已经不需要自己写排序函数了。毫无疑问,经过多年发展,排序算法已经达到最优,基于比较型复杂度是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编辑过]