logo标签列表

std::sort是否改变相等元素的相对顺序？

c++stl
11

使用std::sort时，标准是否保证相等元素的顺序不会改变（哦，忘了这个术语），还是我需要考虑其他解决方案来实现这个目标？

答案是没有保证。如果您需要确保相等元素的顺序不变，则可以使用稳定排序算法，例如std::stable_sort。

6
鉴于存在stable_sort函数，我猜测回答是否需要自己实现排序函数为“否”。 - Éric Malenfant
5个回答
23

std::sort不保证稳定（你试图想到的术语）。正如你所猜测的，std::stable_sort保证是稳定的。std::stable_sort还提供了最坏情况下复杂度的保证，而std::sort则没有。然而，std::sort通常平均速度更快。

请注意，std::sort在平均情况下更快。 - Todd Gamblin
@Jerry 将此答案添加到该维基中（适当的位置）：http://stackoverflow.com/questions/1596139/hidden-features-and-dark-corners-of-stl - vehomzzz
我稍微扩展了一下，但希望没有让它变得非常无聊... - Jerry Coffin
3

来自C++参考文献：这里

相互比较相等的元素不能保证保持其原始相对顺序。

您可能想要使用stable_sort，但请注意它不如快速排序（平均情况下）。

好的，最好加上“average”关键字以避免混淆。 - Matthieu M.
指出此问题的评论可能已被删除，因此让我的评论处于未决状态，我无法真正删除它，因为这会让你的评论也被删除...嗯，好吧 :) - Matthieu M.
2

如果您需要保证排序稳定性，请使用 std::stable_sort。

2
2
你所描述的术语是“稳定性”。
从SGI的STL文档中:
注意: sort没有保证是稳定的。
如果需要，使用stable_sort。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接