algorithm - 对某些对未定义二进制排序函数返回的排序序列

Question

我正在做一些比赛。数学工作，我试图用复杂的数学排序谓词对序列进行排序，该谓词并不总是在序列中的两个元素之间定义。我正在尝试了解更多关于排序算法的知识，这些算法可以优雅地处理无法进行的逐元素比较，因为到目前为止我只管理了一种非常基本的方法。

^{如果这个问题是一些经典问题并且我需要一些时间来定义它，我很抱歉，算法设计不是我的强项。}

定义问题

假设我有一个序列 A = {a, b, c, d, e} .让我们定义 f(x,y)是一个返回 0 的二元函数如果x < y和 1如果y <= x ，通过应用一些复杂的排序标准。

在正常情况下，这将为我们提供足够的详细信息来排序 A . 但是，f也可以返回-1 ，如果排序标准没有明确定义该特定输入对。一对输入的未定义性是可交换的， ^即 f(q,r)未定义当且仅当 f(r,q)未定义。

我想尝试对序列 A 进行排序如果可能的话，使用定义明确的排序标准。

例如让我们假设

• f(a,d) = f(d,a)未定义。
• 所有其他输入对 f 定义明确。

然后尽管不知道 a 之间的不等式关系和 d , 我们将能够对 A 进行排序基于明确定义的排序标准只要 a和 d在生成的“已排序”序列中彼此不相邻。

例如，假设我们首先确定了 A - {d} 的相对排序成为{c, a, b, e} ，因为所有这些对 f定义明确。这实际上可以调用任何排序算法。

然后我们可以调用f(d,c) , 和

• 如果d < c我们完成了 - 排序后的序列确实是 {d, c, a, b, e} .
• 否则，我们移动到序列中的下一个元素，并尝试调用 f(a, d) .这是未定义的，所以我们不能建立d这个角度的位置。
• 然后我们调用f(d, e) , 并按元素从右向左移动。
  • 如果我们找到某个元素 x其中 d > x ， 我们完了。
  • 如果我们最终回到比较 f(a, d)再一次，我们已经确定我们不能根据我们拥有的明确定义的排序标准对序列进行排序。

问题

这些处理未定义比较对的排序算法是否有分类？

更好 虽然不是预期的，但是否有众所周知的“有效”方法？我已经定义了我自己的非常基本的蛮力算法来解决这个问题，但我确信它并不理想。

它实际上只是抛出所有遇到时无法比较的序列元素，如果有任何元素剩余，则对剩余的子序列进行排序，然后穷尽地尝试将所有与所有其他元素不可比较的序列元素放入已排序的子序列中.

只要有一条可以进一步研究该主题的途径就太好了——我缺乏算法方面的经验，因此一直在努力寻找我应该在哪里寻找更多关于此类问题的背景知识。

Answer 1

这非常接近 topological sorting ，你的二元关系是边缘。特别是，这只是 extending a partial order into a total order .天真地，如果你考虑使用拓扑排序的所有对(即 O(V+E))，你有一个最坏情况 O(n^2) 算法(实际上是 O(n+p)，其中 n 是元素的数量，p 是元素的数量可比对)。