最近看到了一个利用Python的list conPRehension实现快速排序的例子，短短几行代码，不仅展示出了快速排序的精髓，而且非常pythonic，看了不禁叹服。下面把这种实现和传统实现都放在这里，进行一个比较。下面的函数quick_sort是传统的实现，换成其他任何语言也都可以这样实现。另一个函数pythonic_quick_sort就是pythonic的实现。
首先构造一个随机数列表用来排序。因为Python默认对递归深度有限制，最大深度是1000。为了防止在排序过程中，因为两边子队列不平衡而造成的栈溢出，所以这里只用了一个较小的列表作为例子，只有1000个元素。当然，在实际工程里面，只需要用Python自带的sort函数就够了。
import random
a = [random.randint(0, 1000) for i in xrange(1000)]def quick_sort(a, start, end): if start >= end: return pivot = a[end] i = start j = end while True: while (not (a[i] > pivot)) and (i < j): i += 1 while (not a[j] < pivot) and (i < j): j -= 1 if i < j: c = a[i] a[i] = a[j] a[j] = c else: c = a[i] a[i] = a[end] a[end] = c break quick_sort(a, start, i - 1) quick_sort(a, i + 1, end)def pythonic_quick_sort(a): if len(a) <= 1: return a pivot = a[-1] pivots = [i for i in a if i == pivot] left = pythonic_quick_sort([i for i in a if i < pivot]) right = pythonic_quick_sort([i for i in a if i > pivot]) return left + pivots + right新闻热点
疑难解答
