2

我正在用 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]
4

2 回答 2

6

您的条件之一必须是<=或>=（但不是两者兼有）。

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

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

例如：

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]
于 2013-03-20T05:41:57.803 回答
0

您不能确保列表中只有一个元素是相等的枢轴。你应该返回这个：

return lesser + [pivot]*(len(lst) - len(lesser)- len(greater)) + greater
于 2013-03-20T05:46:15.827 回答