python - 如何在 python 中修复这个快速排序分区？ (处理 Numpy 数组)

Question

我已经在这个快速排序分区上工作了好几天，但仍然无法修复它。我已经尝试使用打印来调试它，以查看分区在被主快速排序调用时如何演变，但仍然无法弄清楚如何修复它。显示 doctest 以提供上下文，如果不相关，我们深表歉意。

它适用于某些示例，但不适用于其他示例，并且无法弄清楚原因。非常感谢任何见解和帮助。

def partition (s, cmp):
>>> import generate
>>> import numpy
>>> import element
>>> def cmp (x,y):
...    if x == y:
...       return 0
...    elif x < y:
...       return -1
...    else:
...       return 1
>>> t = numpy.array([element.Element(i) for i in [3, -8, 2 , -2, 3, 7, 9, 1, -1, 7]])
>>> p = {'left':0,'right':len(t)-1,'data':t}
>>> p1,p2 = partition(p,cmp)
>>> p1['data'][p1['left']:p1['right']+1]
array([-8, 2, -2, 3, -1, 1], dtype=object)
>>> p2['data'][p2['left']:p2['right']+1]
array([9, 7, 7], dtype=object)
"""
    a = s["data"]   #whole array
    lp = s["left"]+1  #left pointer
    rp = s["right"]    #right pointer
    pivot = a[lp-1]    #pivot is element of index lp=0 in slice
    while lp <= rp:
        if cmp(a[lp], pivot) <= 0:  #lp is already on the correct side since it's <= to pivot
            a[lp-1] = a[lp]
            lp += 1   #moving towards center
        else:
            a[lp], a[rp] = a[rp], a[lp] #taking advantage of python's easy swap
            rp -= 1     #moving towards center
    a[rp] = pivot   #replacing pivot in the end
    lslice = {"data" : a, "left" : s["left"], "right" : rp-1}   #<pivot
    rslice = {"data" : a, "left" : rp+1, "right" : s["right"]}  #>pivot
    return (lslice,rslice)

Answer 1

终于找到问题了，菜鸟错误。它不是来自程序本身，而是来自测试定义，

>>> p0 = {'left':0,'right':len(t)-1,'data':t1}

必须是

>>> p0 = {'left':0,'right':len(t1)-1,'data':t1}