DSA Interview Prep · 课时

快速排序与枢轴选择

使用 Lomuto 和 Hoare 分区方案构建快速排序，讨论最坏情况下的 O(n²)，以及随机选择枢轴如何缓解这一问题。

快速排序与枢轴选择 是 CoddyKit 上的免费 DSA Interview Prep 课时。这是第 3 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。

快速排序：原地分治

快速排序是实践中使用最广泛的排序算法。与归并排序不同，它无需分配额外数组即可进行原地排序。核心思想是：选择一个枢轴元素，对数组进行 partition，使所有小于枢轴的元素位于其左侧，所有大于枢轴的元素位于其右侧，然后递归地对每个 partition 排序。partition 步骤需要 O(n) 时间；如果枢轴选择得当，递归深度为 O(log n)。

def quick_sort(arr, lo=0, hi=None):
    if hi is None: hi = len(arr) - 1
    if lo < hi:
        pivot_idx = partition(arr, lo, hi)
        quick_sort(arr, lo, pivot_idx - 1)  # sort left
        quick_sort(arr, pivot_idx + 1, hi)  # sort right

def partition(arr, lo, hi):
    pivot = arr[hi]  # Lomuto: choose last element as pivot
    i = lo - 1
    for j in range(lo, hi):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[hi] = arr[hi], arr[i+1]
    return i + 1

arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort(arr)
print(arr)  # [1, 1, 2, 3, 6, 8, 10]

Lomuto 分区方案

Lomuto partition使用最后一个元素作为枢轴。慢指针 i 跟踪“小于枢轴”区域的边界，快指针 j 向前扫描。当 arr[j] <= pivot 时，将 i 加一，并交换 arr[i] 与 arr[j]，从而扩展较小元素区域。扫描完成后，通过与 arr[hi] 交换，将枢轴放置到 i+1 位置。它易于实现，但交换次数比 Hoare 方案多 3 倍。

def lomuto_partition_traced(arr, lo, hi):
    pivot = arr[hi]
    i = lo - 1
    print(f'Pivot: {pivot}, array: {arr[lo:hi+1]}')
    for j in range(lo, hi):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[hi] = arr[hi], arr[i+1]
    print(f'After partition: {arr[lo:hi+1]}')
    return i + 1

arr = [3, 1, 4, 1, 5, 9, 2, 6]
lomuto_partition_traced(arr, 0, len(arr)-1)

Hoare 分区方案

Hoare partition使用从两端开始的两个指针，不断向中间移动，直到二者交叉。它选择枢轴（通常是第一个元素），将小于枢轴的元素移到左侧，将大于枢轴的元素移到右侧。Hoare 方案的交换次数比 Lomuto 方案少 3 倍，并且处理相等元素时效果更好，但 partition 完成后枢轴不会处于最终位置，因此需要使用略有不同的递归调用。

def hoare_partition(arr, lo, hi):
    pivot = arr[lo]  # first element as pivot
    i, j = lo - 1, hi + 1
    while True:
        i += 1
        while arr[i] < pivot: i += 1
        j -= 1
        while arr[j] > pivot: j -= 1
        if i >= j: return j
        arr[i], arr[j] = arr[j], arr[i]

def quick_sort_hoare(arr, lo=0, hi=None):
    if hi is None: hi = len(arr) - 1
    if lo < hi:
        p = hoare_partition(arr, lo, hi)
        quick_sort_hoare(arr, lo, p)      # note: p not p-1
        quick_sort_hoare(arr, p+1, hi)

arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort_hoare(arr)
print(arr)  # [1, 1, 2, 3, 6, 8, 10]

最坏情况 O(n²)：已经有序的输入

当枢轴始终是 partition 中最小或最大的元素时，快速排序会出现最坏情况。对于已经有序的数组，如果使用 Lomuto 的最后元素作为枢轴，partition 总是将 0 个元素放在左侧，将 n-1 个元素放在右侧：递归树退化成深度为 n 的链，从而产生 O(n²) 次比较。这就是枢轴选择至关重要，以及生产实现会将枢轴随机化的原因。

import sys
sys.setrecursionlimit(5000)

def quick_sort_naive(arr, lo=0, hi=None):
    if hi is None: hi = len(arr) - 1
    comparisons = [0]
    def _qs(lo, hi):
        if lo >= hi: return
        pivot = arr[hi]  # last element pivot
        i = lo - 1
        for j in range(lo, hi):
            comparisons[0] += 1
            if arr[j] <= pivot:
                i += 1; arr[i], arr[j] = arr[j], arr[i]
        arr[i+1], arr[hi] = arr[hi], arr[i+1]
        p = i + 1
        _qs(lo, p-1); _qs(p+1, hi)
    _qs(lo, hi)
    return comparisons[0]

import math
n = 100
sorted_arr = list(range(n))
ops = quick_sort_naive(sorted_arr)
print(f'n={n}, ops={ops}, n^2={n**2}')  # ops close to n*(n-1)/2

