| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
共有 1230 人关注过本帖, 2 人收藏
标题:有没有兴趣玩下排序算法
只看楼主 加入收藏
wmf2014
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:208
帖 子:2003
专家分:11148
注 册:2014-12-6
结帖率:100%
收藏(2)
 问题点数:0 回复次数:20 
有没有兴趣玩下排序算法
    排序是基础算法,快排算法曾经是很多大公司的入职必考,现在很多编程语言的函数库把排序作为标准函数,大多程序员已经不需要自己写排序函数了。
    毫无疑问,经过多年发展,排序算法已经达到最优,基于比较型复杂度是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编辑过]

附件: 游客没有浏览附件的权限,请 登录注册
搜索更多相关主题的帖子: 算法 函数 double 排序 int 
2020-03-11 15:33
yiyue123
Rank: 2
等 级:论坛游民
威 望:1
帖 子:78
专家分:78
注 册:2018-6-18
收藏
得分:0 
O(kn) 是什么意思?
2020-03-11 15:54
叶纤
Rank: 8Rank: 8
等 级:禁止访问
威 望:1
帖 子:658
专家分:848
注 册:2019-11-22
收藏
得分:0 
回复 2楼 yiyue123
大佬之间的较量,作为小白的咱们在这叫喧个啥,静静的跪拜就是小白的工作,
我先吱一声,吱吱《我是来回答你的问题的》
那个应该大概可能也许是空间时间复杂度吧?

把学习时间浪费在混坛上是傻瓜行为,更何况自己的水平连一两都没到。
2020-03-11 16:27
yiyue123
Rank: 2
等 级:论坛游民
威 望:1
帖 子:78
专家分:78
注 册:2018-6-18
收藏
得分:0 
哈哈哈,你说的有道理。
我还是想知道 k 是哪里来的,不过应该大概可能也许是误写吧
2020-03-12 09:23
wmf2014
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:208
帖 子:2003
专家分:11148
注 册:2014-12-6
收藏
得分:0 
回复 4楼 yiyue123
k取决于数据类型长度,如果是int、float是4个字节,最终要扫描四次,所以时间复杂度就是4n。
我设想的是把任何数据类型当做字节串用计数法排序(计数法复杂度是O(n)),还没想好怎么解决,好像仍然要用递归,空间复杂度不好控制,正负数及指数部分也不好安排排序(3/19 20:30更新:我的思路失败了,用时超过20秒,还排序错误。建议各位学习下松式基排,我的思路和这个类似。)。
今天添加了希尔排序,代码是拷贝别人的。
附各种排序时间空间复杂度表:




[此贴子已经被作者于2020-3-19 20:30编辑过]

附件: 游客没有浏览附件的权限,请 登录注册

能编个毛线衣吗?
2020-03-19 12:24
binthyrain
Rank: 1
等 级:新手上路
帖 子:16
专家分:9
注 册:2020-3-20
收藏
得分:0 
小白一个,不懂,现在在努力 学习,不过得支持大佬。
2020-03-20 13:21
wmf2014
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:208
帖 子:2003
专家分:11148
注 册:2014-12-6
收藏
得分:0 
我们这防控仍在继续,每天都要到执勤点做出入人员登记,测体温。希望疫情早日结束,各位都正常起来,该上学的上学,该挣钱的挣钱!
今天利用空余时间狠狠啃了下基排,下班后利用一下午的时间写了个通用类型基排函数(松式基排的变种),速度是c qsort的7倍,真的很快。如果不是写通用类型,只排正整数的话,速度可达qsort的25倍,排一千万个数也就300多毫秒,太快了!估计也就计数法排序可以比它快了。有了这个,玩排序也就此打住了,其他的什么桶排、堆排我也了解了下,在常规数据类型排序中肯定没有这个速度快。
基排的精髓就是乾坤大挪移,通过对数据各位计数,得到这个数据在该位上的排位,有几位就挪动该数几次,排序即完成,实在精妙!一般基排是10进制位排,松式基排是一个字节当做一位,也就是256进制排。通常基排只能排正整数,如果了解了IEEE754规范和有符号数规则,基排对负数和浮点数排序也是信手拈来,我写的这个函数可以排序所有常规类型数据。



我是通过反复看这个GIF动画学习基排的


附件: 游客没有浏览附件的权限,请 登录注册
收到的鲜花
  • 叶纤2020-03-21 20:47 送鲜花  5朵   附言:现在除了支持外,更多的是膜拜和

能编个毛线衣吗?
2020-03-21 20:42
yu1776151787
Rank: 2
等 级:论坛游民
威 望:1
帖 子:13
专家分:22
注 册:2020-2-22
收藏
得分:0 
回复 7楼 wmf2014
膜拜大佬您啊
2020-03-22 11:31
xianfajushi
Rank: 7Rank: 7Rank: 7
等 级:黑侠
威 望:7
帖 子:463
专家分:616
注 册:2007-9-8
收藏
得分:0 
计数排序法O(n)描述,我就觉得不对,首先要获得数组最大值要一遍数组,因此,说是O(2n)我觉得比较妥当。
2020-03-22 13:38
lin5161678
Rank: 12Rank: 12Rank: 12
等 级:贵宾
威 望:33
帖 子:1083
专家分:3403
注 册:2011-12-3
收藏
得分:0 
回复 9楼 xianfajushi
不管是O(2n)还是 O(0.0000001n) 还是O(10000n)
都叫做O(n)算法
首项系数忽略的

[此贴子已经被作者于2020-3-23 01:54编辑过]


https://zh.
2020-03-23 01:53
快速回复:有没有兴趣玩下排序算法
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.059683 second(s), 9 queries.
Copyright©2004-2020, BCCN.NET, All Rights Reserved