数组中的反转，我错了什么。请查看下面的 Math/Pseudo 代码

Question

我一直在尝试写一个倒数的伪代码。

为了便于说明，让我们的数组称为长度为 n 的 mainArray。并假设 n 为偶数。

根据我的理解，i<j, mainArray[i] > mainArray[j] 时需要对数组进行反转。然后我们交换位置以对其进行排序。

使用合并排序算法，一旦我们达到基本情况并开始合并两半（左半部分和右半部分），代码如下所示

let i = 0, j=0, k=0, inversions = 0
for k in range(0,n-1) 
    if left-half[i] < right-half[j]
       mainArray[k] = left-half[i]
       i+=1
    else
       mainArray[k] = right-half[j]
       j+=1

       //now at this point an inversion has occurred
       //so from my understanding at this point there was only 1 swap? because the program 
       //skipped left-half[i] and proceeded to right-half[j]
       // so my answer was **"Inversions = Inversions + 1"** incrementing by 1 Inversions wherever the **Else-Block is run**. 


       //but in the solution the correct answer is 
       Inversions = Inversions + {(n/2)-i}

我不明白这部分？ 为什么假设右半部分[j] 与数组左半部分中的所有剩余元素交换位置。我在这里缺少什么关键点？

如有任何帮助，我们将不胜感激。谢谢。

Answer 1

回想一下 left-half 和 right-half 是排序的，所以如果 i<j, left-half[i] > right-half[j] 这也意味着 left-half[i+1..n/2] > right[j]。所以我们计算 Inversions + {(n/2)-i} 来计算所有的反转，而不仅仅是一个。

数组中的反转，我错了什么。请查看下面的 Math/Pseudo 代码

Inversions in the array, what am I getting wrong. Please have a look at the Math/Pseudo code below

arrays

sorting

algorithm

recursion

mergesort