免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 2729 | 回复: 2

[C++] list的sort是用什么方法如何实现的? 不是快速排序吧? [复制链接]

论坛徽章:
1
2015年迎新春徽章
日期:2015-03-04 09:58:11
发表于 2015-11-25 23:03 |显示全部楼层
20可用积分
std::sort作用于random_accessible的容器,而list不是,所以list有自己的排序算法。
问题是: std::sort使用的快速排序,或者stable_sort使用的归并排序,在迭代的过程中都需要划定一个分治的范围,也就是要有一个划分的点,对可以随机访问的容器而言是很容易了。而对于list而言,要找到某个分治点,总是要前向或者后向遍历才能找到,对吧。
这样一来岂不是常规的qsort/heap_sort算法对于std::list都没有效果了? std::list::sort内部到底是怎么实现的呢,效率又如何?
谢谢。

最佳答案

查看完整内容

先说效率吧。。。 标准要求是n*lgn的, 但没要求具体用什么算法。并且标准对效率的定义是按比较次数。。。 类似这样。。。BTW: algorithm里面的sort和stable_sort同样只要求效率达标, 并且后者必须是稳定的, 也不要求具体算法。so。。。 临时创建vector。。。 排序。。。 然后重新组合成list是不是也符合标准。。。?或者就向后遍历找划分点是不是也行。。。? 反正又没进行比较。。。libcxx(clang的实现)还真是这么干的。。。 ...

论坛徽章:
2
青铜圣斗士
日期:2015-11-26 06:15:59数据库技术版块每日发帖之星
日期:2016-07-24 06:20:00
发表于 2015-11-25 23:03 |显示全部楼层
asker160 发表于 2015-11-25 23:03
这样一来岂不是常规的qsort/heap_sort算法对于std::list都没有效果了? std::list::sort内部到底是怎么实现的呢,效率又如何?


先说效率吧。。。 标准要求是n*lgn的, 但没要求具体用什么算法。

并且标准对效率的定义是按比较次数。。。 类似这样。。。
Complexity: Approximately N log N comparisons, where N is distance(begin(), end()).


BTW: algorithm里面的sort和stable_sort同样只要求效率达标, 并且后者必须是稳定的, 也不要求具体算法。


so。。。  临时创建vector。。。 排序。。。 然后重新组合成list是不是也符合标准。。。?
或者就向后遍历找划分点是不是也行。。。? 反正又没进行比较。。。
libcxx(clang的实现)还真是这么干的。。。 我已经看到这样的代码了。。。
iterator __e1 = _VSTD::next(__f1, __n2);


有点失望。。。  标准要求得不够严。。。 于是libcxx还真钻了个空。。。


不过g++和msvc带的都没有这样偷懒。
C++模板有一个好处。。。  就是通常来说是能看到源代码的。。。  比如g++ -v,然后找list文件。。。  最终可以在bits/list.tcc里看到实现。

大概解释下。。。
有一个足够大的list数组(没有动态分配,就在栈上分配的一个不太大的数组), 把它想像成二进制数。 i号list要么是空,要么是长度为i^2的list。
然后将要排序的list里的元素一个一个移动到这个数组里面。 大致这样:

  1. 2^0   2^1   2^2 ...
  2. 0
  3. 1
  4. 0     1
  5. 1     1
  6. 0     0     1
复制代码
最开始初始状态全是长度为0的list。 即00000.....
从this移动一个元素到数组的0号list上。 于是就是1000.....
从this移动一个元素到数组的0号list上。  发生合并(进位), 得到一个长度为2的list放在数组的1号list上, 就是 01000...
从this移动一个元素到数组的0号list上。  得到11000...
从this移动一个元素到数组的0号list上。  合并两个长度为1的list, 放到1号list上, 此时再次合并两个长度为2的list, 得到长度为4的list, 放到3号list上。
就这样依次下去, 直到将this的元素移动完。
最后再全部合并到this。

这个数组大小只需要lg2(N)就够了。  对数级的。
32位上一个元素至少要12字节(2个指针+1个元素+padding)。 内存分配还可能会有一些利用不上的洞, 用户空间只有大概3G。
大小固定为32的栈上数组就够用了, 不需要动态内存分配。
64位上地址空间利用率更低。。。
大小为64的数组肯定也够用了。

合并次数。。。
长度为1的不超过N次, 长度为2的不超过N/2次, 长度为2^i的不超过N/2^i次。。。
每个位上都不超过N次比较, 最多lg2(N)位。
所以总体也能在N*lg(N)以内。
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

DTCC2020中国数据库技术大会 限时8.5折

【架构革新 高效可控】2020年8月17日~19日第十一届中国数据库技术大会将在北京隆重召开。

大会设置2大主会场,20+技术专场,将邀请超百位行业专家,重点围绕数据架构、AI与大数据、传统企业数据库实践和国产开源数据库等内容展开分享和探讨,为广大数据领域从业人士提供一场年度盛会和交流平台。

http://dtcc.it168.com


大会官网>>
  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP