以前也无数次的看过快速排序，也无数次死记硬背过快排，今天再次看到快排的时候才恍然大悟，原来可以这么简单的实现快排。废话不说了，直接开车吧。
快排是一种采用分而治之(divide and conquer,D&C)思想的算法，D&C也是一种著名的递归式解决问题的方法。既然是递归算法，那么解决问题的过程通常就包括了两个步骤。
- 找到尽可能简单的基线条件
- 不断将问题分解（或者缩小规模），直到符合基线条件
那么对于排序算法来说，最简单的数组时什么样呢？
最简单的数组
因此，基线条件为数组为空或只包含一个元素，这样的情况下，只需要原样返回数组——根本不用排序。
def quicksort(array):
if len(array)<2:
return array
对包含两个元素的数组排序只需要比较大小交换顺序就可以了
对两个元素排序
对包含三个元素的数组呢？不要忘了咱使用的可是D&C，根据递归策略，对数组进行分解，直到满足基线条件。接下来是快排的工作原理了：
首先从数组中选择一个元素，一般被叫做基准值（pivot），一般我们会将数组的第一个元素作为基准值（其实不一定合适），接下来找到比基准值小和大的元素，即分区（partitioning）。如下图所示：
含有3个元素的数组
分区（partitioning）
现在我们有：
- 一个由小于基准值的数字组成的子数组
- 基准值
- 一个由大于基准值数组组成的子数组
以上只是进行了分区，得到的两个子数组是无序的，如果是有序的，那么合并后就是一个有序的数组了。那么如何对子数组进行排序呢？快排知道如何将他们排序，因此只需要进行快排，然后合并结果就可以了。
quicksort([15,10]) + [33] + quicksort([])
> [10,15,30]
因此最后实现快排的代码：
def quickSort(array):
"""
快速排序
"""
if len(array) < 2:
return array # -----------基线条件
else:
pivot = array[0] # -----------递归条件
less = [i for i in array[1:] if i <= pivot] # -------由所有小于基准值的元素组成的子数组
greater = [i for i in array[1:] if i > pivot] # -------由所有大于基准值的元素组成的字数组
return quickSort(less) + [pivot] + quickSort(greater)
print(quickSort([9, 4, 6, 10, 30, 26, 4]))
> [4, 4, 6, 9, 10, 26, 30]
说好的3行代码呢！借助于python的简洁，上面的代码可以简化为：
def quicksort(array):
if len(array) < 2: return array
return quicksort([lt for lt in array[1:] if lt < array[0]]) + [array[0]] + quicksort([ge for ge in array[1:] if ge >= array[0]])
