英文:
Go Golang : Merge Sort Stack Overflow
问题
我刚刚实现了与CLRS中相同的代码。
CLRS中的伪代码如下：
归并排序（Merge-Sort）（A，p，r）
如果 p < r
q = [(q+r)/2]
归并排序（A，p，q）
归并排序（A，q+1，r）
归并（A，p，q，r）
归并（Merge）（A，p，q，r）
n_1 = q - p + 1
n_2 = r - q
令 L[1 .. n_1 + 1] 和 R[1 .. n_2 + 1] 为新数组
对于 i = 1 到 n_1
L[i] = A[p+i-1]
对于 j = 1 到 n_2
R[j] = A[q+j]
L[n_1 + 1] = 无穷大
R[n_2 + 1] = 无穷大
i = 1
j = 1
对于 k = p 到 r
如果 L[i] <= R[j]
A[k] = L[i]
i = i + 1
否则 A[k] = R[j]
j = j + 1
但是我在归并排序中遇到了堆栈溢出的问题。
[9 -13 4 -2 3 1 -10 21 12]
运行时：goroutine堆栈超过250000000字节限制
致命错误：堆栈溢出
运行时堆栈：
运行时抛出（0x1b4980，0x20280）
我该如何解决这个问题？
func MergeSort(slice []int, first, last int) {
if len(slice) < 2 {
return
}
if first < last {
mid := len(slice) / 2
MergeSort(slice, first, mid)
MergeSort(slice, mid+1, last)
Merge(slice, first, mid, last)
}
}
非常感谢！
英文:
http://play.golang.org/p/rRccL6YHtQ
I just implement the same code as in CLRS
Pseudocode from CLRS
Merge-Sort(A, p, r)
if p < r
q = [(q+r)/2]
Merge-Sort(A, p, q)
Merge-Sort(A, q+1, r)
Merge(A, p, q, r)
Merge(A, p, q, r)
n_1 = q - p + 1
n_2 = r - q
let L[1 .. n_1 + 1] and R[1 .. n_2 + 1] be new arrays
for i = 1 to n_1
L[i] = A[p+i-1]
for j = 1 to n_2
R[j] = A[q+j]
L[n_1 + 1] = INFINITE
R[n_2 + 1] = INFINITE
i = 1
j = 1
for k = p to r
if L[i] <= R[j]
A[k] = L[i]
i = i + 1
else A[k] = R[j]
j = j + 1
But I am getting the stack overflow in the merge sort.
[9 -13 4 -2 3 1 -10 21 12]
runtime: goroutine stack exceeds 250000000-byte limit
fatal error: stack overflow
runtime stack:
runtime.throw(0x1b4980, 0x20280)
How do I make this work?
func MergeSort(slice []int, first, last int) {
if len(slice) < 2 {
return
}
if first < last {
mid := len(slice) / 2
MergeSort(slice, first, mid)
MergeSort(slice, mid+1, last)
Merge(slice, first, mid, last)
}
}
thanks a lot!
答案1
得分: 7
mid := len(slice) / 2
这不是中间位置应该放置的地方。中间位置应该在 first 和 last 之间，它们定义了你要排序的切片的区域，而不是切片的中间位置。或者，你可以对切片进行切片，创建新的切片，并去掉 first 和 last。
英文:
mid := len(slice) / 2
That's not where the middle should go. The middle is supposed to be halfway between first and last, which define the region of the slice you're sorting, not halfway through the slice. Alternatively, you can slice the slice to make new slices and drop first and last.
答案2
得分: 0
你似乎没有对要归并排序的切片进行重新切片，所以递归没有终止。
你可以在递归之前重新切片切片，或者可以像这样做：length := last - first（这可能有一个偏移量，取决于"last"是最后一个索引还是最后一个索引之后的一个索引），然后从那里开始。
英文:
You don't seem to be re-slicing the slice you're merge-sorting, so there is no termination of the recursion.
You could either re-slice the slice before recursion, or you can do something like length := last - first (this may have an off-by-one, depending if "last" is the last index or one past the last index) and then go from there.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论