Pythonic快速排序算法

Question

我的快速有效的，就地的，奏鸣曲吗？

def quicksort(array, lo, hi):
    if hi - lo < 2:
        return
    key = random.randrange(lo, hi)
    array[key], array[lo] = array[lo], array[key]
    y = 1 + lo
    for x in xrange(lo + 1, hi):
        if array[x] <= array[lo]:
            array[x], array[y] = array[y], array[x]
            y += 1
    array[lo], array[y - 1] = array[y - 1], array[lo]
    quicksort(array, lo, y - 1)
    quicksort(array, y, hi)


a = map(int, raw_input().split())
quicksort(a, 0, len(a))

Answer 1

考虑一下您的分区方法

for x in xrange(lo + 1, hi):
    if array[x] <= array[lo]:
        array[x], array[y] = array[y], array[x]
        y += 1

抽象化出来，看上去就像这样。

def partition(array, lo, hi, pivot):
    y = lo
    for x in xrange(lo, hi):
        if array[x] <= pivot:
            array[x], array[y] = array[y], array[x]
            y += 1
    return y

# eg
pivot = partition(array, lo + 1, hi, array[lo])
array[lo], array[pivot] = array[pivot], array[lo]

我觉得这是一种奇怪的分区方法。这不是我学到的，但它更简单，似乎很有效。在搜索示例时，我遇到了关于cs.exchange的这个问题。您应该阅读非常详细的答案，并考虑使用Hoare分区，因为它总是略显效率。

另外，您应该考虑实现一个单独的交换方法。你使用的成语非常好，它只是变得冗长，而且你经常使用它。

def swap_indexes(array, a, b):
    array[a], array[b] = array[b], array[a]

Answer 2

总的来说看起来不错。很少有评论。

• 失踪的import random。
• 随机枢轴选择只是许多可能的策略之一。根据数据的性质，这可能是一个很好的策略，也可能不是一个好的策略。只有客户知道什么是合适的策略，让他选择吧。
• 没有原始循环咒语:每个循环可能代表一个算法，通常是非常重要的本身。在这种情况下，算法是partition。它本身的作用是值得考虑的。