快速排序返回未排序的数组

Question

我已经尝试了两天，想弄清楚为什么我的快速排序函数返回的所有元素都被正确地排序，除了其中的两个。

以下是输入内容：

quicksort([0,7,3,11,23,87,999,1023,12,713,5,6,9])

输出

[0, 6, 3, 5, 7, 9, 11, 12, 23, 87, 713, 999, 1023]

你觉得这个函数哪里有问题？

def quicksort(array):
    #Base case
    if len(array) <= 1:
        return array
    #Choose pivot always at the left part and partition array around it
    Pivot = partition(array,0,len(array));
    #Add values for left and righ arrays
    left = array[:Pivot]
    right = array[Pivot+1:]
    #Add recursive calls
    left = quicksort(left)
    right = quicksort(right)
    #Append Pivot at the end of left array
    left.append(array[Pivot])
    return left+right

为了完整起见，我会添加分区函数，但我几乎确定问题不在那里。

def partition(array,left,right):
    #If pivot is not on leftmost, swap to make it leftmost
    Pivot = array[left]
    i = left+1
    for j in range(left+1,right):
        if array[j] < Pivot:
            #Swap array[j] and array[i]
            array[j], array[i] = array[i], array[j]
            i += 1;
    #Swap pivot and A[i-1]        
    array[left], array[i-1] = array[i-1], array[left]
    return left

- Juanvulcano

---

你当前的代码在排序[3,1,2]时也会失败，如果你想使用一个更简单的例子。 - moreON

Answer 1

你的分区函数总是返回left参数，因为它没有被更改。我认为你想要返回枢轴元素的最终位置。

- moreON

---

我爱你，我以为我完美地实现了分区函数，但我错了。谢谢！ - Juanvulcano

Answer 2

为了完整起见，利用Python的推导列表可以使代码更简单易读。

def qs(l):
    if len(l) < 2:
        return l
    pivot = l.pop()
    left = [x for x in l if x < pivot]
    right = [x for x in l if x >= pivot]
    return qs(left) + [pivot] + qs(right)

这篇文章的伪代码读起来非常类似于教科书中的伪代码。

1. 长度为1或0的列表按定义是有序的
2. 选择一个枢轴，本例中是最后一个元素
3. 创建两个分区，使一个分区拥有所有小于枢轴的元素，另一个分区拥有大于或等于枢轴的元素
4. 递归地对两个分区进行快速排序，并在中间添加枢轴得到结果

- Davide