合并排序的实施存在哪些缺陷？

在IT行业这个发展更新速度很快的行业，只有不停止的学习，才不会被行业所淘汰。如果你是Golang学习者，那么本文《合并排序的实施存在哪些缺陷？》就很适合你！本篇内容主要包括##content_title##，希望对大家的知识积累有所帮助，助力实战开发！

我一直在尝试像在 python 中那样实现合并排序算法，但由于某种原因结果不正确。

例如，对于这个未排序的数组 [5, 2, 8, 3, 1, 7, 4, 11, 9, 10]，我得到的结果是 [1 1 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
}

正确答案

array、l 和 m 都引用同一个切片。

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

所以当你说：

array[k] = m[j]

您正在用 m[j] 覆盖 l[k] 引用的内容

简单的修复是引入一个新的切片来返回：

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
}

本篇关于《合并排序的实施存在哪些缺陷？》的介绍就到此结束啦，但是学无止境，想要了解学习更多关于Golang的相关知识，请关注golang学习网公众号！