快速排序详解：原理、代码与时间复杂度

通俗地说，思路是什么

1. 选一个基准元素，比如最后一个元素，或者随机的一个。
2. 分区：把所有比基准小的元素移到它的左边，所有比它大的移到右边。此时基准就处在它最终的有序位置。
3. 递归地对基准左边和右边的部分排序。之后不需要再合并任何东西。

归并排序是拆分简单、合并困难；快速排序正相反：由分区完成主要工作，而拼合两半则是零成本，因为它们本来就在同一个数组里的正确位置上。

示例：一次 Lomuto 分区

以最后一个元素 70 为基准，对 [10, 80, 30, 90, 40, 50, 70] 分区。下标 i 标记比基准小的元素区域的末尾；j 从左到右扫描。

70 现在位于下标 4，即它的最终位置。接着快速排序分别对 [10, 30, 40, 50] 和 [90, 80] 排序。

Python 实现

import random

def partition(a, lo, hi):
    """Lomuto partition of a[lo..hi] around a random pivot."""
    r = random.randint(lo, hi)
    a[r], a[hi] = a[hi], a[r]       # move the pivot to the end
    pivot = a[hi]
    i = lo - 1
    for j in range(lo, hi):
        if a[j] < pivot:
            i += 1
            a[i], a[j] = a[j], a[i]
    a[i + 1], a[hi] = a[hi], a[i + 1]
    return i + 1

def quicksort(a, lo=0, hi=None):
    """Sort list a in place."""
    if hi is None:
        hi = len(a) - 1
    while lo < hi:
        p = partition(a, lo, hi)
        if p - lo < hi - p:           # recurse on the smaller side
            quicksort(a, lo, p - 1)
            lo = p + 1
        else:
            quicksort(a, p + 1, hi)
            hi = p - 1
    return a

print(quicksort([10, 80, 30, 90, 40, 50, 70]))   # [10, 30, 40, 50, 70, 80, 90]
print(quicksort([3, 3, 3, 1]))                   # [1, 3, 3, 3]

递归进入较小的一侧、对较大的一侧用循环处理，可以让栈深度即使在最坏情况下也保持 O(log n)。为了讲解思路，一个简短的非原地版本很流行，但它在每一层都会分配新列表：

def quicksort_simple(items):
    if len(items) <= 1:
        return items
    pivot = items[len(items) // 2]
    less = [x for x in items if x < pivot]
    equal = [x for x in items if x == pivot]
    greater = [x for x in items if x > pivot]
    return quicksort_simple(less) + equal + quicksort_simple(greater)

print(quicksort_simple([5, 2, 9, 2, 7]))   # [2, 2, 5, 7, 9]

时间与空间复杂度

经典的最坏情况是：固定选首元素或末元素为基准，输入又恰好已有序或逆序，此时每次分区只去掉基准本身，形成 n 层、每层 O(n) 的工作。随机基准让任何输入都几乎不可能出现这种情况。

快速排序与其他排序算法的比较

快速排序不稳定：分区时的交换可能让元素越过与它相等的元素。在内存中的数组上，它通常胜过归并排序和堆排序，因为它的内层循环简单、原地工作，并且大多按顺序访问内存。Introsort 被许多 C++ 标准库的 std::sort 实现所采用，它从快速排序开始，递归过深时切换到堆排序，从而保证 O(n log n)。

基准选择、变体与常见错误

• 基准的选择：首元素或末元素（简单，但在有序输入上是 O(n²)）、随机元素，或三数取中（首、中、尾三者的中位数）。
• Hoare 分区：两个下标相向移动，交换处于错误一侧的元素对。平均而言它的交换次数比 Lomuto 少。
• 三路分区（荷兰国旗问题）：划分为小于、等于和大于三部分。它让含大量重复键的数组也很快；而普通的 Lomuto 在所有键都相等时会退化为 O(n²)。
• 双基准快速排序使用两个基准、分成三部分；Java 用它来对基本类型的数组排序。
• 快速选择（Quickselect）只做一次分区，并只递归进入其中一侧，平均 O(n) 时间内找到第 k 小的元素。

何时使用快速排序

在不需要稳定性时，快速排序是对内存中的数组排序的良好默认选择。在 Python 中请改用 sorted() 或 list.sort()；它们使用 Timsort，既稳定，又对部分有序的数据很快。实现快速排序是非常常见的面试题，后面往往追问最坏情况、基准选择、稳定性，或用快速选择求第 k 大的元素。