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

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

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

^{pr2}$

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

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

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

Answer 1

这应该行了

def partitionv(arr, l, r):

    p = r
    idx = l
    for i in range(l, r-1, 1):
        if arr[i] < arr[p]:
            arr[i], arr[idx] = arr[idx], arr[i]
            idx += 1
    arr[p], arr[idx] = arr[idx], arr[p]

    return arr

这是右边元素的一个分区。在

Answer 2

我不太明白你的算法，它看起来不像快速排序分区。通常，你沿着不同的方向运行i和j，一个从区间顶部开始，另一个从底部开始，但是如果我理解正确，你的方向是相同的。在第一次迭代中，i和j具有相同的值，如果它小于枢轴，则将其自身交换（即，与不小于枢轴的效果相同）？在

Answer 3

if input[j]<pivot:

这意味着它只会将较小的数字移动到轴的左侧。 但是，您希望移动与轴心大小相等的数字，否则与轴心大小相等的数字将散布在轴心的右侧。在

更改为：

^{pr2}$