概览 快速排序基于分治模式，其基本思想是在一次排序中将一列元素拆分成两个部分，以一个“中间值”（称之为主元）为界，其左边的元素总是小于等于它，而右边的元素则总是大于或等于它。然后递归的对左列元素和右列元素进行此操作。这样即可实现对整列元素的排序。 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)。 当然在之前，我用了一个名词叫最原始的快速排序。因为通过改进可以很好的避免这种情况发生。如随机化快速排序通过随机选取主元来规避”一边倒“的情况。很多资料中都有详细的描述，这仅仅简单一提，而这些也值得我去更深入地探索和学习。 参考文档 《算法导论》第七章