| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 4737 人关注过本帖, 3 人收藏
标题:有没有兴趣玩下排序算法
只看楼主 加入收藏
wmf2014
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:216
帖 子:2039
专家分:11273
注 册:2014-12-6
收藏
得分:0 
2020/6/15 20:45更正:
二次排序由插入排序改成递归后,在桶数为排序总数0.5倍的情况下,排序速度比快排高,如果桶数增加到1倍,还可以提高,再增加桶数速度增加不明显,甚至有些倍数还降低了。
图片附件: 游客没有浏览图片的权限,请 登录注册

前两天在https://bbs.bccn.net/thread-501938-1-1.html参与了桶排序讨论,今天用代码实现了下,并把它合并到我的不同排序算法比较的代码中。
经过反复优化,发现桶排序虽然属于非比较类型排序,却没有什么优势,通过不断调整桶数,观察到当桶数是被排序数的4倍时,才勉强和c qsort的排序速度相当。
当然,我的算法并不是严格意义上的非比较排序,我在二次排序中用了插入排序。现在正考虑设计一个桶数据结构,让该算法可以使二次排序通过递归调用完成,也许能够提高些速度,预计可以达到分治法排序速度,大概是c qsort的1.4倍。
下图是设置不同桶数时排序速度的变化:
图片附件: 游客没有浏览图片的权限,请 登录注册

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

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

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


下面是我的桶排序代码,欢迎提供宝贵意见:
程序代码:
void sort7(double *a, int n)
{//桶排序
    const double k = 4;  //定义桶和排序总数的比例
    double *p, dmax, dmin, s;
    int *t, i, j, m, c = (int)(k*n) + 1;       //多设置一个桶,防止误差
    p = (double *)malloc(n * sizeof(double));  //预备一个空间辅助排序
    t = (int*)malloc(c * sizeof(int));         //预备一个空桶
    dmax = dmin = a[0];
    printf("  桶数量是待排序数据的%.2f倍\n", k);
    for (i = 0; i < n; i++)
    {//第一次扫描所有待排序数据,找出其中最大数和最小数,同时将数据转移到预备空间
        if (a[i] > dmax)dmax = a[i];
        if (a[i] < dmin)dmin = a[i];
        p[i] = a[i];
    }
    s = (dmax - dmin) / (double)(c - 1);       //得到每个桶容纳的数据范围基数
    if (s == 0)return;                         //如果基数为0说明待排序数据都相等,无需排序。(double数能否判断等于0,存疑)
    for (i = 0; i < c; i++)t[i] = 0;           //首先将每个桶归零置空
    //第二次扫描所有待排序数组,根据扫描到的数据计算其应该放到哪个桶中,对应桶数据加一。
    for (i = 0; i < n; i++)t[(int)((p[i] - dmin) / s)]++;
    for (i = j = 0; i < c; i++)
    {
        if (t[i])
        {
            j += t[i];
            t[i] = j;                          //确定每个桶的数据上边界位置
            if (j < n)a[j] = dmax + 1;         //上边界处填入不存在的最大数用于判断插入排序停止位置
        }
    }
    for (i = 0; i < n; i++)
    {//第三次扫描所有待排序数据,计算对应桶编号,用桶编号的位置数据作为下标放置待排序数据并执行插入排序
        m = (int)((p[i] - dmin) / s);
        if (t[m])
        {
            for (j = --t[m]; j<n-1&&p[i]>a[j + 1]; j++)
                a[j] = a[j + 1];
        }
        a[j] = p[i];
    }
    free(p);
    free(t);  //释放本函数申请过的内存
}


[此贴子已经被作者于2020-6-15 20:49编辑过]


能编个毛线衣吗?
2020-06-13 21:04
xianfajushi
Rank: 7Rank: 7Rank: 7
等 级:黑侠
威 望:8
帖 子:527
专家分:690
注 册:2007-9-8
收藏
得分:0 
有空闲的话测试一下,https://blog.
2020-10-08 17:21
xianfajushi
Rank: 7Rank: 7Rank: 7
等 级:黑侠
威 望:8
帖 子:527
专家分:690
注 册:2007-9-8
收藏
得分:0 
图片附件: 游客没有浏览图片的权限,请 登录注册
2020-10-09 11:46
wmf2014
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:216
帖 子:2039
专家分:11273
注 册:2014-12-6
收藏
得分:0 
回复 12楼 xianfajushi
不是vip用户,那个程序无法看全,粗看应该还有个循环调你那个定分直插函数的。
你自己可以和c函数库的qsort比较,如果能比他快,就很不错。
其实如果不是分治思想,就只是传统插入排序的改进,很难有根本的速度提高,估计排2000万个双精度数需要三天三夜。插入排序的改进版就是希尔排序,通过不断缩小插入排序间隔,使插入排序复杂度尽可能接近O(n),据测算,希尔排序最好能做到O(n^1.3)。
就单纯的排序速度提高上来说,最快的就是桶排序算法了(基数排序、计数排序都是桶排序的一种),在实数范围内排序基数排序最快,其次是桶排(你可以看我11楼的演示图,排2000万个double类型数,基排比qsort快近7倍,桶排也可做到2.5倍)。这类排序空间复杂度是O(n),空间换时间。

