我已经编写了一个递归版本的归并排序算法。它使用了一个单独的merge
程序:
def merge(lst1, lst2):
i = j = 0
merged = []
while i < len(lst1) and j < len(lst2):
if lst1[i] <= lst2[j]:
merged.append(lst1[i])
i += 1
else:
merged.append(lst2[j])
j += 1
merged.extend(lst1[i:])
merged.extend(lst2[j:])
return merged
def merge_sort(lst):
if len(lst) < 2:
return lst
else:
middle = len(lst) / 2
return merge(merge_sort(lst[:middle]), merge_sort(lst[middle:]))
为了节省堆栈空间(并且为了学习算法的乐趣),我正试图以迭代方式编写这个函数。然而,我发现这很困难,因为我不确定如何在最后组合不同的列表。
谢谢!