在数组 A 中，我们有一个反转 (i, j)。为什么数组中至少有 j-i 次反转？
in array A, we have an inversion (i, j). why do we have at least j-i inversions in array?
我们有一个数组 A：
在数组 A 中存在一对 (i, j) 且 iA[j]。为什么我们在数组 A 中至少有 j-i 次反转？
(i, j)是一个反转。另一个 j-i-1 涉及索引 k 使得 i<k<j，因为 A[i]>A[k] 或 A[k]>A[j]（否则，A[i]<=A[k]<=A[k]，这意味着 A[i]<=A[j] 并且与 A[i]>A[j]).
的假设相矛盾
我们有一个数组 A：
在数组 A 中存在一对 (i, j) 且 i
(i, j)是一个反转。另一个 j-i-1 涉及索引 k 使得 i<k<j，因为 A[i]>A[k] 或 A[k]>A[j]（否则，A[i]<=A[k]<=A[k]，这意味着 A[i]<=A[j] 并且与 A[i]>A[j]).