免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 2520 | 回复: 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)以内。
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

SACC2019中国系统架构师大会

【数字转型 架构演进】SACC2019中国系统架构师大会,7折限时优惠重磅来袭!
2019年10月31日~11月2日第11届中国系统架构师大会(SACC2019)将在北京隆重召开。四大主线并行的演讲模式,1个主会场、20个技术专场、超千人参与的会议规模,100+来自互联网、金融、制造业、电商等领域的嘉宾阵容,将为广大参会者提供一场最具价值的技术交流盛会。

限时七折期:2019年8月31日前


----------------------------------------

大会官网>>
  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP