1

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

代码是这样的

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]

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

4

3 回答 3

0

这应该这样做

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

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

于 2012-08-23T00:20:36.527 回答
0 
if input[j]<pivot:

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

将其更改为：

if input[j]<=pivot:
于 2012-03-28T07:32:30.650 回答
0

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

于 2012-03-28T13:36:08.427 回答