尽管分区函数会执行（python），但Quicksort函数不会产生预期的输出

我必须在学校项目的“切片”对象上实现快速排序算法，该切片对象是具有以下内容的元组：

• 一个“数据”字段（要排序的整个numpy数组）
• “ left”和“ right”字段（索引表示数组中切片的子部分）

分区功能代码如下：

def partition (s, cmp, piv=0):
"""
Creates two slices from *s* by selecting in the first slice all
elements being less than the pivot and in the second one all other
elements.

:param s: A slice of is a dictionary with 3 fields :
          - data: the array of objects,
          - left: left bound of the slide (a position in the array),
          - right: right bound of the slice.
:type s: dict
:param cmp: A comparison function, returning 0 if a == b, -1 is a < b, 1 if a > b
:type cmp: function
:return: A couple of slices, the first slice contains all elements that are
         less than the pivot, the second one contains all elements that are
         greater than the pivot, the pivot does not belong to any slice.
:rtype: tuple

>>> import generate
>>> import element
>>> import numpy
>>> 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 [4,2,3,1]])
>>> p = {'left':0,'right':len(t)-1,'data':t}
>>> pivot = 0
>>> p1,p2 = partition(p,cmp,pivot)
>>> print(p1['data'][p1['left']:p1['right']+1])
[1 2 3 4]
>>> print(p2['data'][p2['left']:p2['right']+1])
[]
"""
#convenience variables to make the function easily readable.
left = s['left']
right = s['right']
swap(s['data'],right,piv)

j = left
for i in range(left,right+1):
    if (cmp(s['data'][i] , s['data'][right]) != 1 ):
        swap(s['data'],i,j)
        j += 1
s1 = {'data':s['data'],'left':left,'right':j-1}
s2 = {'data':s['data'],'left':j+1,'right':right}

return s1,s2

此函数的doctest不会失败，但是在调用quicksort递归函数时，分区函数的行为不符合预期。quicksort函数的代码如下：

def quicksort_slice (s, cmp):
"""
A sorting function implementing the quicksort algorithm

:param s: A slice of an array, that is a dictionary with 3 fields :
          data, left, right representing resp. an array of objects and left
          and right bounds of the slice.
:type s: dict
:param cmp: A comparison function, returning 0 if a == b, -1 is a < b, 1 if a > b
:type cmp: function
:return: Nothing

>>> import generate
>>> import element
>>> import numpy
>>> 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 [4,5,1,2,3,8,9,6,7]])
>>> p = {'left':0,'right':len(t)-1,'data':t}
>>> quicksort_slice(p,cmp)
>>> print(p['data'])
[1 2 3 4 5 6 7 8 9]
"""

if s['left'] < s['right'] :
    s1,s2 = partition(s,cmp)
    quicksort_slice(s1,cmp)
    quicksort_slice(s2,cmp)

这是doctests为此功能生成的输出：

File "C:\Users\Marion\Documents\S2\ASD\TP\tp2_asd\src\sorting.py", line 148, in __main__.quicksort_slice
Failed example:
    print(p['data'])
Expected:
    [1 2 3 4 5 6 7 8 9]
Got:
    [8 2 1 3 7 4 9 5 6]

我试图插入调试打印语句来观察对分区函数的递归调用，看来它不能正确交换值，但我不知道如何解决此问题。任何帮助将非常感激。

编辑：正如下面的评论中所指出的那样，我只是忘了更新piv的值，在第一次调用该函数后它并不总是为0。我还替换了：

for i in range(left,right+1):
if (cmp(s['data'][i] , s['data'][right]) != 1 ):
    swap(s['data'],i,j)
    j += 1

与

for i in range(left,right):
    if (cmp(s['data'][i] , s['data'][right]) != 1 ):
        swap(s['data'],i,j)
        j += 1
swap(s['data'],right,j)