C++ stable_sort(STL stable_sort)排序算法详解

sort() 算法可能会改变相等元素的顺序，有时候这不是我们想要的。假设有一个保存某种事务的容器，或许是银行账户。进一步假设，在处理它们之前，为了能够有序更新这些账户，需要按照账号对这些事务排序。如果出现相等事务的顺序反映的是它们添加到容器的时间顺序，就需要维持这个顺序不变。如果允许对给定账户的事务进行重新排列，可能会出现透支的情况。

这种情况下，stable_sort() 算法可以满足我们的要求，它会对一段元素进行排序并保证维持相等元素的原始顺这里有两个版本：其中一个接受两个用来指定排序元素范围的迭代器，另一个接受用于比较的额外参数。

为了演示 stable_sort() 的使用，可以对上一节中的 names 容器进行排序的语句进行修改：

std::stable_sort(std::begin(names), std::end(names),[](const Name& name1, const Name& name2) { return name1.get_second() < name2.get_second(); });

当然，上一节中使用 sort() 的输出并没有打乱相等元素的顺序，所以使用 stable_sort() 并不会改变相同输入的输出。它们的不同之处在于，stable_sort() 保证不会改变相等元素的顺序，这是 sort() 算法所不能保证的。当需要使相等元素的顺序保持不变时，应该使用 stable_sort()。

关注公众号「站长严长生」，在手机上阅读所有教程，随时随地都能学习。本公众号由站长亲自运营，长期更新，坚持原创，专注于分享创业故事+学习历程+工作记录+生活日常+编程资料。

微信扫码关注公众号