c++ - 许多对象彼此之间具有 "do-not-care"关系的情况的最佳排序算法

Question

我有一个不寻常的排序案例，我的谷歌搜索几乎没有出现。以下是参数:

1)随机访问容器。 (C++ vector )
2) 一般小 vector 尺寸(少于32个对象)
3) 许多对象彼此之间具有“无关”关系，但它们不 相等。 (即他们不关心它们中的哪一个首先出现在最终排序的 vector 中，但它们可能与其他对象进行不同的比较。)用第三种方式(如果仍然不清楚)，2个对象的比较函数可以返回3 个结果:“顺序正确”、“顺序需要翻转”或“不关心”。
4)平等是可能的，但将非常罕见。 (但这可能会像其他任何“无关紧要”一样被对待。
5) 比较运算符远比对象移动昂贵。
6)判断对象相互关心或不关心没有比较速度差异。 (也就是说，我不知道有什么方法可以进行更快速的比较，简单地说这两个对象是否关心彼此。)
7) 随机开始顺序。

Answer 1

无论您打算做什么，考虑到您的条件，我都会确保您制定一大堆测试用例(例如，获取一些数据集并将它们打乱几千次)，因为我认为这很容易选择无法满足您要求的排序。

“不关心”是棘手的，因为大多数排序算法都依赖于排序值的严格排序 - 如果 A“小于或等于”B，并且 B“小于或等于”C，则它假设 A 小于或等于 C——在您的情况下，如果 A“不关心”B 但确实关心 C，但 B 小于 C，那么您为 A-B 比较返回什么以确保A 将与 C 进行比较？

出于这个原因，而且它是小 vector ，我建议不要使用任何内置方法，因为我认为你会得到错误的答案，相反我会构建一个自定义插入排序。

从一个空的目标 vector 开始，插入第一个项目，然后为每个后续项目扫描数组以寻找可以插入的位置的边界(即忽略'不关心'，找到它必须去的最后一个项目并且第一个必须在前面)并将其插入该间隙的中间，沿目标 vector 移动其他所有内容(即它每次增长一个条目)。

[如果比较操作特别昂贵，你可能会更好地从中间开始并沿一个方向扫描直到你碰到一个边界，然后选择是否发现另一个边界是从那个边界移动，还是从中点移动。 .. 这可能会减少比较的次数，但是通过阅读您对您的要求所说的内容，您不能，比如说，使用二进制搜索来找到插入每个条目的正确位置]

是的，这基本上是 O(n^2)，但对于小型数组来说这应该无关紧要，您可以证明答案是正确的。然后您可以查看是否有任何其他种类做得更好，但除非您可以为任何给定的对返回正确的顺序，否则您将得到奇怪的结果...