c++ - 你什么时候在标量上调用 stable_sort() ？

Question

stable_sort使用默认比较器调用而不是sort标量类型（即int,long等）是否很好？

如果是这样，你应该什么时候这样做？

如果不是，那么为什么标准库不直接将此类调用转发到sort？那不是更快吗？

Answer 1

只有当您正在排序的项目具有卫星信息时，稳定排序才真正有用。

---

来自 CLRS（算法简介，第 3 版）：

“实际上，要排序的数字很少是孤立的值。每个通常都是称为记录的数据集合的一部分。每个记录都包含一个键，这是要排序的值。记录的其余部分由卫星数据组成，通常与密钥一起携带。在实践中，当排序算法置换密钥时，它也必须置换卫星数据。

---

当排序稳定时，这意味着排序数组中的关系被项目的原始 ordering 打破。如果您只是排序int和long类型，则不需要稳定的排序。

Answer 2

应该没有区别（可能除了-0.0和0.0之类的东西）。但是我认为没有必要转发此类调用，因为 std::sort 或 std::stable_sort 不应该知道它们在排序什么，只要比较操作编译即可。这些功能不需要太聪明。

Answer 3

具体使用默认比较器（暗示自然严格排序）？在这种情况下，我认为对标量进行稳定排序没有任何用处。在等效值（根据比较器）无法区分的情况下，稳定排序无法提供任何额外的好处。（尽管@Andrey Tuganov 在他的回答中对负零做了一个有趣且相关的评论）。

然而，当排序标准弱于自然严格排序时，标量上的稳定排序可能很有用。例如，您可以编写一个比较谓词，表示任何奇数都大于任何偶数。在这种情况下，结果排序将简单地将数组划分为偶数和奇数的连续块（​​按该顺序）。如果您有兴趣保持这些数字的相对顺序不变，则需要稳定的排序算法。