随机枢轴：期望 O(n log n)

通过均匀随机地选择枢轴（在 partition 前将一个随机元素与 arr[hi] 交换），持续选择糟糕枢轴的概率会呈指数级下降。比较次数的期望值为 2n ln(n) ≈ 1.39 n log₂(n)，因此以压倒性概率达到期望 O(n log n) 时间。这就是实践中使用随机快速排序的原因——它可以避免对手针对固定枢轴策略精心构造的病态最坏情况。

import random

def quick_sort_random(arr, lo=0, hi=None):
    if hi is None: hi = len(arr) - 1
    if lo < hi:
        # Randomise pivot
        rand_i = random.randint(lo, hi)
        arr[rand_i], arr[hi] = arr[hi], arr[rand_i]
        # Lomuto partition with last element as pivot
        pivot = arr[hi]
        i = lo - 1
        for j in range(lo, hi):
            if arr[j] <= pivot:
                i += 1; arr[i], arr[j] = arr[j], arr[i]
        arr[i+1], arr[hi] = arr[hi], arr[i+1]
        p = i + 1
        quick_sort_random(arr, lo, p - 1)
        quick_sort_random(arr, p + 1, hi)

arr = list(range(100, 0, -1))  # worst case for naive
quick_sort_random(arr)
print(arr[:10])  # [1,2,3,4,5,6,7,8,9,10]

三数取中枢轴

另一种枢轴策略是选择第一个、中间和最后一个元素的中位数。这样可以避免对已经排序或逆序排序的输入（最常见的对抗性输入）出现最坏情况，同时避免生成随机数的开销。许多生产实现会对大型数组使用三数取中或九点取中（三个中位数的中位数），并在小于约 10 个元素的子数组上回退到插入排序。

def median_of_three(arr, lo, hi):
    mid = (lo + hi) // 2
    # Sort lo, mid, hi values in place
    if arr[lo] > arr[mid]:  arr[lo], arr[mid] = arr[mid], arr[lo]
    if arr[lo] > arr[hi]:   arr[lo], arr[hi]  = arr[hi],  arr[lo]
    if arr[mid] > arr[hi]:  arr[mid], arr[hi] = arr[hi],  arr[mid]
    # Median is now at arr[mid]; swap to arr[hi-1] as pivot
    arr[mid], arr[hi] = arr[hi], arr[mid]
    return arr[hi]  # pivot value

arr = [3, 9, 1]
print(median_of_three(arr, 0, 2), arr)  # 3, [1,3,9] (sorted)

荷兰国旗问题：三路分区

标准分区会将小于枢轴的元素放在左侧，将大于枢轴的元素放在右侧，但等于枢轴的元素会分散在各处。三路分区（荷兰国旗问题）会创建三个区域：<pivot、==pivot、>pivot。对于包含大量重复元素的数组，这一点至关重要——标准快速排序会退化到 O(n²)，而三路快速排序在所有元素值都相同的输入上可以达到 O(n)。

def three_way_partition(arr, lo, hi):
    pivot = arr[lo]
    lt = lo      # arr[lo..lt-1] < pivot
    gt = hi      # arr[gt+1..hi] > pivot
    i = lo       # current
    while i <= gt:
        if arr[i] < pivot:
            arr[lt], arr[i] = arr[i], arr[lt]
            lt += 1; i += 1
        elif arr[i] > pivot:
            arr[i], arr[gt] = arr[gt], arr[i]
            gt -= 1  # don't advance i
        else:
            i += 1
    return lt, gt  # pivot occupies arr[lt..gt]

arr = [3, 1, 4, 1, 5, 9, 2, 6, 3, 3]
lt, gt = three_way_partition(arr, 0, len(arr)-1)
print(arr, '| pivot region:', lt, 'to', gt)

Quickselect：O(n) 时间内找第 k 小的元素

Quickselect使用快速排序的 partition 步骤来查找第 k 小的元素，无需完整排序，平均时间复杂度为 O(n)。partition 完成后，枢轴位于最终位置 p。如果 p == k，则返回 arr[p]。如果 k < p，则在左侧 partition 上递归；如果 k > p，则在右侧 partition 上递归。平均而言，每次递归都会将问题规模减半：O(n) + O(n/2) + O(n/4) + ... = O(2n) = O(n)。

import random

def quickselect(nums, k):
    '''Find kth smallest (0-indexed) in O(n) average.'''
    def _select(lo, hi):
        if lo == hi: return nums[lo]
        rand_i = random.randint(lo, hi)
        nums[rand_i], nums[hi] = nums[hi], nums[rand_i]
        pivot = nums[hi]
        i = lo - 1
        for j in range(lo, hi):
            if nums[j] <= pivot:
                i += 1; nums[i], nums[j] = nums[j], nums[i]
        p = i + 1
        nums[p], nums[hi] = nums[hi], nums[p]
        if p == k:    return nums[p]
        elif k < p:   return _select(lo, p - 1)
        else:         return _select(p + 1, hi)
    return _select(0, len(nums) - 1)

