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

你不能保证列表中只有一个元素和基准值相等。你应该返回这个：

return lesser + [pivot]*(len(lst) - len(lesser)- len(greater)) + greater

Answer 2

你需要在条件中使用 <= 或 >= 其中之一（但不能同时使用）。

否则，你可能会选到重复的元素作为基准值，而这些重复的元素既不大于也不小于基准值，所以它们不会被分到 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]