Quick Sort | 快速排序

📚 Quick Sort | 快速排序

Quick sort is a highly efficient, divide-and-conquer sorting algorithm that is widely used in practice and commonly examined in Edexcel A-Level Computer Science. This article explains how quick sort works, its recursive partition process, complexity analysis, and key points to remember for the exam.

快速排序是一种高效的分治排序算法，在实际中广泛应用，也是爱德思 A-Level 计算机科学考试中常见的考点。本文将解释快速排序的工作原理、递归分区过程、复杂度分析以及考试需要掌握的关键要点。

1. Introduction to Quick Sort | 快速排序简介

Quick sort is a comparison-based sorting algorithm that follows the divide-and-conquer strategy. It selects a pivot element, partitions the array into two sub-arrays around the pivot, and then recursively sorts the sub-arrays.

快速排序是一种基于比较的排序算法，遵循分治策略。它选择一个基准元素，将数组划分为基准周围的两个子数组，然后递归地对子数组进行排序。

The algorithm was developed by Tony Hoare in 1959 and has an average-case time complexity of O(n log n), making it faster than simple algorithms like bubble sort and insertion sort for large datasets.

该算法由 Tony Hoare 于 1959 年提出，平均时间复杂度为 O(n log n)，对于大型数据集比冒泡排序、插入排序等简单算法更快。

2. The Partition Step | 分区步骤

The core of quick sort is the partition operation. Given an array and a pivot value, partition rearranges the elements so that all elements less than the pivot come before it, and all elements greater than the pivot come after it.

快速排序的核心是分区操作。给定一个数组和一个基准值，分区会重新排列元素，使所有小于基准的元素位于基准之前，所有大于基准的元素位于基准之后。

There are several partition schemes, including the Lomuto scheme and the Hoare scheme. For Edexcel, the Lomuto scheme is commonly taught because it is simpler to trace in exam questions.

分区有多种方案，包括 Lomuto 方案和 Hoare 方案。在爱德思考试中，通常教授 Lomuto 方案，因为它在考试题目中更容易跟踪。

In the Lomuto partition, the pivot is typically chosen as the last element. A pointer i marks the boundary of the ‘small’ region, and a pointer j scans from left to right, swapping elements smaller than the pivot with the element at position i.

在 Lomuto 分区中，基准通常选择为最后一个元素。指针 i 标记“较小”区域的边界，指针 j 从左向右扫描，将小于基准的元素与位置 i 处的元素交换。

3. Choosing the Pivot | 选择基准值

The choice of pivot greatly affects quick sort’s performance. Common strategies include choosing the first element, the last element, a random element, or the median of the first, middle, and last elements (median-of-three).

基准的选择对快速排序的性能有很大影响。常见的策略包括选择第一个元素、最后一个元素、随机元素，或者第一个、中间和最后一个元素的中位数（三数取中法）。

Choosing a poor pivot, such as always the smallest or largest element in an already sorted array, leads to the worst-case time complexity of O(n²). Median-of-three or random pivot selection helps avoid this degradation in practice.

选择不当的基准（例如在已排序数组中总是选择最小或最大元素）会导致最坏时间复杂度 O(n²)。三数取中法或随机选择基准有助于在实践中避免这种性能退化。

4. Pseudocode for Quick Sort | 快速排序的伪代码

The following pseudocode shows a recursive quick sort using the Lomuto partition scheme. Here, arr is the array to be sorted, lo is the starting index, and hi is the ending index.

以下伪代码展示了使用 Lomuto 分区方案的递归快速排序。其中 arr 是要排序的数组，lo 是起始索引，hi 是结束索引。

QUICKSORT(arr, lo, hi)
    if lo < hi:
        p = PARTITION(arr, lo, hi)
        QUICKSORT(arr, lo, p - 1)
        QUICKSORT(arr, p + 1, hi)

PARTITION(arr, lo, hi)
    pivot = arr[hi]
    i = lo - 1
    for j = lo to hi - 1:
        if arr[j] < pivot:
            i = i + 1
            swap arr[i] and arr[j]
    swap arr[i + 1] and arr[hi]
    return i + 1

In the partition step, the pivot ends up in its final sorted position, and the two sub-arrays are sorted recursively. The base case occurs when lo >= hi, meaning the sub-array has zero or one element.

在分区步骤中，基准最终位于其最终排序位置，然后递归地对两个子数组进行排序。基准情况发生在 lo >= hi 时，表示子数组有零个或一个元素。

5. Worked Example | 实例演练

Let us trace quick sort on the array [8, 3, 7, 4, 2]. We choose the last element as the pivot, so pivot = 2. The partition step moves all elements smaller than 2 to the left, but since 2 is the smallest, the array becomes [2, 3, 7, 4, 8] and pivot index 0 is returned.

