1. 快速排序

不稳定，时间复杂度：O(nlogn)， 空间复杂度：O(logn)

缺点： 对小规模的数据集性能不是很好。

通过一趟sort将要排序的data分割成独立的两部分，其中一部分的所有数据比另一部分的所有数据都要小，然后再递归地对这两部分数据进行快排，直到整个待排序列有序。

对待排序列A[0],A[1], ..., A[N-1]，选取序列的第一个元素(可以是任意元素)作为基准点，然后将所有比它小的数都放到它前面，所有比他大的元素放到它的后面，这个过程称为一趟快速排序。每一趟快排都是将这一趟的基准数归位，直到所有的数都归位为止。

1.1 最简实现

未改变原列表

def quick_sort(arr):
    if arr is None or len(arr) < 2:
        return arr
    return quick_sort([i for i in arr[1:] if i < arr[0]]) \
           + arr[0:1] \
           + quick_sort([i for i in arr[1:] if i >= arr[0]])

1.2 一般实现

2. 归并排序

1. 分解：将当前区间一分为二，即求分裂点mid；

2. 求解：递归地对两个子区间a[:mid]和a[mid:]进行归并排序(终结条件是子区间长度为1)；

3. 合并：将已排序的两个子区间a[:mid]和a[mid:]归并为一个有序的区间a[:]。

快速排序和归并排序都是分而治之，但归并排序是从中间直接将数列分成两个，而快排是比较后将小的放左边，大的放右边；合并时，归并排序需要将两个数组重新再次排序，而快排则不需要，所有快排更高效一些。

注意：

while a 为True 等价于 a is not None and len(a)>0