print(quickselect([3,2,1,5,6,4], 1))  # 2  (2nd smallest)

快速排序的空间复杂度

快速排序被称为“原地”算法，但递归仍会使用平均 O(log n) 的栈空间（递归树每一层对应一个栈帧）。最坏情况下，栈深度为 O(n)。若要保证最坏情况下的栈空间为 O(log n)，应始终先对较小的 partition 进行递归，并对较大的 partition 使用尾调用优化。Python 的递归深度限制使得过深的快速排序递归存在风险——这一点值得在面试中提及。

def quick_sort_optimised(arr, lo=0, hi=None):
    if hi is None: hi = len(arr) - 1
    while lo < hi:
        p = lomuto_partition_qs(arr, lo, hi)
        # Recurse on smaller partition; iterate on larger
        if p - lo < hi - p:
            quick_sort_optimised(arr, lo, p - 1)
            lo = p + 1  # tail-call elimination
        else:
            quick_sort_optimised(arr, p + 1, hi)
            hi = p - 1

def lomuto_partition_qs(arr, lo, hi):
    pivot = arr[hi]; i = lo - 1
    for j in range(lo, hi):
        if arr[j] <= pivot: i += 1; arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[hi] = arr[hi], arr[i+1]
    return i + 1

比较排序算法

综合运用您所学的知识：

快速排序：期望 O(n log n)，最坏 O(n²)，O(log n) 空间，不稳定，在随机数据上实践中最快
归并排序：保证 O(n log n)，O(n) 空间，稳定，最适合链表和外部排序
堆排序：保证 O(n log n)，O(1) 空间，不稳定，由于缓存未命中，实践中速度较慢
插入排序：最佳情况为 O(n)，适合较小的 n 或几乎有序的数据

在面试中，请根据这些权衡说明您的选择理由。

# Python's sorted() uses Timsort:
# - Hybrid: merge sort for large runs, insertion sort for small (< 64 elements)
# - Stable, O(n log n) worst case
# - O(n) best case for sorted/reverse-sorted/nearly-sorted
# - O(n) extra space

import random
arr = random.sample(range(10000), 1000)
sorted_arr = sorted(arr)  # Timsort
print(sorted_arr[:5], '...')  # first 5 elements

Introsort：三者结合

Introsort（在 C++ STL 中用于 std::sort）结合了快速排序、堆排序和插入排序：先使用随机快速排序；如果递归深度超过 2 log n（表明枢轴序列不理想），就切换到堆排序，以保证 O(n log n)；对于小于 16 个元素的子数组，则使用插入排序。这样既能保证最坏情况为 O(n log n)，又兼具快速排序的平均情况速度和插入排序在小型子数组上的效率。

# Introsort hybrid (simplified)
def introsort(arr, depth_limit=None):
    if depth_limit is None:
        import math
        depth_limit = 2 * int(math.log2(len(arr) + 1)) if arr else 0
    if len(arr) <= 16:
        # insertion sort for small arrays
        for i in range(1, len(arr)):
            key = arr[i]; j = i - 1
            while j >= 0 and arr[j] > key:
                arr[j+1] = arr[j]; j -= 1
            arr[j+1] = key
        return arr
    if depth_limit == 0:
        arr.sort()  # fall back to heapsort equivalent
        return arr
    # Otherwise quick sort
    pivot = arr[-1]
    small = [x for x in arr[:-1] if x <= pivot]
    large = [x for x in arr[:-1] if x > pivot]
    return introsort(small, depth_limit-1) + [pivot] + introsort(large, depth_limit-1)

print(introsort([5,3,8,1,9,2,7]))

快速检查

测试您对本课数据结构与算法——编程面试准备相关概念的理解。

课程回顾

本课中您学到了：快速排序围绕枢轴进行原地分区，并对两侧递归处理，以 O(log n) 的栈空间达到期望 O(n log n) 的时间复杂度——在随机数据上实践中比归并排序更快；最坏情况 O(n²) 会在使用固定枢轴处理有序输入时出现，可以通过随机选择枢轴或使用三数取中来避免；以及三路分区能够高效处理重复元素，而 Quickselect 将分区思想扩展为在无需完整排序的情况下，以 O(n) 的平均时间找到第 k 小的元素。接下来我们将探索非比较排序以及 Python 的内置 sort。

常见问题解答

「快速排序与枢轴选择」课时是免费的吗？

是的 — 「快速排序与枢轴选择」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。

「快速排序与枢轴选择」这节课中我会学到什么？

使用 Lomuto 和 Hoare 分区方案构建快速排序，讨论最坏情况下的 O(n²)，以及随机选择枢轴如何缓解这一问题。你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 DSA Interview Prep 需要有经验吗？

无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。这是第 3 节课，共 4 节。

「快速排序与枢轴选择」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 DSA Interview Prep 课中编写并运行代码吗？

能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

← 返回 DSA Interview Prep