昂贵比较的排序算法

Question

给定一个包含 n 个不同对象（非整数）的数组，其中 n 在 5 和 15 之间。我有一个比较函数 cmp(a, b)，如果 a < b 则返回 true，否则返回 false，但调用此函数非常昂贵。我正在寻找具有以下特性的排序算法：

• 算法应尽可能少地调用 cmp(a, b)（在以下约束条件的前提下）。不能并行或替换调用 cmp(a, b)。成本是不可避免的，即将每次调用 cmp(a, b) 看作花费的金钱。

• 中止算法应该给出足够好的结果（最适合对数组排序）。理想情况下，算法应该尝试产生整个数组的粗略顺序，而不是一次部分地排序子集。这可能意味着总调用次数不像理论上可能那么小，以便对整个数组进行排序。

• cmp(a, b) 意味着 not cmp(b, a) => 数组中没有相等的项 => 不需要稳定性。这总是正确的，除非...

• 在罕见情况下，cmp(a, b) 违反了传递性。现在我会忽略这一点，但最终我也希望能够处理这个问题。传递性可能会在短链中被违反，即 x < y < z < x，但在较长的链中不会被违反。在这种情况下，x y z 的最终顺序并不重要。

只需要优化对cmp()的调用次数；算法复杂度、空间、速度和其他因素都不相关。

背景故事

有人问这个奇怪的问题是从哪里来的。尽管我尝试过正式化，但实际上这个问题根本不正式。一段时间以前，我的一个朋友在互联网上找到了一个网页，可以让他将一些东西放入列表中，并对该列表进行比较以使其排序。后来他失去了那个网页，并向我求助。我说当然可以，并打出了this implemtation。你可以查看源代码，看看我是如何假装解决上述问题的。由于当时我喝醉了，所以决定将真正的思考外包给堆栈溢出。

- Gleno

---

cmp是否存在货币精度权衡？能否获得可能性分数而不是真或假？您的模型没有问题，但有一些相关模型的文献。 - David Eisenstat

在这个模型中，假设传递性并忽略中止的可能性，你所能做的最好的事情是一个用于排序的最优决策树，对于小的n应该是已知的，也许不超过15，因为它们可能无法简洁地说明。 - David Eisenstat

“sorted”这个词在非传递性的“顺序”中到底意味着什么？你是指希望在这种情况下邻近元素看起来像已经排序好了吗？ - user2357112

什么是“n个尺寸为n的不同对象”？ - Codor

我尝试解决类似的问题：从比较中创建一个图形，不显示已经完成比较的比较，最后进行拓扑排序。 - Absurd-Mind

Answer 1

你最好从Knuth的TAOCP第三卷的第5章开始学习，它是关于最优排序（即使用最少的比较）的。然而，由于你要排序的对象数量非常小，我怀疑在最优算法和冒泡排序之间不会有任何明显的差异。因此，也许你需要专注于降低比较的成本。不过这个问题很奇怪...你介意提供一些细节吗？它出现在哪里？

- user1666959

---

我想我应该更具体一些。我已经在我的问题中添加了一个琐事部分，详细展示了我的思考过程。 ;) - Gleno