我试图实现快速排序的就地分区子例程。它适用于唯一元素数组,但当数组包含重复元素时失败
代码是这样的
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]
这是因为我的实现有问题吗?有人可以帮忙吗?