概览

快速排序基于分治模式，其基本思想是在一次排序中将一列元素拆分成两个部分，以一个“中间值”（称之为主元）为界，其左边的元素总是小于等于它，而右边的元素则总是大于或等于它。然后递归的对左列元素和右列元素进行此操作。这样即可实现对整列元素的排序。

Partition 过程

快速排序的关键在于确定这个“左”和“右”，即如何对一个数组进行划分。对于最原始的快速排序来说，总是将要排序数组中的第一个元素当作主元，然后左右交替的迭代数组中的元素，并最终达到之前所说的目标：主元左边的元素始终不大于主元，而右边的元素始终不小于主元。下图展示了该过程：

p 为主元，即初始时数组中的第一个元素；

i 和 j 的初始状态分别指向数组的最左边和最右边。

第一次从右至左找寻比 p 小的元素，并将两者交换；

第二次从左至右找寻比 p 大的元素，并将两者交换；

循环进行，直到 i、j 相遇。

来看看 Python 实现的示例代码：

def partition(l, p, r):
    """
    PARTITION 过程，实现对子列表 l[p, r] 的原址重排

    :param l: 排序列表
    :param p: 起始位置
    :param r: 终止位置
    :return: 主元（pivot）
    """

    # 将子列表的第一个元素作为主元，
    # 则排序后的列表中主元左侧的元素小于或等于主元，右侧的元素大于或等于主元
    pivot = l[p]

    left = p
    right = r

    while left < right:
        # 整个查找左右交替进行
        # 当从左至右查找，查询比主元小的元素
        # 当从右至左查找，则查询比主元大的元素

        while left < right and l[right] >= pivot:
            right -= 1

        l[left], l[right] = l[right], l[left]

        while left < right and l[left] <= pivot:
            left += 1

        l[left], l[right] = l[right], l[left]

    # 最后将主元所在的位置返回
    return left

快速排序

之后要做的就是针对左右两侧的数组递归的进行划分，这样就构成了快速排序：

def quick_sort(l, p=0, r=None):
    """
    快速排序

    :param l: 排序列表
    :param p: 排序起始位置
    :param r: 排序终止位置
    :return: 无返回
    """

    r = len(l) - 1 if r is None else r
    if p < r:
        # 调用 PARTITION 函数对列表进行划分，并得到划分的支点，即主元所在的位置
        q = partition(l, p, r)
        # 以主元为中心，对左、后子数组再次排序
        quick_sort(l, p, q - 1)
        quick_sort(l, q + 1, r)

时间复杂度

快速排序的期望时间复杂度是O(nlgn)。但针对一个已经排好序的数组来说，其递归树呈完全的“一边倒”趋势，导致其最坏情况的时间复杂度为O(n^2)。

当然在之前，我用了一个名词叫最原始的快速排序。因为通过改进可以很好的避免这种情况发生。如随机化快速排序通过随机选取主元来规避”一边倒“的情况。很多资料中都有详细的描述，这仅仅简单一提，而这些也值得我去更深入地探索和学习。

参考文档

《算法导论》第七章