我一直在try 实现合并排序算法,就像我在Python中所做的那样,但由于某些原因,结果并不正确.

例如,对于这个未排序的数组[5,2,8,3,1,7,4,11,9,10],我得到的结果是[1 1 1 4 4 9 9 10],而不是正确的结果.有人能找出函数中的问题吗?

func merge_sort(array []uint) []uint {
    if len(array) > 1 {
        r := len(array) / 2
        L := array[:r]
        M := array[r:]

        L = merge_sort(L)
        M = merge_sort(M)

        i, j, k := 0, 0, 0
        for i < len(L) && j < len(M) {
            if L[i] <= M[j] {
                array[k] = L[i]
                i++
            } else {
                array[k] = M[j]
                j++
            }
            k++
        }
        for i < len(L) {
            array[k] = L[i]
            i++
            k++
        }
        for j < len(M) {
            array[k] = M[j]
            j++
            k++
        }
    }

    return array
}

推荐答案

arrayLM都引用相同的切片.

L[0]引用的元素与array[0]相同

所以当你说:

array[k] = M[j]

您正在覆盖L[j]引用的M[j]

简单的解决方法是引入一个新的切片来返回:

func merge_sort(array []uint) []uint {

    if len(array) > 1 {
        r := len(array) / 2
        L := array[:r]
        M := array[r:]

        L = merge_sort(L)
        M = merge_sort(M)

        result := make([]uint, len(array))

        i, j, k := 0, 0, 0
        for i < len(L) && j < len(M) {
            if L[i] <= M[j] {
                result[k] = L[i]
                i++
            } else {
                result[k] = M[j]
                j++
            }
            k++
        }
        for i < len(L) {
            result[k] = L[i]
            i++
            k++
        }
        for j < len(M) {
            result[k] = M[j]
            j++
            k++
        }
        return result
    }
    return array
}

Go相关问答推荐

如何修复Go中调用GetRawInputDeviceInfA Windows API函数时的错误?

为什么我不能使用Docker从本地访问我的Gin应用程序?

如何使用中间件更改http请求的响应代码?

通过渠道和goroutines增值1000倍

如何将 goose 迁移与 pgx 一起使用?

go-jwt 令牌验证错误 - 令牌签名无效:密钥类型无效

Golang telegram 机器人

testcontainers:如何修复绑定源路径不存在

我应该先解锁然后再广播吗?

Github Actions Go lambda 项目不同的 sha256sums

Apache Beam 左加入 Go

从动态输入中提取字符串,其中部分字符串可能不存在

将 .gz 文件添加到 tar.gz 文件,但在添加之前解码 gz.输出文件被剪辑(损坏)

我相信我正确地在 sRGB 和线性 RGB 之间进行了转换,那么为什么深色的结果看起来更糟呢?

如何使用特定的 Go 版本运行 govulncheck?

使用go doc命令查看示例函数?

Gorm 在保存/创建时序列化 struct

函数调用中的类型参数panic

Go:为一组单个结果实现 ManyDecode

如何断言类型是指向golang中接口的指针