能编个毛线衣吗?
2020-10-09 14:18
xianfajushi
Rank: 7Rank: 7Rank: 7
等 级:黑侠
威 望:8
帖 子:527
专家分:690
注 册:2007-9-8
收藏
得分:0 
回复 14楼 wmf2014
谢谢!心血来潮由写折半查找萌发写了一个插入排序,目前步长为1如图片,也萌生了类似希尔的思路,克服插入排序长距离移动的短处,目前所写的这个算法从初测循环次数计算为(n*n)/3是最坏的情况,初测11111数据用时0.07秒左右,因此想听听高人的看法。

[此贴子已经被作者于2020-10-9 15:57编辑过]

2020-10-09 15:34
lin5161678
Rank: 12Rank: 12Rank: 12
等 级:贵宾
威 望:45
帖 子:1136
专家分:3729
注 册:2011-12-3
收藏
得分:0 
以下是引用xianfajushi在2020-10-9 15:34:09的发言:

谢谢!心血来潮由写折半查找萌发写了一个插入排序,目前步长为1如图片,也萌生了类似希尔的思路,克服插入排序长距离移动的短处,目前所写的这个算法从初测循环次数计算为(n*n)/3是最坏的情况,初测11111数据用时0.07秒左右,因此想听听高人的看法。

while (定 > 序)数组[定] = 数组[定-- - 1], ++记;
非常糟糕的做法
数组[定] = 数组[定-- - 1]
不可以这样写
这是未定义行为

https://zh.
2020-10-09 16:45
wmf2014
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:216
帖 子:2039
专家分:11273
注 册:2014-12-6
收藏
得分:0 
回复 15楼 xianfajushi
如果测试一万个int数就花了70毫秒,那我建议你的代码不要叫改进了,叫改退。普通的插入排序排11111个int数我只花0.043秒(测试电脑为惠普学生本,i5-4200u,主频1.60G,8G内存,win10 64位系统,很低档的)。测试排序算法速度,数据量不到一千万以上,没有测试意义,如果以复杂度O(n^2)来测试这个量的数据,我感觉用时是无穷大,反正我曾经等了三个钟头没有得到结果,只好终止了。我的插入排序代码如下,供你参考:
程序代码:
void sort_i(int *a, int n)  //n为排序数据总数
{//插入排序
    int i, j;
    int t;
    for (i = 1; i < n; i++)
    {
        t = a[i];
        for (j = i; j > 0 && t < a[j - 1]; j--)
            a[j] = a[j - 1];
        a[j] = t;
    }
}


[此贴子已经被作者于2020-10-9 19:24编辑过]


能编个毛线衣吗?
2020-10-09 19:01
xianfajushi
Rank: 7Rank: 7Rank: 7
等 级:黑侠
威 望:8
帖 子:527
专家分:690
注 册:2007-9-8
收藏
得分:0 
测试基本也在0.07秒左右
图片附件: 游客没有浏览图片的权限,请 登录注册
2020-10-10 09:41
xianfajushi
Rank: 7Rank: 7Rank: 7
等 级:黑侠
威 望:8
帖 子:527
专家分:690
注 册:2007-9-8
收藏
得分:0 
回复 16楼 lin5161678
错乱的疯言疯语
2020-10-10 09:48
lin5161678
Rank: 12Rank: 12Rank: 12
等 级:贵宾
威 望:45
帖 子:1136
专家分:3729
注 册:2011-12-3
收藏
得分:0 
以下是引用xianfajushi在2020-10-10 09:48:38的发言:

错乱的疯言疯语

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

可以看到 相同的代码输出结果
一个是 123456 一个是123356
输出结果是无法预期的
这就是我为什么说这是错误的原因

你不懂这点这很正常 这是C/C++比较琐碎的内容
但是你不懂 而我告诉你之后 你不好好学习 而是骂人
这就非常没礼貌没家教了

希望你好好学习 不要半桶水整天自作聪明

https://zh.
2020-10-10 11:09
快速回复:有没有兴趣玩下排序算法
数据加载中...
 
   



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

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