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()。