这个Python的归并排序哪里出问题了?

完全相同的逻辑在C++下没有问题,Python报
RecursionError: maximum recursion depth exceeded in comparison

    
def merge(a:list, start:int, end:int, mid:int):
    t=deepcopy(a)
    i=start
    j=mid
    k=start
    while i<mid and j<end:
        if(t[i]>t[j]):
            a[k]=t[j]
            k+=1
            j+=1
        else:
            a[k]=t[i]
            i+=1
            k+=1
    while i<mid:
        a[k]=t[i]
        i+=1
        k+=1
    while j<end:
        a[k]=t[j]
        j+=1
        k+=1

    def merge_sort(a:list, start:int, end:int):
        if start<(end-1):
            mid=(end-start)//2
            merge_sort(a, start,mid)
            merge_sort(a, mid, end)
            merge(a, start, end, mid)


阅读 2.3k
3 个回答

报错是递归层数超过了默认的,设置一下

import sys 
sys.setrecursionlimit(1000000)
def sort_arr(arr):
  while len(arr) > 1:
    # 数组中元素两两归并,并排序
    arr = [
      sort_arrs(arr[i], arr[i + 1] if i < len(arr) - 1 else [])
      for i in range(0, len(arr), 2)
    ]
  # 全部归并成功后,数组中将只剩一个元素,返回这个元素就是排序结果了
  return arr[0]


def sort_arrs(arr1, arr2=None):
  # 假如需要排序的数组是 [1, 2, 3] 则需要这一步
  # 假如需要排序的数组是 [[1], [2], [3]] 则不需要这一步
  if isinstance(arr1, int):
    arr1 = [arr1]
  if isinstance(arr2, int):
    arr2 = [arr2]
  if not arr2:
    return arr1
  res = []
  index = 0
  for item in arr1:
    while index < len(arr2):
      if item < arr2[index]:
        break
      res.append(arr2[index])
      index += 1
    res.append(item)
  res.extend(arr2[index:])
  return res


print sort_arr([12, 23, 1, 44, 233, 10, 9, 8, 0])

发现哪错了……
计算mid的时候应该是

mid=(end+start)//2

这里把加号写成减号了

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
推荐问题