使用归并排序算法编写的C/C++程序,用于计算数组中的逆序数

使用归并排序算法编写的C/C++程序,用于计算数组中的逆序数

数组的反转表示;需要进行多少次更改才能将数组转换为其排序形式。当数组已经排序时,需要 0 次反转,而在其他情况下,如果数组反转,反转次数将达到最大。

为了解决这个问题,我们将遵循归并排序方法降低时间复杂度,采用分治算法。

输入

A sequence of numbers. (1, 5, 6, 4, 20).

登录后复制

输出

将数字升序排列所需的反转次数。

Here the number of inversions are 2.
First inversion: (1, 5, 4, 6, 20)
Second inversion: (1, 4, 5, 6, 20)

登录后复制

算法

merge(array, tempArray, left, mid, right)

输入 - 两个数组,谁已经合并,左,右和中间索引。

输出-按排序顺序合并的数组。

Begin
i := left, j := mid, k := right
count := 0
while i