TL;DR: 可以修改快速排序算法，以获得以下保证：在期望时间O(n log n)内，我们可以根据翻转的比较之一执行以下操作之一。
- 完美地对数组进行排序。
- 完美地对数组进行排序，除了在数组中某个位置交换了相邻的一对项。
- 完美地对数组进行排序，除了将可以识别的数组中的三个连续项置换了位置。
这保证了最大位移量为2，这是理论上可能的最好结果。
我思考了几个小时这个问题，发现我的所有操作都与
tournaments相关。
首先，我想尝试重新构思这个问题。如果你有一组n个项目，并且你知道它们之间的“真实”比较结果，你可以将该结果表示为一个有向图，每个节点代表一个项目，边表示一个项目比另一个项目小的情况。这种类型的有向图称为“锦标赛”，因为你可以将其视为编码循环赛的结果，每个选手都与其他选手比赛。
在诚实比较器的情况下，我们的锦标赛将是无环的，特别地，它将具有以下关键属性：每个出度为0、1、2、...、n-1的节点都恰好有一个。这里的想法是最小元素的出度为n-1（它比其他所有元素都小），而最大元素的出度为0（它比其他所有元素都大）。事实上，有一个定理：如果锦标赛中的每个节点具有不同的出度，则锦标赛是无环的。另一个有用的事实是：在无环锦标赛中，从U到V存在一条边，当且仅当outdeg(U)>outdeg(V)。
在“不诚实的比较器”的情况下，我们基本上从一个无环锦标赛开始，然后翻转一条边。您的问题是关于基于此比较器进行近似排序，但我想退后一步，问一个不同的问题，我认为这个问题可以更精确地回答您的问题。在哪些情况下可以确定翻转了哪条边？如果我们能做到这一点，那么我们甚至可以比近似排序更好地“取消翻转”边缘并完美排序。另一方面，在哪些情况下无法确定翻转了哪条边，当发生这种情况时，我们离排序有多远？这对应于必须进行近似排序，因为我们无法恢复原始排序。
以下是一个有用的事实：
定理：从一个无环锦标赛开始，翻转一条边。然后当且仅当翻转边缘的两个端点的出度最初相差至少三个时，可以确定翻转的边。
为了证明这一点，我们将展示蕴含的两个方向。
首先，假设我们翻转两个节点X和Y之间的边，它们的出度相差一。完成后，我们得到了一个锦标赛，其中所有节点的出度不同（所有其他节点的出度保持不变，如果我们翻转了边（X，Y），那么X和Y交换出度，因为一个增加了一个，一个减少了一个）。现在我们留下了另一个无环锦标赛。特别地，我们无法确定我们翻转了哪条边，因为我们可能翻转任何一对出度相差一的节点之间的任何一条边。
接下来，假设我们在节点X和Y之间翻转一条边，其中outdeg（X）= k + 1且outdeg（Y）= k-1。现在，我们有outdeg（X）= k = outdeg（Y），并且在另一个地方，必须有一些具有k的出度的节点Z。因此，在这一点上，我们有三个出度为k的节点（即X，Y和Z），而且我们知道我们必须翻转它们之间的三条边中的一条。但是我们无法确定它是哪一个。具体而言，翻转XY边或XZ边或YZ边都会产生无环锦标赛。因此，在这种情况下，没有办法撤消变换。这意味着我们从此比较器获得的任何排序顺序都将使这两个项目不合适，因此我们至少会有最大距离为1。
对于这种特殊情况的重要说明：这对应于比较器创建一个包含节点X、Y和Z的恰好一个循环的锦标赛。具体而言，它将采用X、Z、Y、X的形式。问题在于我们无法确定原始排序是（X，Z，Y）、（Z，Y，X）还是（Y，X，Z），因此我们至少会有最大距离为2。
最后，假设我们有两个节点X和Y，并翻转边XY，其中outdeg（X）= k，outdeg（Y）= m，且k≥m + 3。现在我们留下了一个锦标赛，其中有两个节点的出度为k-1，另外两个节点的出度为m + 1。但这四个节点中，保证只有一对节点可以翻转回来以产生无环锦标赛。看到这一点的一种方法是：取现在具有重复出度的四个节点；将它们称为X和Y（如上所述），还有W和Z，假设我们有循环X，W，Z，Y，X，其中从原始循环中唯一翻转的边是（Y，X）。这个循环会是什么样子？嗯，因为（X，W），（W，Z）和（Z，Y）是没有翻转的锦标赛中的边，所以在原始锦标赛中，我们有outdeg（X）> outdeg（W）> outdeg（Z）> outdeg（Y）。这意味着我们必须让新图中的X和W具有出度k-1，而Z和Y具有出度m + 1。因此，只有翻转从Y到X的边才会增加一个度数为（k-1）的节点的度数回到k，同时减少一个度数为（m + 1）的节点的度数到m。
总结：
定理: 故障比较器要么
- 表现为真实的比较器，在这种情况下，我们交换了原始序列中相邻的两个元素，我们将永远不知道哪个是正确的。
- 恰好有一个长度为三的循环，其中包含元素的原始顺序永远无法得知，或者
- 具有长度为四的循环，在这种情况下，我们可以确定哪个比较被反转了。
考虑到这一点，重新构思问题可以得到以下目标：
目标： 设计一个算法，在O(n log n)的时间内对给定的n个元素列表执行以下操作之一，假设存在故障比较器，该比较器在比较两个固定元素X和Y时返回错误结果：
- 完全排序列表。
- 完全排序列表，除了相邻的两个项被交换。
- 完全排序列表，除了三个相邻的项被排列。
这里有一个可能的算法，它以期望O(n log n)的时间完成，基于快速排序。基本思路如下：我们运行一个更或多或少常规的快速排序，在每个时间点上检查是否找到了三角形。如果没有，那么我们要么处于情况（1）或情况（2）。如果我们确实找到了三角形，我们看看是否可以确定哪个比较被反转了。如果可以，那么我们重新运行快速排序，除了在这种破损情况下“修复”比较器。如果不能，则我们处于情况（3），并像通常一样完成快速排序。
我们将用来检测三角形的具体技术如下。从一个普通的、香草味的快速排序开始：选择一个枢轴，将数组分成小于枢轴和大于枢轴的元素，然后递归地对两个较小的子数组进行排序。然而，在这样做之后，我们还要执行一个额外的步骤：假设我们正在排序的子数组中有三个或更多元素，请查看枢轴p及其前后的元素（称为s，p，g，即“较小”，“枢轴”和“较大”）。然后，如果比较器说s < p < g < s，我们就找到了一个三角形。实际上，我们有更强的东西。
假设在快速排序中，比较器确实比较了X和Y，即不匹配的项。我们假设X < Y，但是比较器错误地报告Y < X。在快速排序中，只有当其中一个元素是当前子数组中的枢轴元素时，才能比较两个项。不失一般性，让我们假设X是枢轴，并将Y与其进行比较。
假设比较器是诚实的，那么在这里应该发生的是 Y 被发现比 X 更大，因此应该被放入“更大”的子数组中。但由于比较器是个撒谎鬼，所以 Y 被放入了“更小”的子数组中。如果我们然后递归地对“更小”的子数组和“更大”的子数组进行排序，想想 Y 最终会在哪里。它在“更小”的子数组中，但实际上比 X 更大，这意味着它将比该“更小”子数组中的所有内容都更大。因此，Y 将出现在 X 的前面。现在看看“更大”子数组中的项目。有两种可能性。第一种是在“真实”的排序中，X 和 Y 之间至少有一个值。那个值将出现在“更大”的子数组中，因为它比 X 更大，特别是“更大”子数组的第一个元素会比 Y 更小。这意味着排序后，Y、X 和紧随 X 之后的项将形成一个三角形。另一种选择是，在真正排序中，X 和 Y 是相邻的，这种情况下我们永远不会知道（如上所述）。这与上面的见解结合起来，意味着：
定理：假设我们运行快速排序，在递归地对左右子数组进行排序后，我们查看由主元、其前一个项和其后一个项组成的三个项，以确定它们是否形成一个三角形。如果此算法检测到三角形，则存在三角形。此外，如果此算法未检测到三角形，则可能存在以下两种情况之一：(1)不存在三角形；(2)存在三角形，但比较器从未应用于错误的对(X,Y)，因此排序顺序是正确的。
说了这么多，我们可以陈述完整的算法，以期望的O(n log n)时间尽可能地对数组进行排序。
function modifiedQuicksort(array, comparator):
if array has length 0 or 1, return.
pick a random pivot element from the array.
use the comparator to form subarrays smaller and greater based on
how elements compare against the pivot.
recursively apply modifiedQuicksort to those two arrays.
if the comparator finds a triangle formed from the last element of
smaller, the pivot, and the first element of greater, report those
three items as a triangle.
return smaller, pivot, greater.
function sortAsBestWeCan(array, comparator):
run modifiedQuicksort(array, comparator)
if it didn't report a triangle, return the result of the call.
otherwise, it reported a triangle A, B, C.
for each other item D:
if comparator(A, D) and comparator(D, B) or
comparator(B, D) and comparator(D, C) or
comparator(C, D) and comparator(D, A):
you have found a 4-cycle from A, B, C, and D.
detect which comparison is reversed.
use that knowledge plus the comparator and your favorite
O(n log n)-time sorting algorithm to perfectly sort
the input array.
otherwise, those three items are the only triangle, and the
array is sorted as well as it can be. return it.
