用python再论快排

今天看到用python实现的快排，虽然消耗了额外空间，但是真的很清新脱俗啊。。。

# -*- coding: UTF-8 -*-

def quicksort(array):
    if(len(array) <= 1):
        return array
    lower = []
    upper = []
    base = array.pop()
    for i in array:
        if i > base:
            upper.append(i)
        else:
            lower.append(i)
    return quicksort(lower) + [base] + quicksort(upper)


print(quicksort([5,2,7,9,12,3,7]))

运行结果：

E:\python_study>python 91.py
[2, 3, 5, 7, 7, 9, 12]

比base大的就丢到大的数组中，比base小的就丢到小的数组中。跟常规的交换位置实现的快排相比较，虽然消耗了额外的空间复杂度，但是思路清晰简单太多了。