我想知道 std::sort 和 std::stable_sort 在功能、内存和硬件方面有何不同? documentation提到“将 [first,last) 范围内的元素按升序排序,如排序,但 stable_sort 保留具有等效值的元素的相对顺序。”,但这对我来说没有意义。什么是“相对顺序”和“等值”?
最佳答案
是的,就像你说的,这不是C++独有的概念。
稳定排序保留语义等值(value)的物理顺序。
The order of equal elements is not guaranteed to be preserved.
Complexity:O(N·log(N))
, whereN
=std::distance(first, last)
comparisons
The order of equal elements is guaranteed to be preserved.
Complexity:O(N·log^2(N))
, whereN
=std::distance(first, last)
applications ofcmp
. If additional memory is available, then the complexity isO(N·log(N))
.
这意味着 std::stable_sort
不能在执行时间方面非常有效地执行,除非“有额外的内存可用”,在这种情况下,它不会在以下方面有效地执行内存消耗。
关于c++ - std::sort 和 std::stable_sort 有什么区别?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23985891/