c++ - `std::sort` 函数是否不稳定？

Question

只是想确认我的想法是对还是错。根据定义：

如果两个具有相同或相同键的对象在排序输出中出现的顺序与它们在要排序的输入数组中出现的顺序相同，则称该排序算法是稳定的。

现在在标准库的std::sort中，当两个元素相等时返回 false 是必须的。因此，可以肯定地说所使用的排序算法是不稳定的吗？

score 4 · Accepted Answer

现在在 STL 的排序函数中，当两个元素相等时返回 false 是必须的。因此，可以肯定地说所使用的排序算法是不稳定的吗？

不，这完全无关。

事实上，std::sort不能保证是稳定的；如果您需要稳定的排序，请使用std::stable_sort.

std::sort但是字符串弱排序要求是不相关的，并且对于和都是相同的std::stable_sort。

score 2 · Accepted Answer

std::sort()不能保证是稳定的，实际上它永远不会被实现为稳定的，因为稳定排序比较慢。如果您需要稳定的排序，请使用std::stable_sort().

score 2 · Accepted Answer

当两个元素相等时返回 false 是必须的。

这并没有区分稳定和不稳定的排序算法。

两种主要的标准排序算法是std::sort和std::stable_sort。第一个不保证是稳定的，后者是。两者都 require<或用作谓词的比较器来实现严格的弱排序（这意味着a < ais falsefor any a）。

score -2 · Accepted Answer

检查http://www.cplusplus.com/reference/algorithm/sort/上的 C++ 参考，这清楚地表明它不稳定

4 回答 4