如何使这个朴素的 Python 快速排序实现更符合 Python 风格？

Question

我花了两个小时在读《diveintopython》，并且实现了一个简单的快速排序版本。

import operator

def even(num):
    return operator.mod(num,2) == 0

def last(list):
    return len(list)-1

def median(list):
    if even(len(list)):
        return len(list)/2 - 1
    else:
        return len(list)/2

def sort(list, pivot_selector):
    if len(list) <= 1:
        return list
    else:
        i = pivot_selector(list)
        pivot = list[i]
        less, greater, equal = [], [], []
        for x in list:
            if x < pivot:
                less.append( x )
            elif x == pivot:
                equal.append( x )
            else:
                greater.append( x )

    return sort(less, pivot_selector) + equal + sort(greater, pivot_selector)

if __name__ == "__main__":
    print sort([5,4,3,2],median)
    print sort([],median)
    print sort([2],median)
    print sort([3,2],median)
    print sort([3,2,3],median)
    print sort([1,3,2],median)
    print sort([1,'a',0],median)
    print sort([None,1,0],median)

我有5个问题：

1. 这段代码放在一个叫做 quicksort.py 的文件里。怎么才能让某个方法连公开都不让它被看到呢？
2. 把一个 *pivot_selector* 作为参数传进去，这样做算不算是符合 Python 的风格？
3. 我的快速排序实现有什么问题或者不够好的地方吗？
4. 怎么让用户可以指定一个比较器，以便对列表元素进行自定义排序呢？
5. 有没有什么 Python 的方式可以强制要求列表里的元素都是同一种类型？

Answer 1

我觉得这个挺不错的。我喜欢用函数参数来选择枢轴。

有几点建议：

• 不要覆盖内置的名称，比如 list 或 sort。
• 可以用 li[-1] 来获取列表中的最后一个元素。
• even 这个函数看起来有点多余。

Answer 2

关于你的代码，有一些随意的笔记：

• 为什么在 even 里要用 operator.mod 而不是直接用 % 呢？
• 在 median 里，len(list)/2 - 1 真的那么重要吗？如果你的列表长度是4，为什么索引2就比索引1少一个中位数呢？而且，middle 这个名字更合适，因为这个函数其实并没有真正计算出一个 中位数。在快速排序中找到真实的中位数是个复杂的问题，通常都是用近似的方法。
• 把选择器当作函数传递是很符合Python风格的。你可以用同样的方法传递一个比较函数，然后在 sort 中使用它。
• 你的问题（5）听起来有点不符合Python的风格——别这么做。Python强调的是鸭子类型——如果用户认为他想把整数和 class UserID 进行比较，并且提供了合适的方法或运算符，那就让他去做吧。

Answer 3

1 - 这段代码在一个叫做 quicksort.py 的文件里。怎么才能让这个方法连公开都不被导出呢？

通常的做法是给模块里的私有函数名字前加一个下划线。

2 - 把一个 *pivot_selector* 作为参数传入，这样做算不算符合 Python 的风格？

因为 Python 支持一等函数，所以把函数作为参数传来传去是完全可以的。

3 - 我的快速排序实现有什么问题或者不太理想的地方吗？

我觉得使用一个 equal 列表有点不太传统。通常来说，和基准值相等的项会放到 greater 列表里。

4 - 你会怎么让用户指定一个比较器，以便对列表元素进行自定义排序呢？

标准的 Python sort() 和 sorted() 函数都有一个可选的比较函数参数。这似乎是最好的做法。

5 - 有没有什么 Python 风格的方法来强制要求列表参数必须包含同类类型的元素？

在 Python 中，通常你不需要担心这个问题。Python 有鸭子类型的概念，所以只要一个对象能完成它该做的事情，我们就不需要事先检查它的类型。这种做法常常被表达为“请求原谅比请求许可更容易”。

所以，让你的模块的用户去担心如果他们传入一个无法相互比较的对象列表时会抛出的异常吧。