📚 Quick Sort | 快速排序
Quick sort is a highly efficient, comparison-based sorting algorithm that follows the divide-and-conquer paradigm. Invented by Tony Hoare in 1959, it has become one of the most widely used sorting algorithms due to its average-case time complexity of O(n log n) and its ability to sort 'in-place' with relatively small extra memory. Quick sort works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively. This elegant approach often outperforms other O(n log n) algorithms in practice because its inner loop can be efficiently implemented on most architectures.
快速排序是一种高效的基于比较的排序算法，遵循分治范式。它由东尼·霍尔于1959年发明，因其平均时间复杂度为 O(n log n) 并能够以较小的额外内存“就地”排序，成为使用最广泛的排序算法之一。快速排序通过从数组中选择一个“枢轴”元素，然后将其他元素划分到两个子数组中（依据是小于还是大于枢轴），随后递归地对子数组进行排序。这种优雅的方法在实践中通常优于其他 O(n log n) 算法，因为其内部循环可以在大多数体系结构上高效实现。
1. Introduction to Quick Sort | 快速排序简介
Quick sort is a recursive, comparison-based sorting algorithm that operates by partitioning an array into two halves around a pivot element. Unlike merge sort, which divides the array into equal halves and merges them after sorting, quick sort reduces the problem size and then recursively sorts the left and right partitions. The key operation is the partitioning step, which rearranges elements such that all elements smaller than the pivot come before it and all larger elements come after it. This in-place characteristic saves memory and makes it a popular choice for large datasets.
快速排序是一种递归的、基于比较的排序算法，它通过围绕一个枢轴元素将数组分成两半来操作。与归并排序不同，归并排序将数组分成相等两半并在排序后合并，快速排序减小问题规模，然后递归排序左右分区。关键操作是划分步骤，它重新排列元素，使得所有小于枢轴的元素位于其前，大于的元素位于其后。这种就地特性节省了内存，使其成为大型数据集的常用选择。
2. The Divide-and-Conquer Strategy | 分治策略
Divide-and-conquer is a fundamental algorithmic technique that solves a problem by breaking it into subproblems of the same type, conquering them recursively, and then combining the results. Quick sort applies this principle: Divide the array into two (or more) sub-arrays based on a pivot; Conquer by recursively sorting the sub-arrays; Combine is trivial because the array is already sorted after the recursive calls. The base case occurs when the sub-array has zero or one element, which is already sorted. This strategy leads to a highly cache-efficient implementation.
分治是一种基本的算法技术，通过将问题分解为相同类型的子问题，递归解决这些问题，然后组合结果来求解。快速排序应用这一原则：分解：基于枢轴将数组划分为两个（或更多）子数组；解决：递归地对子数组进行排序；合并：由于递归调用后数组已排序，合并步骤很简单。基准情况是当子数组有零个或一个元素时，它已经有序。这种策略导致了高度缓存高效的实现。
3. How Quick Sort Works | 快速排序工作原理
To sort an array using quick sort, first choose a pivot element. The pivot can be any element from the array, but the choice affects performance. The algorithm then partitions the array so that elements smaller than the pivot are moved to its left, and elements greater are moved to its right. After partitioning, the pivot is in its final correct sorted position. The process is then applied recursively to the left sub-array (elements before the pivot) and the right sub-array (elements after the pivot). The recursion terminates when sub-arrays of size 0 or 1 are reached, as they are inherently sorted.
要使用快速排序对一个数组进行排序，首先选择一个枢轴元素。枢轴可以是数组中的任何元素，但选择会影响性能。然后算法对数组进行划分，使得小于枢轴的元素移到其左侧，大于的元素移到右侧。划分完成后，枢轴处于其最终的正确排序位置。接着对左侧子数组（枢轴之前的元素）和右侧子数组（枢轴之后的元素）递归应用该过程。当子数组大小为0或1时递归终止，因为它们本身已排序。
4. Partitioning Process | 划分过程
rd the centre. While the left pointer finds an element greater than or equal to the pivot and the right pointer finds an element less than or equal to the pivot, they swap the elements when both have stopped. This continues until the pointers cross. Finally, the pivot is swapped into its correct position. This method ensures that all elements to the left of the pivot are ≤ pivot and all to the right are ≥ pivot. The partition index is returned to the recursive calls.
快速排序的核心是划分函数。一种常见的实现使用两个指针或索引，从子数组的两端向中间扫描。当左指针找到一个大于或等于枢轴的元素，右指针找到一个小于或等于枢轴的元素，两者都停止时，它们交换元素。一直持续到指针交错。最后，将枢轴交换到其正确位置。这种方法确保枢轴左侧的所有元素 ≤ 枢轴，右侧的所有元素 ≥ 枢轴。划分索引返回给递归调用。
5. Pivot Selection | 枢轴选择
The choice of pivot greatly influences the performance of quick sort. Simple strategies include picking the first element, the last element, or the middle element. However, these can lead to worst-case O(n²) complexity on already sorted or nearly sorted arrays. A better strategy is to choose the pivot randomly, which gives an expected average-case O(n log n). Another common technique is 'median-of-three', where the pivot is chosen as the median of the first, middle, and last elements of the array. This reduces the probability of hitting the worst case and improves efficiency on many real-world datasets.
枢轴的选择极大地影响快速排序的性能。简单的策略包括选择第一个元素、最后一个元素或中间元素。然而，这些策略可能在已排序或接近排序的数组上导致最坏情况 O(n²) 复杂度。一种更好的策略是随机选择枢轴，这给出了预期的平均情况 O(n log n)。另一种常见技术是“三数取中法”，即选择数组第一个、中间和最后一个元素的中位数作为枢轴。这降低了达到最坏情况的概率，并提高了许多真实数据集的效率。
6. Pseudocode of Quick Sort | 快速排序伪代码
The following pseudocode illustrates a standard in-place quick sort using the last element as the pivot. The partition function returns the index where the pivot is placed. The recursive quickSort function processes the left and right sub-arrays.
下面的伪代码展示了一个标准的就地快速排序，使用最后一个元素作为枢轴。划分函数返回枢轴放置的索引。递归的 quickSort 函数处理左右子数组。
function quickSort(arr, low, high)
if low < high
pi = partition(arr, low, high)
quickSort(arr, low, pi - 1)
quickSort(arr, pi + 1, high)
function partition(arr, low, high)
pivot = arr[high]
i = low - 1
for j = low to high - 1
if arr[j] < pivot
i = i + 1
swap arr[i] with arr[j]
swap arr[i+1] with arr[high]
return i + 1
In this pseudocode, the variable i maintains the boundary of elements smaller than the pivot. The loop with j scans the array, and whenever an element smaller than the pivot is found, i is incremented and the element is swapped into the smaller region. After the loop, the pivot is swapped with the element at index i+1, placing it in the correct position. The function returns this index.
在这段伪代码中，变量 i 维护小于枢轴的元素边界。j 的循环扫描数组，每当发现一个小于枢轴的元素时，i 递增，并将该元素换入较小区域。循环结束后，枢轴与索引 i+1 处的元素交换，将其放置在正确位置。该函数返回此索引。
An alternative partitioning scheme using two pointers was described previously. Both are valid and have similar performance characteristics. Edexcel A-level students should be able to trace and implement the given pseudocode.
之前描述的使用两个指针的替代划分方案也是有效的，并且具有类似的性能特征。Edexcel A-level 学生应能够追踪和实现给定的伪代码。
7. Time Complexity Analysis | 时间复杂度分析
Quick sort's time complexity depends on the balance of the partitions. In the best-case scenario, each partition splits the array into two nearly equal halves. The recurrence relation is T(n) = 2T(n/2) + O(n), which solves to O(n log n). The average-case also yields O(n log n), even with random pivot selection, as the partitions tend to be reasonably balanced. However, in the worst-case n²). The worst case occurs on already sorted arrays when the first or last element is chosen as pivot without randomisation.
快速排序的时间复杂度取决于分区的平衡性。在最佳情况下，每次分区将数组分成两个几乎相等的两半。递推关系式为 T(n) = 2T(n/2) + O(n)，解得 O(n log n)。平均情况也给出 O(n log n)，即使使用随机枢轴选择，因为分区往往相当平衡。然而，在最坏情况下，枢轴始终是最小或最大的元素，产生一个空子数组和一个大小为 n-1 的子数组。这导致 T(n) = T(n-1) + O(n)，即 O(n²)。当选择第一个或最后一个元素作为枢轴且数组已排序时，会出现最坏情况。
8. Space Complexity and Stability | 空间复杂度与稳定性
Quick sort is an in-place algorithm when implemented with careful swapping; its space complexity is generally O(log n) due to the recursive call stack. In the worst case, the recursion depth can become O(n) with highly unbalanced partitions, but this can be mitigated by always recursively sorting the smaller partition first or using tail recursion elimination. Quick sort is not stable in its typical in-place implementations because elements with equal keys may change their relative order during partitioning. Stability can be achieved by using extra space (e.g., stable partitioning) but that increases space usage.
快速排序在仔细交换实现时是一种就地算法；其空间复杂度通常为 O(log n)，因为递归调用栈。在最坏情况下，递归深度可能变为 O(n)，分区高度不平衡时会发生，但可以通过始终先递归排序较小的分区或使用尾递归消除来缓解。在其典型的就地实现中，快速排序是不稳定的，因为具有相等键的元素在划分过程中可能改变其相对顺序。可以通过使用额外空间（例如稳定划分）来实现稳定性，但这会增加空间使用量。
9. Best, Average, and Worst Cases | 最佳、平均和最差情况
The table below summarises the time complexities for quick sort under different scenarios:
下表总结了不同情况下快速排序的时间复杂度：
| Case | Time Complexity | Condition |
|---|---|---|
| Best | O(n log n) | Balanced partitions (each ≈ n/2) |
| Average | O(n log n) | Random pivot, typical data |
| Worst | O(n²) | Unbalanced partitions (pivot is min/max every time) |
In practice, the worst-case behaviour can be avoided by using randomised pivots or median-of-three selection. For exam purposes, you must be able to identify which choice of pivot leads to the worst case on a given dataset. For example, choosing the first element as pivot on an already sorted ascending array yields the worst case.
在实践中，通过使用随机化枢轴或三数取中法选择可以避免最坏情况行为。出于考试目的，你必须能够识别哪种枢轴选择在给定数据集上导致最坏情况。例如，在已按升序排序的数组上选择第一个元素作为枢轴会产生
Published by TutorHao | A-Level Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图