C标准库中std::sort()的时间复杂度是多少？

Question

C++标准库中 std::sort() 的复杂度是多少？应用哪种类型？那里有应用任何特定排序算法的规则吗？

原文由 Hari Chaudhary 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

平均而言，第一个和最后一个之间的距离是线性的：对元素执行大约 N*log2(N) （其中 N 是这个距离）比较，并且最多执行许多元素交换（或移动）。

原文由 Ahmed Aunek 发布，翻译遵循 CC BY-SA 4.0 许可协议