时间戳

首页 > 解决方案 > 递归合并排序的功能实现？

python - 递归合并排序的功能实现？

问题描述

尝试在 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()

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

标签： pythonfunctional-programmingmergesortpurely-functional

解决方案

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

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

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 中，您无法使用 monads 将副作用从纯计算中分离出来，因此，如果您想真正避免这种打印，则必须返回层，并在最后打印它们 :)

还有，这个版本在技术上做了很多副本列表，所以比较慢。这可以通过使用链表和 consing / unconsing 来解决。但是，这超出了范围。

推荐阅读