如何使用合并排序计算 Scala 中 Int 列表的反转计数?

Question

def mergeSort(xs: List[Int]): List[Int] = {
val n = xs.length / 2
if (n == 0) xs
else {
def merge(xs: List[Int], ys: List[Int]): List[Int] =
(xs, ys) match {
case(Nil, ys) => ys
case(xs, Nil) => xs
case(x :: xs1, y :: ys1) =>
if (x < y) {
x :: merge(xs1, ys)
}
else {
y :: merge(xs, ys1)
}
}
val (left, right) = xs splitAt(n)
merge(mergeSort(left), mergeSort(right))
}
}

数组的反转计数指示 – 数组距离排序有多远(或接近(。如果数组已排序，则反转计数为 0。如果数组按相反顺序排序，则反转计数为最大值。 正式地说，如果a[i]>a[j]和i

例： 序列 2， 4， 1， 3， 5 有三个反转 (2， 1(， (4， 1(， (4， 3(。

因此，如果将此列表(2， 4， 1， 3， 5(传递给函数，则反转计数应为 3。

如何添加变量以获取数字？

Answer 1

可能会有所帮助

def mergeSort(xs: List[Int], cnt: Int): (List[Int], Int) = {
val n = xs.length / 2
if (n == 0) (xs, cnt)
else {
def merge(xs: List[Int], ys: List[Int], cnt: Int): (List[Int], Int) =
(xs, ys) match {
case(Nil, ys) => (ys, cnt)
case(xs, Nil) => (xs, cnt)
case(x :: xs1, y :: ys1) =>
if (x <= y) {
val t = merge(xs1, ys, cnt)
(x :: t._1, t._2)
}
else {
val t = merge(xs, ys1, cnt + xs.size)
(y :: t._1, t._2)
}
}
val (left, right) = xs splitAt(n)
val leftMergeSort = mergeSort(left, cnt)
val rightMergeSort = mergeSort(right, cnt)
merge(leftMergeSort._1, rightMergeSort._1, leftMergeSort._2 + rightMergeSort._2)
}
}

我正在传递一个元组，就是这样所有的函数调用。

当我们发现一个列表的第一个元素小于第二个列表的第一个元素时，我递增 cnt 的值。在这种情况下，我们将 list.length 添加到 cnt 中。查看代码，以获得更清晰的视图。

希望这有帮助！