MergeSort递归实现
MergeSort recursive implementation
我今天刚学 Python,正在尝试递归地实现 Mergesort...我完全不知道我做错了什么。有人可以帮忙吗?
def mergesort(A):
if len(A) < 2:
return A
middle = len(A) // 2
L = mergesort(A[:middle])
R = mergesort(A[middle:])
return merge(L, R)
# Merge - combine part of mergesort
def merge(Lsort, Rsort):
sort = [None] * (len(Lsort + Rsort))
i = 0
j = 0
k = 0
while (len(Lsort) <= len(sort)) or (len(Rsort) <= len(sort)):
if Lsort[i] < Rsort[j]:
sort[k] = Lsort[i]
i += 1
else:
sort[k] = Rsort[j]
j += 1
k += 1
return sort
这与Python无关,而是与逻辑有关。
将 while
表达式更改为
while k < len(sort):
和if
表达为
if (j >= len(Rsort)) or (i < len(Lsort) and Lsort[i] < Rsort[j]):
你的合并功能有问题,应该更像是:
def merge(Lsort, Rsort):
sort = []
i = 0
j = 0
while (len(Lsort) > i) & (len(Rsort) > j):
if Lsort[i] < Rsort[j]:
sort.append(Lsort[i])
i += 1
else:
sort.append(Rsort[j])
j += 1
if len(Lsort) > 0:
sort += Lsort[i:]
if len(Rsort) > 0:
sort += Rsort[j:]
return sort
一般来说,您不需要为排序分配 space,只需在进行时追加到一个空列表即可。对于 while 逻辑,您需要确保不超出 Lsort 和 Rsort 数组的范围。确保您的索引小于数组长度。
当任一数组用完时,您可以将剩余的数组项连接到您的排序列表中。
这里是http://interactivepython.org/runestone/static/pythonds/SortSearch/TheMergeSort.html
提供的Python版本
(注意下面我在示例列表上粘贴了应用程序流程的图像,以帮助我理解递归流程(因为我是 nube))。
我今天刚学 Python,正在尝试递归地实现 Mergesort...我完全不知道我做错了什么。有人可以帮忙吗?
def mergesort(A):
if len(A) < 2:
return A
middle = len(A) // 2
L = mergesort(A[:middle])
R = mergesort(A[middle:])
return merge(L, R)
# Merge - combine part of mergesort
def merge(Lsort, Rsort):
sort = [None] * (len(Lsort + Rsort))
i = 0
j = 0
k = 0
while (len(Lsort) <= len(sort)) or (len(Rsort) <= len(sort)):
if Lsort[i] < Rsort[j]:
sort[k] = Lsort[i]
i += 1
else:
sort[k] = Rsort[j]
j += 1
k += 1
return sort
这与Python无关,而是与逻辑有关。
将 while
表达式更改为
while k < len(sort):
和if
表达为
if (j >= len(Rsort)) or (i < len(Lsort) and Lsort[i] < Rsort[j]):
你的合并功能有问题,应该更像是:
def merge(Lsort, Rsort):
sort = []
i = 0
j = 0
while (len(Lsort) > i) & (len(Rsort) > j):
if Lsort[i] < Rsort[j]:
sort.append(Lsort[i])
i += 1
else:
sort.append(Rsort[j])
j += 1
if len(Lsort) > 0:
sort += Lsort[i:]
if len(Rsort) > 0:
sort += Rsort[j:]
return sort
一般来说,您不需要为排序分配 space,只需在进行时追加到一个空列表即可。对于 while 逻辑,您需要确保不超出 Lsort 和 Rsort 数组的范围。确保您的索引小于数组长度。
当任一数组用完时,您可以将剩余的数组项连接到您的排序列表中。
这里是http://interactivepython.org/runestone/static/pythonds/SortSearch/TheMergeSort.html
提供的Python版本(注意下面我在示例列表上粘贴了应用程序流程的图像,以帮助我理解递归流程(因为我是 nube))。