arrays - 数组中的反转，我错了什么。请查看下面的数学/伪代码

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}

这部分我没看懂？为什么假设 right-half[j] 与数组左半部分中的所有剩余元素交换位置。 我在这里缺少什么关键点？

任何帮助，将不胜感激。谢谢。

标签： arraysalgorithmsortingrecursionmergesort

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}所有的反转，而不仅仅是一个。