python - 就地分区不适用于重复元素

Question

我试图实现快速排序的就地分区子例程。它适用于唯一元素数组，但当数组包含重复元素时失败

代码是这样的

def inplace_partitioning(input,l,r):
    len_a=len(input)
    pivot=input[l]
    i=l+1
    for j in range(l+1,r+1,1):
        if input[j]<pivot:#do nothing if new elem >pivot
            #swap new elem with leftmost elem greater than pivot
            temp=input[j]
            input[j]=input[i]
            input[i]=temp
            i+=1
    #swap pivot with rightmost elem lessthan pivot
    temp=input[l]
    input[l]=input[i-1]
    input[i-1]=temp

当输入是唯一元素时，代码给出正确的结果

input=[5,6,3,1,8,4]
inplace_partitioning(input,0,len(input)-1)
print input

>>[4, 3, 1, 5, 8, 6]

当我尝试下面的数组时，我得到了错误的结果

input=[5,6,3,1,8,5]
>>>[1, 3, 5, 6, 8, 5]

这是因为我的实现有问题吗？有人可以帮忙吗？

Answer 1

if input[j]<pivot:

这意味着它只会将较小的数字移到主元的左侧。但是，您希望移动等于枢轴大小的数字，否则与枢轴大小相等的数字将分布在整个枢轴右侧。

将其更改为:

if input[j]<=pivot: