algorithm - 如何解决合并排序中的递归错误?
问题描述
我试图通过仅使用一个 1 辅助数组而不是在递归例程中为左右创建一个新数组来实现合并排序。因为这可能会导致额外创建数组的大量成本。而且您有时会看到 Mergesort 由于该错误而表现不佳。
我正在尝试按照本课程中的描述实现合并排序 - https://www.coursera.org/learn/algorithms-part1/lecture/ARWDq/mergesort (第 7 分钟 -10 分钟)。
我目前面临 RecursionError
我已经用 python 编写了代码(在这个社区的其他人的帮助下)。这里是 -
class merge_sort:
aux_array = []
def __init__(self, data):
self.data = data
self.aux_array = [0 for i in range(len(data))]
def merge(self, low, mid, high):
for k in range(low, high):
self.aux_array[k] = self.data[k]
if( low == high):
self.data[low] = self.aux_array[low]
return
i = low
j = mid + 1
for k in range(low, high):
if(i > mid):
self.data[k] = self.aux_array[j]
j = j + 1
elif(j > high):
self.data[k] = self.aux_array[i]
i = i + 1
elif(self.aux_array[i] < self.aux_array[j]):
self.data[k] = self.aux_array[i]
i = i + 1
else:
self.data[k] = self.aux_array[j]
j = j + 1
return
def mergesort(self,low, high):
if(low < high):
mid = (high - low)//2
self.mergesort(low, mid)
self.mergesort(mid+1, high)
self.merge(low, mid, high)
else:
return
def start_sort(self):
high = len(self.data) - 1
self.mergesort(0, high)
arr = [10, 2, 30, 0, 4]
arr1 = merge_sort(arr)
arr1.start_sort()
print(arr1)
这是确切的错误-
Traceback (most recent call last):
File "new_sorting.py", line 55, in <module>
arr1.start_sort()
File "new_sorting.py", line 49, in start_sort
self.mergesort(0, high)
File "new_sorting.py", line 42, in mergesort
self.mergesort(mid+1, high)
File "new_sorting.py", line 42, in mergesort
self.mergesort(mid+1, high)
File "new_sorting.py", line 42, in mergesort
self.mergesort(mid+1, high)
[Previous line repeated 993 more times]
File "new_sorting.py", line 41, in mergesort
self.mergesort(low, mid)
File "new_sorting.py", line 39, in mergesort
if(low < high):
RecursionError: maximum recursion depth exceeded in comparison
解决方案
评论中指出的修复:
class merge_sort:
def __init__(self, data):
self.data = data # reference to data
self.aux_array = [0] * len(data) # allocate aux_array
def merge(self, low, mid, high):
for k in range(low, high+1): # fix (high+1)
self.aux_array[k] = self.data[k]
i = low
j = mid + 1
for k in range(low, high+1): # fix (high+1)
if(i > mid):
self.data[k] = self.aux_array[j]
j = j + 1
elif(j > high):
self.data[k] = self.aux_array[i]
i = i + 1
elif(self.aux_array[i] < self.aux_array[j]):
self.data[k] = self.aux_array[i]
i = i + 1
else:
self.data[k] = self.aux_array[j]
j = j + 1
def mergesort(self, low, high):
if(low >= high):
return
mid = low + (high - low)//2 # fix (low + )
self.mergesort(low, mid)
self.mergesort(mid+1, high)
self.merge(low, mid, high)
def start_sort(self):
high = len(self.data) - 1
self.mergesort(0, high)
arr = [10, 2, 30, 0, 4]
#arr1.data will be a reference to arr
arr1 = merge_sort(arr)
arr1.start_sort()
print(arr) # fix (arr not arr1)