更快的排序

在基本的排序算法中，介绍了三种排序算法，这三种排序算法的平均复杂度都是O(n^2^)。实际上，如果使用分治(divide-and-conquer)策略，我们还可以实现一些复杂度为O(nlogn)的算法。分治的策略其实就是说，每一种算法都能找到一种方法，将列表分解为更为简单的子列表，随后再将这些子列表递归的排序。

快速排序(quick sort)

首先，我们概括一下快速排序的策略：

从列表中点位置选取一个元素，这个元素叫做基准点（pivot）；
将列表中的元素分区，以便小于基准点的所有元素都移动到基准点的左侧，剩下的元素移动到基准点的右侧，实际上基准点的位置也是可以变化的；
分而治之，对于基准点分割而形成的子列表，递归的重复上述步骤；
每次遇到小于2个元素的子列表，就结束这个过程。

快速排序的实现

def quicksort(lyst):
    if len(lyst) < 2:
        return lyst
    left = []
    right = []
    pivot = lyst.pop()
    for item in lyst:
        if item < pivot:
            left.append(item)
        else:
            right.append(item)
    return quicksort(left) + [pivot] + quicksort(right)

上述代码中，我们默认选择的基准点是列表的最后一个元素，递归的调用quicksort这个函数，完成分割的子列表的排序，直到完成原始列表的排序。从上述代码中可以分析到，快速排序算法的最好情况下，就是每次分割自列表的时候，尽可能的从列表中间进行分割。假设我们每次分割列表都是从原始列表中间分割的，经过log2n次，所有的子列表都只包含一个元素，也就是说，最好情况下的快速排序算法的复杂度是O(nlog2n)；那么最坏的情况就是，对于一个已经排序好的列表，我们选取的基准点是第一个元素或者最后一个元素，这样导致第一次分割后，基准点的左侧或者右侧有n-1个元素，第二次分割后有n-2个元素，依次类推，算法复杂度很容易得出是O(n^2^)。由于上述实现代码中，使用的是递归的方式，那么我们还需要考虑调用栈所使用的内存。由于每次调用都需要一个固定大小的内存用于栈，并且，每一次分割对应了两次的递归调用。可知，在最好的情况下，内存使用的是O(log2n)，在最坏的情况下，内存使用的是O(n)。

归并排序(merge sort)

归并排序的算法概述如下：

计算一个列表的中间位置，并且递归的排序其左边和右边的子列表；
将两个排序好的子列表重新合并为单个排好序的列表；
当子列表不再能够划分的时候，停止这个过程。

实现归并过程

def merge(left, right):
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    if left:
        result += left
    if right:
        result += right
    return result

def mergeSort(lyst):
    if len(lyst) < 2:
        return lyst
    mid = len(lyst) // 2
    left = lyst[:mid]
    right = lyst[mid:]

    left = mergeSort(left)
    right = mergeSort(right)

    return merge(left, right)

上述代码实现中，mergeSort函数实现了算法概述中的第一步，即计算一个列表的中间位置，并且递归的排序左列表和右列表。使用mergeSort函数递归的排序分割的子列表，直到子列表满足len(lyst)<2的条件，然后调用函数merge将分割开的子列表进行合并，合并完成后的结果就是排序后的列表。

归并排序的复杂度分析

由于归并排序中，列表在分割的时候，尽可能的选择了中间位置，那么其在分割操作的时候，最大的运行时间是logn。且在合并的过程中，运行时间为n，则整个归并排序的时间复杂度为O(nlogn)。