recursion - 戈朗 : Counting Inversions Sorting issue

Question

我最近开始尝试使用 Golang。我正在尝试编写一个程序来计算给定 slice 的反转次数，但我遇到了一个问题。

我正在尝试使用基于 MergeSort 的代码对 slice 进行排序，但我的代码似乎无法正确对 slice 进行排序。我假设必须对最后的 slice 进行排序才能使反转计数正常工作，但我不知道该怎么做。我可以在这个问题上得到一些帮助吗？

func InversionCount(a []int) int {
    if len(a) <= 1 {
        return 0
    }
    mid := len(a) / 2
    left := a[:mid]
    right := a[mid:]
    leftCount := InversionCount(left)
    rightCount := InversionCount(right)

    res := make([]int, 0, len(right)+len(left)) //temp slice to hold the sorted left side and right side

    iCount := mergeCount(left, right, &res)

    a = res        //Copies the result back into the original slice
    fmt.Println(a) //Why hasn't "a" been sorted?
    return iCount + leftCount + rightCount
}

func mergeCount(left, right []int, res *[]int) int {
    count := 0

    for len(left) > 0 || len(right) > 0 {
        if len(left) == 0 {
            *res = append(*res, right...)
            break
        }
        if len(right) == 0 {
            *res = append(*res, left...)
            break
        }
        if left[0] <= right[0] {
            *res = append(*res, left[0])
            left = left[1:]
        } else { //Inversion has been found
            count += 1
            *res = append(*res, right[0])
            right = right[1:]
        }
    }

    return count
}

func main() {
    s := []int{4, 3, 2, 1}
    fmt.Print(InversionCount(s))
}

这是我的代码的链接:http://play.golang.org/p/QSJyg_qadD

Answer 1

你需要更换线路

count += 1

与

count += len(left)

要点是在 mergeCount 中的任何一点 left[0] > right[0]，那么因为 left 已经排序, 所有 left 中剩余的东西相对于 right[0] 倒置。如果这样做，您将得到正确的计数。

您的排序不起作用是另一个问题。如果您有兴趣解决这个问题，我建议您取出所有计数逻辑并尝试修复排序。如果您仍然卡住，它可能值得自己的问题。

一个问题是 InversionCount(arr) 不会导致 arr 被排序，所以

a = res        //Copies the result back into the original slice
fmt.Println(a) //Why hasn't "a" been sorted?

这不是您想要的，因为早些时候当您将 mergeCount 应用于 left 和 right 时，那些子数组left 和 right 未按 InversionCount 排序。一个更简单的例子:

package main

import "fmt"

func Foo(a []int) {
    a = []int{1, 2, 3, 4}
}

func main() {
    a := []int{4, 3, 2, 1}
    Foo(a)
    fmt.Println(a) // [4, 3, 2, 1]
}