对于许多对象彼此具有"不关心"关系的情况的最佳排序算法

Question

我有一个不寻常的分类案例,我的谷歌搜索已经发现很少.以下是参数:

1)随机访问容器.(C++向量)
2)通常小的向量大小(小于32个对象)
3)许多对象相对于彼此具有"不关心"关系,但它们不相等.(即他们并不关心它们中的哪一个首先出现在最终的排序向量中,但是它们可能与其他对象的比较不同.)换句话说(如果它仍然不清楚),2个对象的比较函数可以返回3结果:"订单正确","订单需要翻转"或"不关心".
4)平等是可能的,但是非常罕见.(但这可能只会被视为任何其他"不关心"
.5)比较运算符比对象运动要昂贵得多.
6)确定对象关心或不关心彼此没有比较速度差异.(即我不知道如何进行更快速的比较,简单地说明2个物体是否彼此关心不是.)
7)随机起始顺序.

Answer 1

你不能用“不关心”进行排序，它可能会打乱元素的顺序。例子：

list = {A, B, C};
where:
A dont care B
B > C
A < C

因此，即使 A 和 B 之间不关心，B 也必须大于 A，否则其中之一将为假：B > C 或 A < C。如果它永远不会发生，那么您需要将它们视为等于而不是不在乎。