我不確定為什么合并操作的左大小和右大小似乎不適用于左 = 0、中 = 0 和右 = 1。由于這些計(jì)算，左右數(shù)組的切片不起作用有任何意義。合并排序算法假定這些數(shù)組之一必須具有值才能使其位于代碼的合并部分。這導(dǎo)致索引錯(cuò)誤:(https://play.golang.org/p/Fmj4xNQTL8Wpackage mainimport ( "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 回答
Helenr
TA貢獻(xiàn)1780條經(jīng)驗(yàn) 獲得超4個(gè)贊
我想建議幾件事：
數(shù)組范圍。Dijkstra 曾經(jīng)爭論過數(shù)組范圍（或在 Go 中，切片范圍）應(yīng)該如何：對于 的符號
l[i:j]，您希望它具有所有這些屬性：它應(yīng)該從 i 開始。
計(jì)算長度應(yīng)該是微不足道的：
len(l[i:j]) == j-i總是正確的表達(dá)一個(gè)空范圍應(yīng)該是優(yōu)雅的，所以
i<=j總是如此
因此，l[i:j]被設(shè)置為一個(gè)半開范圍：[i,j]，包含下界，排除上界。這也是 Go 切片的工作方式（以及 Python 和許多其他語言）。
關(guān)鍵是，最好在您的代碼中保留此約定：在執(zhí)行范圍時(shí)，包括下限并排除上限。
切片是內(nèi)置于 Go 中的。你可以使用它而且很便宜。您不需要以如此冗長且容易出錯(cuò)的方式計(jì)算所有這些
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:])
}
代碼更清晰、更健壯。
切片不做深拷貝，這意味著，
left := arr[l:mid]只創(chuàng)建一個(gè)指向 的元素的指針arr。這就是為什么我說切片在 Go 中很便宜。
但是，如果沒有深拷貝，當(dāng)您合并切片時(shí)，數(shù)據(jù)會(huì)被覆蓋并因此損壞。您需要合并到一個(gè)新的切片中，然后將其復(fù)制回原始切片。這就是為什么 naive mergesort 被認(rèn)為有O(n)額外的內(nèi)存使用。
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)
}
Playground: https://play.golang.org/p/LlJj-JycfYE
- 1 回答
- 0 關(guān)注
- 174 瀏覽
添加回答
舉報(bào)
0/150
提交
取消