一亿个数，怎样排序才能用时最短
std::partial_sort - cppreference.com复杂度O(N*log2(N))，如果额外内存可用，那么复杂度O(N*log(N))正在测试。刚刚用我的渣电脑测了一亿个数，用了100秒。。现在换一台机器测，十亿，等结果Linux，CPU AMD X4955，3.2GHz，内存8G————————————代码：#include \u0026lt;iostream\u0026gt;#include \u0026lt;algorithm\u0026gt;#include \u0026lt;vector\u0026gt;#include \u0026lt;ctime\u0026gt;int main() { std::vector\u0026lt;int\u0026gt; v(1000000000); for (auto\u0026amp; it : v) it = rand(); clock_t start, finish; start = clock(); std::partial_sort(v.begin(), v.begin() + 100000000, v.end()); finish = clock(); std::cout \u0026lt;\u0026lt; static_cast\u0026lt;double\u0026gt;(finish - start) / CLOCKS_PER_SEC \u0026lt;\u0026lt; "s\";}结果出炉了：
等会。。我是不是看错题了？排前一亿个数？直接sort？
■网友
内存装得下的话，快排改成不在一亿范围的分区不进一步排序就行了。内存不够的话这事貌似得想想...
■网友
我知道的最好的算法是并行的归并排序。当然可能用gpu会更快吧。不太了解怎么用gpu，就不乱说了。
用我的渣船(4720HQ,2.7GHz,8线程,16g内存)，写了一段go对int数组排序，渣渣并行版本跑了6s多算完了。非并行版归并19s，理论上能快8倍，一定是因为我的程序没写好,恩。sort自带Sort需要29s,猜测可能是因为归并排序比快排空间局部性更好，能更好的利用缓存？
(当然也可能是我那个写错了。。。）
MIT 6.172 lec14
【一亿个数，怎样排序才能用时最短】 hgztheyoung/RandomShit
■网友
如果要求排序的前一亿个数有序的话，应该是堆排序（小根堆）。
推荐阅读
- 聪明人养花，这3种“花”怎样也要养一盆，每年能省不少医药费
- 支付■流水超一亿！姑苏警方重拳捣毁“四方支付”犯罪团伙
- 互联网怎样解决“家政服务上门速度慢”的问题
- 怎样看待从1月8号起，QQ钱包开始提现收费
- 银行it人怎样转型
- 汽车|冬天怎样让车内温度快速升高？座椅加热的最佳使用方式二，外循环的作用总结
- 怎样进入通信行业
- 怎样评价扶他柠檬茶的小说《云养汉》的结尾
- 怎样成为一名合格的Python程序员?
- 怎样评价华为、诺基亚、中兴中标中国移动高端路由交换设备扩容集采