Python快速排序实现错过了重复的元素

Question

我正在用Python实现Quick Sort.我的代码成功排序列表,但未能包含重复的元素.请帮我找一下这个bug.

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]