函数实现递归归并排序?

Question

尝试在Python中实现函数递归归并排序已经有好几天了。除此之外，我希望能够打印出排序算法的每一步。是否有任何方法使这个Python代码以函数范式的方式运行?这是我到目前为止得到的…

def merge_sort(arr, low, high):
#  If low is less than high, proceed. Else, array is sorted
if low < high:
mid = (low + high) // 2             # Get the midpoint
merge_sort (arr, low, mid)          # Recursively split the left half
merge_sort (arr, mid+1, high)       # Recursively split the right half

return merge(arr, low, mid, high)   # merge halves together
def merge (arr, low, mid, high):
temp = []
# Copy all the values into a temporary array for displaying
for index, elem in enumerate(arr): 
temp.append(elem)
left_p, right_p, i = low, mid+1, low
# While left and right pointer still have elements to read
while left_p <= mid and right_p <= high:
if temp[left_p] <= temp[right_p]:   # If the left value is less than the right value. Shift left pointer by 1 unit to the right
arr[i] = temp[left_p]
left_p += 1
else:                               # Else, place the right value into target array. Shift right pointer by 1 unit to the right
arr[i] = temp[right_p]
right_p += 1
i += 1                              # Increment target array pointer
# Copy the rest of the left side of the array into the target array
while left_p <= mid:
arr[i] = temp[left_p]
i += 1
left_p += 1
print(*arr) # Display the current form of the array
return arr
def main():
# Get input from user
arr = [int(input()) for x in range(int(input("Input the number of elements: ")))]
print("Sorting...")
sorted_arr = merge_sort(arr.copy(), 0, len(arr)-1)      
print("nSorted Array")
print(*sorted_arr)
if __name__ == "__main__":
main()

任何帮助将不胜感激!谢谢你。

Answer 1

在纯函数式归并排序中，我们不希望改变任何值。

我们可以定义一个零突变的递归版本，如下所示:

def merge(a1, a2):
if len(a1) == 0:
return a2
if len(a2) == 0:
return a1
if a1[0] <= a2[0]:
rec = merge(a1[1:], a2)
return [a1[0]] + rec
rec = merge(a1, a2[1:])
return [a2[0]] + rec
def merge_sort(arr):
if len(arr) <= 1:
return arr
halfway = len(arr) // 2
left = merge_sort(arr[:halfway])
right = merge_sort(arr[halfway:])
return merge(left, right)

您可以将print(arr)添加到merge_sort的顶部以逐步打印，但是技术上的副作用将使其不纯(尽管在这种情况下仍然是引用透明的)。然而，在python中，您无法使用monad将副作用从纯计算中分离出来，因此如果您真的想避免这种打印，则必须返回层，并在最后打印它们:)

而且，这个版本在技术上做了大量的列表拷贝，所以相对较慢。这可以通过使用链表来修复，并添加/删除它。但是，这超出了范围。