2 回答
好吧，让我们考虑一下。
我们意识到，每个数字最终都需要与小于它之后的每个数字交换，迟早。因此，给定数字的掉期总数是它后面小于它的数字的总数。然而，这仍然是O(n^2)时间。
对于冒泡排序的外循环的每一次通过，一个元素被放置在正确的位置。不失一般性，我们会说，对于每一次通过，剩余的最大元素都会被排序到列表的末尾。
因此，在外循环的第一遍中，最大的数字放在最后。这需要q次交换，其中q是从最终位置开始的位置数。
因此，我们可以说需要q 1 +q 2 + ... +q n交换来完成这个冒泡排序。但是，请记住，每次交换时，都会将一个数字靠近一个位置或远离其最终位置一个位置。在我们的特定情况下，如果一个数字在一个更大的数字前面，并且在其正确位置或前面，则需要再进行一次交换。但是，如果一个数字落后于一个更大的数字并且落后于它的正确位置，则需要少交换一次。
我们可以通过以下示例看到这是正确的：
5 3 1 2 4
=> 3 5 1 2 4
=> 3 1 5 2 4
=> 3 1 2 5 4
=> 3 1 2 4 5
=> 1 3 2 4 5
=> 1 2 3 4 5 (6 swaps total)
"5" 移动 4 个空格。"3" 移动 1 个空格。"1" 移动 2 个空格。"2" 移动 2 个空格。"4" 移动 1 个空格。总计：10 个空格。
请注意，3 在 5 之后，在其正确位置的前面。因此，将需要再进行一次交换。1 和 2 落后于 3 和 5 - 将需要少四次交换。4 落后于 5 并且落后于它的正确位置，因此需要少交换一次。我们现在可以看到，预期值 6 与实际值匹配。
我们可以通过首先对列表进行排序来计算 Σq ，在进行排序时将每个元素的原始位置保留在内存中。这在O(nlogn + n)时间上是可能的。
我们还可以看到哪些数字落后于其他数字，但这不可能比O(n^2)时间更快。但是，我们可以获得更快的解决方案。
每次交换都有效地将两个数字移动到正确的位置，但有些交换实际上什么也没做，因为一个最终被交换，每个数字在它小于它之后变得更近，而另一个数字迟早会变得更远。我们前面的例子中的第一次交换因此，在“3”和“5”之间是我们例子中唯一的例子。
我们必须计算有多少所述掉期的总数。这留给读者作为练习，但这里有最后一个提示：您只需遍历列表的前半部分。虽然这对于给定的数字仍然是，最后O(n^2)，我们只需要对O(n^2)列表的前半部分总数进行操作，使其后面的数字总体上更快。
使用分而治之
除：序列n的大小到两个大小为n / 2的列表征服：递归计算两个列表组合：这是一个技巧部分（在线性时间内完成）
结合使用合并和计数。假设这两个列表是 A，B。它们已经排序。从 A、B 生成输出列表 L，同时还计算反转次数 (a,b)，其中 a 在 A 中，b 在 B 中，并且 a > b。
这个想法类似于合并排序中的“合并”。将两个排序的列表合并为一个输出列表，但我们也计算反转。
每次将 a_i 附加到输出时，都不会遇到新的反转，因为 a_i 小于列表 B 中剩下的所有内容。如果将 b_j 附加到输出中，则它小于 A 中的所有剩余项，我们增加按 A 中剩余元素数计算的反转计数。
合并和计数（A，B）；A,B 两个输入列表（已排序）；C 输出列表；i,j 当前指向每个列表的指针，从开头开始；a_i, b_j 由 i, j 指向的元素；count 反转次数，初始为 0
while A,B != empty 将 min(a_i,b_j) 附加到 C if b_j < a_i count += A j++ else i++ 中剩余的元素数；现在一个列表是空的，将列表的其余部分附加到 C 返回计数，C
使用merge-and-count，我们可以设计计数反转算法如下：
sort-and-count(L) 如果 L 有一个元素返回 0 否则将 L 分成 A, B (rA, A) = sort-and-count(A) (rB, B) = sort-and-count(B) (r, L) = 合并计数(A,B) 返回 r = rA+rB+r, L
T(n) = O(n lg n)