c++ - std::sort 和 std::stable_sort 有什么区别？

Question

我想知道 std::sort 和 std::stable_sort 在功能、内存和硬件方面有何不同？ documentation提到“将 [first,last) 范围内的元素按升序排序，如排序，但 stable_sort 保留具有等效值的元素的相对顺序。”，但这对我来说没有意义。什么是“相对顺序”和“等值”？

Answer 1

是的，就像你说的，这不是C++独有的概念。

稳定排序保留语义等值(value)的物理顺序。

---

std::sort :

The order of equal elements is not guaranteed to be preserved.
Complexity: O(N·log(N)), where N = std::distance(first, last) comparisons

std::stable_sort :

The order of equal elements is guaranteed to be preserved.
Complexity: O(N·log^2(N)), where N = std::distance(first, last) applications of cmp. If additional memory is available, then the complexity is O(N·log(N)).

这意味着 std::stable_sort 不能在执行时间方面非常有效地执行，除非“有额外的内存可用”，在这种情况下，它不会在以下方面有效地执行内存消耗。