因此,我目前正在使用python和Tkinter制作排序算法可视化工具。我已经实现了选择,插入,冒泡和外壳排序。但是,由于递归性质,我在合并排序方面遇到了麻烦。在合并排序中,它会不断跳过合并排序的调用。
def merge_sort(self, array, lines):
'''Sort the array/lines via merge sort. O(n log n).'''
self.window.title("Merge Sort")
# Basecase.
if len(array) <= 1:
return
middle = len(array) // 2
left = array[:middle]
left_lines = lines[:middle]
right = array[middle:]
right_lines = lines[middle:]
# Recursion.
self.merge_sort(left, left_lines)
self.merge_sort(right, right_lines)
i = j = k = 0
# Merge.
while i < len(left) and j < len(right):
if left[i] < right[j]:
array[k], left[i] = left[i], array[k]
lines[k], left_lines[i] = left_lines[i], lines[k]
self.swap(lines[k], left_lines[i])
yield
i += 1
else:
array[k], right[j] = right[j], array[k]
lines[k], right_lines[j] = right_lines[j], lines[k]
self.swap(lines[k], right_lines[j])
yield
j += 1
k += 1
while i < len(left):
array[k], left[i] = left[i], array[k]
lines[k], left_lines[i] = left_lines[i], lines[k]
self.swap(lines[k], left_lines[i])
yield
i += 1
k += 1
while j < len(right):
array[k], right[j] = right[j], array[k]
lines[k], right_lines[j] = right_lines[j], lines[k]
self.swap(lines[k], right_lines[j])
yield
j += 1
k += 1
This is my method, however it keeps skipping over self.merge_sort(left, left_lines)
and self.merge_sort(right, right_lines)
.
我试过调试它,并使用print语句检查它调用self.merge_sort()的次数,但是它始终只调用一次并退出。