加入
发新帖
发表于 2014-3-11 22:35 | 查看: 1344| 回复: 6
大家好久不见,因为学业比较忙消失了这么久。


今天我在代码测试的时候,发现使用C语言编写的快速排序速度远远达不上C++库函数中的sort函数。想请教一下C++库函数中sort函数的算法是怎样?
另外我在C中编写随机快排时出现编译成功却总是运行错误,是否是生成随机数需要某个库的支持?

收藏回复 显示全部楼层 道具 举报

发表于 2014-3-11 22:49
你点开库里看sort函数原代码不就知道它是怎么做的了,理论上快排的平均复杂度水平已达到比较算法的极限O(nlog2n),但要论最快也是要分场合,数据量小的时候快排还不如其他几种简单的排序。某些特定序列快排不如复杂度更低的计数排序等。而且快排也有优化与否的差距

回复 显示全部楼层 道具 举报

发表于 2014-3-11 23:13
wdytoya 发表于 2014-3-11 22:49
你点开库里看sort函数原代码不就知道它是怎么做的了,理论上快排的平均复杂度水平已达到比较算法的极限O(nl ...

我用的是在线代码测试平台,库函数在服务器。
据说随机快排在速度上有时可以超越快排,是不是得看人品?
另外我在Wikioi上测试代码时,C的快排所有数据都超时了,而C++的sort用时仅为C的十分之一,求解。

回复 显示全部楼层 道具 举报

发表于 2014-3-12 09:44
本帖最后由 Ruiner 于 2014-3-12 09:46 编辑

排序要看数据特征的,bucket sort平均线性时间 。另外你看下wikipedia上有说为什么std::sort比qsort快。
具体实现是与编译器相关的,而且有些实现是使用多种排序方式基于某种策略来选择的,不太可能是单纯的一种排序算法。

回复 显示全部楼层 道具 举报

发表于 2014-3-12 11:17
Terry 发表于 2014-3-11 23:13
我用的是在线代码测试平台,库函数在服务器。
据说随机快排在速度上有时可以超越快排,是不是得看人品? ...

没用过wikioi不了解,以前只用过一些高校的Online Judge平台,就算是在线的,库还是那些库,编译器一般也都是用的标准的,比如GCC,你去找找GCC或其他标准库的源码就好了,Online Judge平台上有让你选择你用什么库编译的,wikioi没用过不清楚

回复 显示全部楼层 道具 举报

发表于 2014-3-12 12:25
Ruiner 发表于 2014-3-12 09:44
排序要看数据特征的,bucket sort平均线性时间 。另外你看下wikipedia上有说为什么std::sort比qsort快。
...

维基被墙了,这是我在文库上找到的:
std::sort是一个改进版的qsort. std::sort函数优于qsort的一些特点:对大数组采取9项取样,更完全的三路划分算法,更细致的对不同数组大小采用不同方法排序。

大致就是基于qsort对数据进行特殊化处理,针对不同数据选择最优化解吧

回复 显示全部楼层 道具 举报

发表于 2014-4-9 18:10
光子计算机来临之时,世间万物的逻辑皆可采用穷举法解决,排个序算什么.......

回复 显示全部楼层 道具 举报

您需要登录后才可以回帖 登录 | 加入

搜索

繁體   

返回顶部