Python 快速排序实现遗漏了重复元素

Question

我正在用 Python 实现快速排序。我的代码成功地对列表进行排序，但未能包含重复元素。请帮我找出错误。

from random import choice

def quickSort(lst):
    if not lst:
        return []
    else:
        pivot = choice(lst)
        lesser = quickSort([l for l in lst if l < pivot])
        greater = quickSort([l for l in lst if l > pivot])
        #print lesser, pivot, greater
        return lesser + [pivot] + greater

print quickSort([3, 2, 5, 6, 1, 7, 2, 4,234, 234, 23, 1234, 24, 132])

输出:

[1, 2, 3, 4, 5, 6, 7, 23, 24, 132, 234, 1234]

Answer 1

你的条件之一需要是<=或 >= (但不是两者)。

否则，您最终会选择一个重复元素作为基准，并且由于其他副本既不大于也不小于基准，因此它们不会传递给 lesser 中的任何一个。或 greater排序。

但是，由于您没有为您的项目使用唯一标识符，因此在您使用整数的示例中，这也将涉及将您的枢轴包含在集合中。为了避免这种情况，您可能需要为数据透视选择一个索引而不是一个值。

例如:

from random import randint

def quickSort(lst):
    if not lst:
        return []
    else:
        pivot = randint(0, len(lst) - 1)
        pivot_value = lst[pivot]
        lesser = quickSort([l for i,l in enumerate(lst)
                           if l <= pivot_value and i != pivot])
        greater = quickSort([l for l in lst if l > pivot_value])
        return lesser + [pivot_value] + greater

---

测试:

>>> from random import randint
>>>
>>> def quickSort(lst):
...     if not lst:
...         return []
...     else:
...         pivot = randint(0, len(lst) - 1)
...         pivot_value = lst[pivot]
...         lesser = quickSort([l for i,l in enumerate(lst)
...                            if l <= pivot_value and i != pivot])
...         greater = quickSort([l for l in lst if l > pivot_value])
...         return lesser + [pivot_value] + greater
...
>>> print quickSort([3, 2, 5, 6, 1, 7, 2, 4,234, 234, 23, 1234, 24, 132])
[1, 2, 2, 3, 4, 5, 6, 7, 23, 24, 132, 234, 234, 1234]