快速排序代码 (Python)

Question

这是我在 StackExchange 上的第一个 post，我正在尝试找出我的简单 QuickSort 程序的代码有什么问题。我很确定一些整数只需要调整 +-1 或其他东西，所以我想保留格式。

代码如下：

def QuickSort(Array_1,lower=0,upper=-1):
    print(Array_1)
    if upper==-1:
        upper=len(Array_1)-1
    if lower<upper:
        Array_2,pivot=partition(Array_1,lower,upper)
        Array_3=QuickSort(Array_2,lower,pivot-1)
        Array_4=QuickSort(Array_3,pivot+1,upper)
        return Array_4
    else:
        return Array_1

def partition(Array,lower,upper):
    key=Array[upper]
    print(Array)
    i=lower
    j=lower-1
    z=0
    for j in range(lower,upper-1):
        print(i)
        print(j)
        if Array[j]<key:
            Array[i],Array[j]=Array[j],Array[i]
            i+=1
    Array[upper],Array[i]=Array[i],Array[upper]
    print(Array)
return (Array,i+1)

此外，我注意到的一件事是，如果我将 'j in range(p,r-1)' 更改为 'j in range(p,r)'，代码将无限运行，但它看起来并不像它应该的那样。想法？

变量已被编辑为有意义的变量。我想他们都改对了。

 input: [8, 18, 6, 19]
 desired output: [6,8,18,19]
 output: [19, 8, 18, 6]

 input: [16, 0, 20, 10, 5, 2]
 desired output: [0,2,5,10,16,20]
 output: [2, 0, 20, 16, 10, 5]

Answer 1

正如您已经猜到的那样，您的 partition 函数中只有一些小错误：

1) 您的 for 循环没有处理最后一个元素，因为您使用 range(lower, upper-1) 而不是 range(lower, upper)

2) 你最终应该 return i 而不是 i+1

def partition(Array,lower,upper):
    ...
    for j in range(lower,upper):
    ...
    return (Array,i)

结果：

>>> print QuickSort([8, 18, 6, 19])
[6, 8, 18, 19]

和

>>> print QuickSort([16, 0, 20, 10, 5, 2])
[0, 2, 5, 10, 16, 20]

快速排序代码 (Python)

QuickSort Code (Python)

python

quicksort