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