1

我正在尝试合并两个列表但出现错误。有人有想法吗？

下面是我的合并功能。

 def mymerg(container, first_index, mid_index, last_index):
      left_list = container[:mid_index]
      right_list = container[mid_index:]
      i = 0
      j = 0
      for elem in range(first_index, last_index+1, 1):
           if left_list[i] <= right_list[j]:
                container[elem] = left_list[i]
                i = i + 1
           else:
                container[elem] = right_list[j]
                j = j + 1

这是我的排序函数，它在 My_Merge_Sort(container, first_index, mid_index) 行中生成错误

    def mymgsor(container, first_index, last_index):
            if first_index < last_index:
                    mid_index = len(container)//2
                    mymgsor(container, first_index, mid_index)
                    mymgsor(container, mid_index+1, last_index)
                    mymerg(container, first_index, mid_index, last_index)

如果 first_index < last_index: RuntimeError: maximum recursion depth exceeded in comparison，我也会收到此错误。我的代码有什么问题？提前致谢。

当我调用这个函数时，我使用 mymgsor(sample_list, 0, len(sample_list)-1)

4

1 回答 1

1

使用heapq.merge而不是实现你自己的。

>>> import heapq
>>> list(heapq.merge([1,3,5], [2,4,6,7,8]))
[1, 2, 3, 4, 5, 6, 7, 8]

使用 heapq.merge：

>>> def mymgsor(container, first_index, last_index):
...     if first_index < last_index:
...         mid_index = (last_index+first_index) // 2
...         mymgsor(container, first_index, mid_index)
...         mymgsor(container, mid_index+1, last_index)
...         container[first_index:last_index+1] = heapq.merge(container[first_index:mid_index+1], container[mid_index+1:last_index+1])
...
>>> xs = [5,4,2,3,1]
>>> mymgsor(xs, 0, len(xs)-1)
>>> xs
[1, 2, 3, 4, 5]

运行时错误的原因：

以下行总是产生相同的值；导致 的无限递归mymgsor：

mid_index = len(container)//2

mymerg计算指数错误。尝试以下操作：

def mymerg(container, first_index, mid_index, last_index):
    left_list = container[first_index:mid_index+1]   # copy only  first_index .. mid_index
    right_list = container[mid_index+1:last_index+1] # copy only mid_index+1 .. last_index
    i = 0
    j = 0
    for elem in range(first_index, last_index+1, 1):
        if left_list[i] <= right_list[j]:
            container[elem] = left_list[i]
            i += 1
            if i == len(left_list): # no more left
                container[elem+1:last_index+1] = right_list[j:]
                break
        else:
            container[elem] = right_list[j]
            j += 1
            if j == len(right_list): # no more right
                container[elem+1:last_index+1] = left_list[i:]
                break
于 2013-08-31T18:06:12.513 回答