快速排序

快速排序和归并排序类似，都用到了分治的思想。

分解 ----> 解决 ----> 合并

分解：将数组 A[p...r] 划分为两个子数组 A[p...q-1] 和 A[q+1...r]，使得 A[p...q-1] 的每一个元素都小于等于 A[q]，而A[q] 也小于等于 A[q+1...r] 中的每个元素，计算下表 q 也是划分过程的一部分。

解决：通过递归调用快速排序，对子数组 A[p...q-1] 和 A[q+1...r] 进行排序。

合并：因为子数组都是原址排序的，所有不需要合并，A[p...r] 已经有序。

python 版代码如下：

def quickSort(target, p, r):
    if p < r:
        q = partition(target, p, r)
        quickSort(target, p, q-1)
        quickSort(target, q+1, r)
    return target

def partition(target, p, r):
    # 每次选取最右侧元素作为主元，循环结束之后，将主元的正确位置返回
    key = target[r]
    i = p - 1
    for j in range(p, r):
        if target[j] <= key:
            i += 1
            target[i], target[j] = target[j], target[i]
    target[i+1], target[r] = target[r], target[i+1]
    return i + 1

可类比归并排序来记忆！