为什么python列表显示切片异常？

Question

我正在尝试递归地对列表元素进行分区（如分而治之），然后打印切片元素，但突然发现意外异常（在输出中的第 6 行及以后）。

def Mergesort(a, l, r):
    if(l<r):
      mid = (r+l+1) // 2
      print(a)
      Mergesort(a[l : mid], l, mid-1)
      Mergesort(a[mid : r+1], mid, r)

a = [8, 3, -2, 6, 7, 4, 1, 2, -1, 0, 9, 12, 11, 5] 
Mergesort(a, 0, len(a)-1)

输出：

[8, 3, -2, 6, 7, 4, 1, 2, -1, 0, 9, 12, 11, 5]
[8, 3, -2, 6, 7, 4, 1]
[8, 3, -2]
[3, -2]
[6, 7, 4, 1]
[1]
[]
[2, -1, 0, 9, 12, 11, 5]
[]
[]
[]
[]
[]

Answer 1

这是因为你在def Mergesort中的l, r不准确。当您对 RHS 数组 a=[2, -1, 0, 9, 12, 11, 5] 进行合并排序时，它实际上是运行: Mergesort([2, -1, 0, 9, 12, 11, 5],7,10)，而不是 Mergesort([2, -1, 0, 9, 12, 11, 5],0,3)。由于 len(a)=7，它只会 return 一个空数组 []。我修改了代码：

def Mergesort(a, l, r):
    if(l<r):
        mid = (r+l+1) // 2
        print (a)
   #    
        Mergesort(a[l : mid], 0, len(a)-1)
        Mergesort(a[mid : r+1],0, len(a)-1)

a = [8, 3, -2, 6, 7, 4, 1, 2, -1, 0, 9, 12, 11, 5] 
Mergesort(a, 0, len(a)-1)

现在可以拆分左右数组了。如果在 if 子句中 print (a) 则输出：

[8, 3, -2, 6, 7, 4, 1, 2, -1, 0, 9, 12, 11, 5]
[8, 3, -2, 6, 7, 4, 1]
[8, 3, -2, 6, 7, 4, 1]
[8, 3, -2]
[8, 3, -2]
[8]
[3, -2]
[3]
[-2]
[]
[6, 7, 4, 1]
[6, 7, 4]
[6, 7]
[6]
[7]
[4]
[1]
[]
[2, -1, 0, 9, 12, 11, 5]
[2, -1, 0, 9, 12, 11, 5]
[2, -1, 0]
[2, -1, 0]
[2]
[-1, 0]
[-1]
[0]
[]
[9, 12, 11, 5]
[9, 12, 11]
[9, 12]
[9]
[12]
[11]
[5]
[]

请注意，代码仍不完美，需要改进（但它解决了您提出的拆分问题），我建议改进

1) mid 的定义使其正确拆分偶数数组；

2) l 和 r 的定义使得它不会分割单元素数组。

Answer 2

我找到了解决方案。实际上，在函数中传递切片列表时，索引从零开始。

为什么python列表显示切片异常？

Why is python list showing slicing abnormality?

python

recursion

divide-and-conquer