让我们对数组 [8, 3, 7, 4, 2] 跟踪快速排序。我们选择最后一个元素作为基准，因此 pivot = 2。分区步骤将所有小于 2 的元素移到左侧，但由于 2 是最小的，数组变为 [2, 3, 7, 4, 8]，返回基准索引 0。

Next, quick sort the right sub-array [3, 7, 4, 8] with pivot 8. All elements are smaller than 8, so the partition leaves the array as [3, 7, 4, 8] and returns index 3 (last). Then quick sort the left sub-array [3, 7, 4] with pivot 4. Partition swaps 7 and 4, giving [3, 4, 7] and pivot index 1. Finally, sub-arrays [3] and [7] are already sorted.

接下来，对右子数组 [3, 7, 4, 8] 以 8 为基准进行快速排序。所有元素都小于 8，因此分区后数组仍为 [3, 7, 4, 8]，返回索引 3（最后一个）。然后对左子数组 [3, 7, 4] 以 4 为基准进行快速排序。分区交换 7 和 4，得到 [3, 4, 7]，返回基准索引 1。最后子数组 [3] 和 [7] 已经有序。

The final sorted array is [2, 3, 4, 7, 8]. This example shows how recursion breaks the problem into smaller sub-problems until the base case is reached.

最终排序后的数组是 [2, 3, 4, 7, 8]。这个例子展示了递归如何将问题分解为更小的子问题，直到达到基准情况。

6. Time Complexity Analysis | 时间复杂度分析

Quick sort's time complexity depends on how balanced the partitions are. In the best case, each partition splits the array into two nearly equal halves, yielding the recurrence T(n) = 2T(n/2) + O(n), which solves to O(n log n).

快速排序的时间复杂度取决于分区的平衡程度。在最好情况下，每次分区将数组分成两个几乎相等的部分，得到递推式 T(n) = 2T(n/2) + O(n)，其解为 O(n log n)。

In the average case, even with some imbalance, the expected time is still O(n log n). This is why quick sort is considered efficient for random data.

在平均情况下，即使存在一些不平衡，期望时间仍为 O(n log n)。这就是为什么快速排序对于随机数据被认为是高效的。

In the worst case, when the pivot is always the smallest or largest element (e.g., already sorted array with first or last pivot), the recurrence becomes T(n) = T(n-1) + O(n), giving O(n²).

在最坏情况下，当基准总是最小或最大元素时（例如已排序数组且以第一个或最后一个元素为基准），递推式变为 T(n) = T(n-1) + O(n)，得到 O(n²)。

The table below summarises the time complexities:

下表总结了时间复杂度：

Case	Time Complexity
Best	O(n log n)
Average	O(n log n)
Worst	O(n²)

7. Space Complexity and Recursion Depth | 空间复杂度与递归深度

Quick sort is an in-place sorting algorithm because it only requires a small, constant amount of extra memory for the pointers, apart from the recursion stack. The space complexity is O(log n) on average due to the recursion depth.

快速排序是一种原地排序算法，因为除了递归栈之外，它只需要少量、固定的额外内存用于指针。由于递归深度，平均空间复杂度为 O(log n)。

In the worst case, the recursion depth can be O(n), leading to O(n) space complexity. However, tail recursion optimisation or iterative implementation can reduce this.

在最坏情况下，递归深度可能为 O(n)，导致 O(n) 空间复杂度。然而，尾递归优化或迭代实现可以减少这一开销。

8. Stability and Adaptivity | 稳定性与自适应性

Quick sort is not a stable sorting algorithm. Equal elements may change their relative order during the partition swaps, especially with the Lomuto scheme.

快速排序不是稳定的排序算法。在分区交换过程中，相等元素的相对顺序可能会改变，尤其是在 Lomuto 方案中。

It is also not adaptive: the algorithm does not take advantage of existing order in the input. Even an already sorted array will be processed with the same recursive calls, unless a more sophisticated pivot choice is used.

它也不是自适应的：该算法不会利用输入中已有的顺序。即使是已经排序的数组，也会以相同的递归调用进行处理，除非使用更复杂的基准选择方法。

9. Quick Sort vs Merge Sort | 快速排序与归并排序比较

Both quick sort and merge sort use divide-and-conquer and have average-case O(n log n). However, quick sort is in-place and often faster in practice due to better cache performance, while merge sort requires O(n) extra space.

快速排序和归并排序都采用分治策略，平均时间复杂度均为 O(n log n)。然而，快速排序是原地排序，由于缓存性能更好，通常在实践中更快，而归并排序需要 O(n) 额外空间。

Merge sort is stable and guarantees O(n log n) even in the worst case, making it more

Published by TutorHao | A-Level Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

Quick Sort | 快速排序