1的左右尺寸在合并排序中无法正确计算

你在学习Golang相关的知识吗？本文《1的左右尺寸在合并排序中无法正确计算》，主要介绍的内容就涉及到，如果你想提升自己的开发能力，就不要错过这篇文章，大家要知道编程理论基础和实战操作都是不可或缺的哦！

我不确定为什么合并操作的左尺寸和右尺寸似乎不适用于 left = 0、mid = 0 和 right = 1。由于这些计算，左右数组的切片没有任何意义。合并排序算法假设这些数组之一必须具有值才能出现在代码的合并部分中。这会导致索引错误:(

https://play.golang.org/p/fmj4xnqtl8w

package main

import (
    "fmt"
)

func merge(arr []int, l, mid, r int) {
    leftSize := mid - l + 1
    rightSize := r - mid

    left := arr[l:mid]
    right := arr[mid+1 : r]

    fmt.Printf("l:%v, m:%v, r:%v\n", l, mid, r)
    fmt.Printf("left: size:%v arr:%v, right: size:%v arr:%v\n", leftSize, l, rightSize, r)

    /*
        i = left array pointer
        j = right array pointer
        k = original array pointer
    */
    i, j, k := 0, 0, l

    for i < leftSize && j < rightSize {
        if left[i] <= right[j] {
            arr[k] = left[i]
            i++
            k++
        } else {
            arr[k] = right[j]
            j++
            k++
        }
    }

    for i < leftSize {
        arr[k] = left[i]
        i++
        k++
    }
    for j < rightSize {
        arr[k] = right[j]
        j++
        k++
    }
}

func mergeSort(arr []int, left, right int) {
    if left >= right {
        return
    }

    // mid done this way to avoid overflows
    mid := left + (right-left)/2

    mergeSort(arr, left, mid)
    mergeSort(arr, mid+1, right)
    merge(arr, left, mid, right)
}

func main() {
    tc := []int{99, 212, 23, 3, 1, 10}
    mergeSort(tc, 0, len(tc)-1)
    fmt.Printf("%v", tc)
}

解决方案

我想建议一些事情：

1. 数组范围。 dijkstra 曾经争论过数组范围（或 go 中的切片范围）应该是这样的：对于 l[i:j] 的表示法，你希望它具有所有这些属性：

   • 应该从 i 开始。
   • 计算长度应该很简单：len(l[i:j]) == j-i 始终为 true
   • 表达空范围应该很优雅，因此 i<=j 始终为 true

因此，l[i:j]被设置为半开范围：[i,j)，包含下限，排除上限。这也是 go 切片的工作方式（以及 python 和许多其他语言）。

重点是，最好在代码中保留此约定：在执行范围时，包括下限并排除上限。

1. 切片是用 go 构建的。你可以利用它而且很便宜。您不需要以如此冗长且容易出错的方式计算所有这些 l、r、mid，您只需对 slice 进行切片即可。

例如：

func mergesort(arr []int) {
    size := len(arr)

    if size <= 1 {
        return
    }
    mid := size / 2
    mergesort(arr[:mid])
    mergesort(arr[mid:])
    merge(arr, arr[:mid], arr[mid:])
}

代码更加清晰、更加健壮。

1. 切片不会进行深度复制，这意味着 left := arr[l:mid] 仅创建指向 arr 元素的指针。这就是为什么我说 go 中的切片很便宜。

但是，如果没有深层复制，当您合并切片时，数据会被覆盖并因此损坏。您需要合并到一个新切片中，然后将其复制回原始切片。这就是为什么朴素合并排序被认为具有 o(n) 额外内存使用。

func merge(arr, left, right []int) {
    res := make([]int, len(arr))
    leftsize, rightsize := len(left), len(right)

    var i,j,k int
    for i = range res {
        if j >= leftsize || k >= rightsize {
            break
        }

        if left[j] <= right[k] {
            res[i] = left[j]
            j++
        } else {
            res[i] = right[k]
            k++
        }
    }

    // only one of these two copies run, so no need to increase i
    copy(res[i:], left[j:])
    copy(res[i:], right[k:])

    copy(arr, res)
}

演示：https://play.golang.org/p/LlJj-JycfYE

不是完整答案，但一些建议：

1. 您可以通过更改切片索引来避免恐慌：

之前：

left := arr[l : mid]
    right := arr[mid+1 : r]

之后：

left := arr[l : mid+1]
    right := arr[mid : r]

1. 您可以打印左右数组内容来调试每一步发生的情况。打印尺寸不如查看内容有用：

之前：

fmt.printf("left: size:%v arr:%v, right: size:%v arr:%v\n", leftsize, l, rightsize, r)

之后：

fmt.Printf("left: size:%v arr:%v, right: size:%v arr:%v\n", left, l, right, r)

终于介绍完啦！小伙伴们，这篇关于《1的左右尺寸在合并排序中无法正确计算》的介绍应该让你收获多多了吧！欢迎大家收藏或分享给更多需要学习的朋友吧~golang学习网公众号也会发布Golang相关知识，快来关注吧！