11.5 Quick sort¶
Quick sort is a sorting algorithm based on the divide and conquer strategy, known for its efficiency and wide application.
The core operation of quick sort is "pivot partitioning," aiming to: select an element from the array as the "pivot," move all elements smaller than the pivot to its left, and move elements greater than the pivot to its right. Specifically, the pivot partitioning process is illustrated as follows.
- Select the leftmost element of the array as the pivot, and initialize two pointers
iandjat both ends of the array. - Set up a loop where each round uses
i(j) to find the first element larger (smaller) than the pivot, then swap these two elements. - Repeat step
2.untiliandjmeet, finally swap the pivot to the boundary between the two sub-arrays.
Figure 11-8 Pivot division process
After the pivot partitioning, the original array is divided into three parts: left sub-array, pivot, and right sub-array, satisfying "any element in the left sub-array \(\leq\) pivot \(\leq\) any element in the right sub-array." Therefore, we only need to sort these two sub-arrays next.
Quick sort's divide and conquer strategy
The essence of pivot partitioning is to simplify a longer array's sorting problem into two shorter arrays' sorting problems.
quick_sort.py
def partition(self, nums: list[int], left: int, right: int) -> int:
"""哨兵划分"""
# 以 nums[left] 为基准数
i, j = left, right
while i < j:
while i < j and nums[j] >= nums[left]:
j -= 1 # 从右向左找首个小于基准数的元素
while i < j and nums[i] <= nums[left]:
i += 1 # 从左向右找首个大于基准数的元素
# 元素交换
nums[i], nums[j] = nums[j], nums[i]
# 将基准数交换至两子数组的分界线
nums[i], nums[left] = nums[left], nums[i]
return i # 返回基准数的索引
quick_sort.cpp
/* 元素交换 */
void swap(vector<int> &nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
/* 哨兵划分 */
int partition(vector<int> &nums, int left, int right) {
// 以 nums[left] 为基准数
int i = left, j = right;
while (i < j) {
while (i < j && nums[j] >= nums[left])
j--; // 从右向左找首个小于基准数的元素
while (i < j && nums[i] <= nums[left])
i++; // 从左向右找首个大于基准数的元素
swap(nums, i, j); // 交换这两个元素
}
swap(nums, i, left); // 将基准数交换至两子数组的分界线
return i; // 返回基准数的索引
}
quick_sort.java
/* 元素交换 */
void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
/* 哨兵划分 */
int partition(int[] nums, int left, int right) {
// 以 nums[left] 为基准数
int i = left, j = right;
while (i < j) {
while (i < j && nums[j] >= nums[left])
j--; // 从右向左找首个小于基准数的元素
while (i < j && nums[i] <= nums[left])
i++; // 从左向右找首个大于基准数的元素
swap(nums, i, j); // 交换这两个元素
}
swap(nums, i, left); // 将基准数交换至两子数组的分界线
return i; // 返回基准数的索引
}
quick_sort.cs
/* 元素交换 */
void Swap(int[] nums, int i, int j) {
(nums[j], nums[i]) = (nums[i], nums[j]);
}
/* 哨兵划分 */
int Partition(int[] nums, int left, int right) {
// 以 nums[left] 为基准数
int i = left, j = right;
while (i < j) {
while (i < j && nums[j] >= nums[left])
j--; // 从右向左找首个小于基准数的元素
while (i < j && nums[i] <= nums[left])
i++; // 从左向右找首个大于基准数的元素
Swap(nums, i, j); // 交换这两个元素
}
Swap(nums, i, left); // 将基准数交换至两子数组的分界线
return i; // 返回基准数的索引
}
quick_sort.go
/* 哨兵划分 */
func (q *quickSort) partition(nums []int, left, right int) int {
// 以 nums[left] 为基准数
i, j := left, right
for i < j {
for i < j && nums[j] >= nums[left] {
j-- // 从右向左找首个小于基准数的元素
}
for i < j && nums[i] <= nums[left] {
i++ // 从左向右找首个大于基准数的元素
}
// 元素交换
nums[i], nums[j] = nums[j], nums[i]
}
// 将基准数交换至两子数组的分界线
nums[i], nums[left] = nums[left], nums[i]
return i // 返回基准数的索引
}
quick_sort.swift
/* 哨兵划分 */
func partition(nums: inout [Int], left: Int, right: Int) -> Int {
// 以 nums[left] 为基准数
var i = left
var j = right
while i < j {
while i < j, nums[j] >= nums[left] {
j -= 1 // 从右向左找首个小于基准数的元素
}
while i < j, nums[i] <= nums[left] {
i += 1 // 从左向右找首个大于基准数的元素
}
nums.swapAt(i, j) // 交换这两个元素
}
nums.swapAt(i, left) // 将基准数交换至两子数组的分界线
return i // 返回基准数的索引
}
quick_sort.js
/* 元素交换 */
swap(nums, i, j) {
let tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
/* 哨兵划分 */
partition(nums, left, right) {
// 以 nums[left] 为基准数
let i = left,
j = right;
while (i < j) {
while (i < j && nums[j] >= nums[left]) {
j -= 1; // 从右向左找首个小于基准数的元素
}
while (i < j && nums[i] <= nums[left]) {
i += 1; // 从左向右找首个大于基准数的元素
}
// 元素交换
this.swap(nums, i, j); // 交换这两个元素
}
this.swap(nums, i, left); // 将基准数交换至两子数组的分界线
return i; // 返回基准数的索引
}
quick_sort.ts
/* 元素交换 */
swap(nums: number[], i: number, j: number): void {
let tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
/* 哨兵划分 */
partition(nums: number[], left: number, right: number): number {
// 以 nums[left] 为基准数
let i = left,
j = right;
while (i < j) {
while (i < j && nums[j] >= nums[left]) {
j -= 1; // 从右向左找首个小于基准数的元素
}
while (i < j && nums[i] <= nums[left]) {
i += 1; // 从左向右找首个大于基准数的元素
}
// 元素交换
this.swap(nums, i, j); // 交换这两个元素
}
this.swap(nums, i, left); // 将基准数交换至两子数组的分界线
return i; // 返回基准数的索引
}
quick_sort.dart
/* 元素交换 */
void _swap(List<int> nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
/* 哨兵划分 */
int _partition(List<int> nums, int left, int right) {
// 以 nums[left] 为基准数
int i = left, j = right;
while (i < j) {
while (i < j && nums[j] >= nums[left]) j--; // 从右向左找首个小于基准数的元素
while (i < j && nums[i] <= nums[left]) i++; // 从左向右找首个大于基准数的元素
_swap(nums, i, j); // 交换这两个元素
}
_swap(nums, i, left); // 将基准数交换至两子数组的分界线
return i; // 返回基准数的索引
}
quick_sort.rs
/* 哨兵划分 */
fn partition(nums: &mut [i32], left: usize, right: usize) -> usize {
// 以 nums[left] 为基准数
let (mut i, mut j) = (left, right);
while i < j {
while i < j && nums[j] >= nums[left] {
j -= 1; // 从右向左找首个小于基准数的元素
}
while i < j && nums[i] <= nums[left] {
i += 1; // 从左向右找首个大于基准数的元素
}
nums.swap(i, j); // 交换这两个元素
}
nums.swap(i, left); // 将基准数交换至两子数组的分界线
i // 返回基准数的索引
}
quick_sort.c
/* 元素交换 */
void swap(int nums[], int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
/* 哨兵划分 */
int partition(int nums[], int left, int right) {
// 以 nums[left] 为基准数
int i = left, j = right;
while (i < j) {
while (i < j && nums[j] >= nums[left]) {
j--; // 从右向左找首个小于基准数的元素
}
while (i < j && nums[i] <= nums[left]) {
i++; // 从左向右找首个大于基准数的元素
}
// 交换这两个元素
swap(nums, i, j);
}
// 将基准数交换至两子数组的分界线
swap(nums, i, left);
// 返回基准数的索引
return i;
}
quick_sort.kt
/* 元素交换 */
fun swap(nums: IntArray, i: Int, j: Int) {
val temp = nums[i]
nums[i] = nums[j]
nums[j] = temp
}
/* 哨兵划分 */
fun partition(nums: IntArray, left: Int, right: Int): Int {
// 以 nums[left] 为基准数
var i = left
var j = right
while (i < j) {
while (i < j && nums[j] >= nums[left])
j-- // 从右向左找首个小于基准数的元素
while (i < j && nums[i] <= nums[left])
i++ // 从左向右找首个大于基准数的元素
swap(nums, i, j) // 交换这两个元素
}
swap(nums, i, left) // 将基准数交换至两子数组的分界线
return i // 返回基准数的索引
}
quick_sort.zig
// 元素交换
fn swap(nums: []i32, i: usize, j: usize) void {
var tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
// 哨兵划分
fn partition(nums: []i32, left: usize, right: usize) usize {
// 以 nums[left] 为基准数
var i = left;
var j = right;
while (i < j) {
while (i < j and nums[j] >= nums[left]) j -= 1; // 从右向左找首个小于基准数的元素
while (i < j and nums[i] <= nums[left]) i += 1; // 从左向右找首个大于基准数的元素
swap(nums, i, j); // 交换这两个元素
}
swap(nums, i, left); // 将基准数交换至两子数组的分界线
return i; // 返回基准数的索引
}
Code Visualization
11.5.1 Algorithm process¶
The overall process of quick sort is shown in Figure 11-9.
- First, perform a "pivot partitioning" on the original array to obtain the unsorted left and right sub-arrays.
- Then, recursively perform "pivot partitioning" on both the left and right sub-arrays.
- Continue recursively until the sub-array length reaches 1, thus completing the sorting of the entire array.
Figure 11-9 Quick sort process
quick_sort.swift
/* 快速排序 */
func quickSort(nums: inout [Int], left: Int, right: Int) {
// 子数组长度为 1 时终止递归
if left >= right {
return
}
// 哨兵划分
let pivot = partition(nums: &nums, left: left, right: right)
// 递归左子数组、右子数组
quickSort(nums: &nums, left: left, right: pivot - 1)
quickSort(nums: &nums, left: pivot + 1, right: right)
}
quick_sort.rs
/* 快速排序 */
pub fn quick_sort(left: i32, right: i32, nums: &mut [i32]) {
// 子数组长度为 1 时终止递归
if left >= right {
return;
}
// 哨兵划分
let pivot = Self::partition(nums, left as usize, right as usize) as i32;
// 递归左子数组、右子数组
Self::quick_sort(left, pivot - 1, nums);
Self::quick_sort(pivot + 1, right, nums);
}
Code Visualization
11.5.2 Algorithm features¶
- Time complexity of \(O(n \log n)\), adaptive sorting: In average cases, the recursive levels of pivot partitioning are \(\log n\), and the total number of loops per level is \(n\), using \(O(n \log n)\) time overall. In the worst case, each round of pivot partitioning divides an array of length \(n\) into two sub-arrays of lengths \(0\) and \(n - 1\), reaching \(n\) recursive levels, and using \(O(n^2)\) time overall.
- Space complexity of \(O(n)\), in-place sorting: In completely reversed input arrays, reaching the worst recursion depth of \(n\), using \(O(n)\) stack frame space. The sorting operation is performed on the original array without the aid of additional arrays.
- Non-stable sorting: In the final step of pivot partitioning, the pivot may be swapped to the right of equal elements.
11.5.3 Why is quick sort fast¶
From its name, it is apparent that quick sort should have certain efficiency advantages. Although the average time complexity of quick sort is the same as "merge sort" and "heap sort," quick sort is generally more efficient, mainly for the following reasons.
- Low probability of worst-case scenarios: Although the worst time complexity of quick sort is \(O(n^2)\), less stable than merge sort, in most cases, quick sort can operate under a time complexity of \(O(n \log n)\).
- High cache usage efficiency: During the pivot partitioning operation, the system can load the entire sub-array into the cache, thus accessing elements more efficiently. In contrast, algorithms like "heap sort" need to access elements in a jumping manner, lacking this feature.
- Small constant coefficient of complexity: Among the mentioned algorithms, quick sort has the fewest total number of comparisons, assignments, and swaps. This is similar to why "insertion sort" is faster than "bubble sort."
11.5.4 Pivot optimization¶
Quick sort's time efficiency may decrease under certain inputs. For example, if the input array is completely reversed, since we select the leftmost element as the pivot, after the pivot partitioning, the pivot is swapped to the array's right end, causing the left sub-array length to be \(n - 1\) and the right sub-array length to be \(0\). If this recursion continues, each round of pivot partitioning will have a sub-array length of \(0\), and the divide and conquer strategy fails, degrading quick sort to a form similar to "bubble sort."
To avoid this situation, we can optimize the strategy for selecting the pivot in the pivot partitioning. For instance, we can randomly select an element as the pivot. However, if luck is not on our side, and we keep selecting suboptimal pivots, the efficiency is still not satisfactory.
It's important to note that programming languages usually generate "pseudo-random numbers". If we construct a specific test case for a pseudo-random number sequence, the efficiency of quick sort may still degrade.
For further improvement, we can select three candidate elements (usually the first, last, and midpoint elements of the array), and use the median of these three candidate elements as the pivot. This significantly increases the probability that the pivot is "neither too small nor too large". Of course, we can also select more candidate elements to further enhance the algorithm's robustness. Using this method significantly reduces the probability of time complexity degradation to \(O(n^2)\).
Sample code is as follows:
quick_sort.py
def median_three(self, nums: list[int], left: int, mid: int, right: int) -> int:
"""选取三个候选元素的中位数"""
l, m, r = nums[left], nums[mid], nums[right]
if (l <= m <= r) or (r <= m <= l):
return mid # m 在 l 和 r 之间
if (m <= l <= r) or (r <= l <= m):
return left # l 在 m 和 r 之间
return right
def partition(self, nums: list[int], left: int, right: int) -> int:
"""哨兵划分（三数取中值）"""
# 以 nums[left] 为基准数
med = self.median_three(nums, left, (left + right) // 2, right)
# 将中位数交换至数组最左端
nums[left], nums[med] = nums[med], nums[left]
# 以 nums[left] 为基准数
i, j = left, right
while i < j:
while i < j and nums[j] >= nums[left]:
j -= 1 # 从右向左找首个小于基准数的元素
while i < j and nums[i] <= nums[left]:
i += 1 # 从左向右找首个大于基准数的元素
# 元素交换
nums[i], nums[j] = nums[j], nums[i]
# 将基准数交换至两子数组的分界线
nums[i], nums[left] = nums[left], nums[i]
return i # 返回基准数的索引
quick_sort.cpp
/* 选取三个候选元素的中位数 */
int medianThree(vector<int> &nums, int left, int mid, int right) {
int l = nums[left], m = nums[mid], r = nums[right];
if ((l <= m && m <= r) || (r <= m && m <= l))
return mid; // m 在 l 和 r 之间
if ((m <= l && l <= r) || (r <= l && l <= m))
return left; // l 在 m 和 r 之间
return right;
}
/* 哨兵划分（三数取中值） */
int partition(vector<int> &nums, int left, int right) {
// 选取三个候选元素的中位数
int med = medianThree(nums, left, (left + right) / 2, right);
// 将中位数交换至数组最左端
swap(nums, left, med);
// 以 nums[left] 为基准数
int i = left, j = right;
while (i < j) {
while (i < j && nums[j] >= nums[left])
j--; // 从右向左找首个小于基准数的元素
while (i < j && nums[i] <= nums[left])
i++; // 从左向右找首个大于基准数的元素
swap(nums, i, j); // 交换这两个元素
}
swap(nums, i, left); // 将基准数交换至两子数组的分界线
return i; // 返回基准数的索引
}
quick_sort.java
/* 选取三个候选元素的中位数 */
int medianThree(int[] nums, int left, int mid, int right) {
int l = nums[left], m = nums[mid], r = nums[right];
if ((l <= m && m <= r) || (r <= m && m <= l))
return mid; // m 在 l 和 r 之间
if ((m <= l && l <= r) || (r <= l && l <= m))
return left; // l 在 m 和 r 之间
return right;
}
/* 哨兵划分（三数取中值） */
int partition(int[] nums, int left, int right) {
// 选取三个候选元素的中位数
int med = medianThree(nums, left, (left + right) / 2, right);
// 将中位数交换至数组最左端
swap(nums, left, med);
// 以 nums[left] 为基准数
int i = left, j = right;
while (i < j) {
while (i < j && nums[j] >= nums[left])
j--; // 从右向左找首个小于基准数的元素
while (i < j && nums[i] <= nums[left])
i++; // 从左向右找首个大于基准数的元素
swap(nums, i, j); // 交换这两个元素
}
swap(nums, i, left); // 将基准数交换至两子数组的分界线
return i; // 返回基准数的索引
}
quick_sort.cs
/* 选取三个候选元素的中位数 */
int MedianThree(int[] nums, int left, int mid, int right) {
int l = nums[left], m = nums[mid], r = nums[right];
if ((l <= m && m <= r) || (r <= m && m <= l))
return mid; // m 在 l 和 r 之间
if ((m <= l && l <= r) || (r <= l && l <= m))
return left; // l 在 m 和 r 之间
return right;
}
/* 哨兵划分（三数取中值） */
int Partition(int[] nums, int left, int right) {
// 选取三个候选元素的中位数
int med = MedianThree(nums, left, (left + right) / 2, right);
// 将中位数交换至数组最左端
Swap(nums, left, med);
// 以 nums[left] 为基准数
int i = left, j = right;
while (i < j) {
while (i < j && nums[j] >= nums[left])
j--; // 从右向左找首个小于基准数的元素
while (i < j && nums[i] <= nums[left])
i++; // 从左向右找首个大于基准数的元素
Swap(nums, i, j); // 交换这两个元素
}
Swap(nums, i, left); // 将基准数交换至两子数组的分界线
return i; // 返回基准数的索引
}
quick_sort.go
/* 选取三个候选元素的中位数 */
func (q *quickSortMedian) medianThree(nums []int, left, mid, right int) int {
l, m, r := nums[left], nums[mid], nums[right]
if (l <= m && m <= r) || (r <= m && m <= l) {
return mid // m 在 l 和 r 之间
}
if (m <= l && l <= r) || (r <= l && l <= m) {
return left // l 在 m 和 r 之间
}
return right
}
/* 哨兵划分（三数取中值）*/
func (q *quickSortMedian) partition(nums []int, left, right int) int {
// 以 nums[left] 为基准数
med := q.medianThree(nums, left, (left+right)/2, right)
// 将中位数交换至数组最左端
nums[left], nums[med] = nums[med], nums[left]
// 以 nums[left] 为基准数
i, j := left, right
for i < j {
for i < j && nums[j] >= nums[left] {
j-- //从右向左找首个小于基准数的元素
}
for i < j && nums[i] <= nums[left] {
i++ //从左向右找首个大于基准数的元素
}
//元素交换
nums[i], nums[j] = nums[j], nums[i]
}
//将基准数交换至两子数组的分界线
nums[i], nums[left] = nums[left], nums[i]
return i //返回基准数的索引
}
quick_sort.swift
/* 选取三个候选元素的中位数 */
func medianThree(nums: [Int], left: Int, mid: Int, right: Int) -> Int {
let l = nums[left]
let m = nums[mid]
let r = nums[right]
if (l <= m && m <= r) || (r <= m && m <= l) {
return mid // m 在 l 和 r 之间
}
if (m <= l && l <= r) || (r <= l && l <= m) {
return left // l 在 m 和 r 之间
}
return right
}
/* 哨兵划分（三数取中值） */
func partitionMedian(nums: inout [Int], left: Int, right: Int) -> Int {
// 选取三个候选元素的中位数
let med = medianThree(nums: nums, left: left, mid: (left + right) / 2, right: right)
// 将中位数交换至数组最左端
nums.swapAt(left, med)
return partition(nums: &nums, left: left, right: right)
}
quick_sort.js
/* 选取三个候选元素的中位数 */
medianThree(nums, left, mid, right) {
let l = nums[left],
m = nums[mid],
r = nums[right];
// m 在 l 和 r 之间
if ((l <= m && m <= r) || (r <= m && m <= l)) return mid;
// l 在 m 和 r 之间
if ((m <= l && l <= r) || (r <= l && l <= m)) return left;
return right;
}
/* 哨兵划分（三数取中值） */
partition(nums, left, right) {
// 选取三个候选元素的中位数
let med = this.medianThree(
nums,
left,
Math.floor((left + right) / 2),
right
);
// 将中位数交换至数组最左端
this.swap(nums, left, med);
// 以 nums[left] 为基准数
let i = left,
j = right;
while (i < j) {
while (i < j && nums[j] >= nums[left]) j--; // 从右向左找首个小于基准数的元素
while (i < j && nums[i] <= nums[left]) i++; // 从左向右找首个大于基准数的元素
this.swap(nums, i, j); // 交换这两个元素
}
this.swap(nums, i, left); // 将基准数交换至两子数组的分界线
return i; // 返回基准数的索引
}
quick_sort.ts
/* 选取三个候选元素的中位数 */
medianThree(
nums: number[],
left: number,
mid: number,
right: number
): number {
let l = nums[left],
m = nums[mid],
r = nums[right];
// m 在 l 和 r 之间
if ((l <= m && m <= r) || (r <= m && m <= l)) return mid;
// l 在 m 和 r 之间
if ((m <= l && l <= r) || (r <= l && l <= m)) return left;
return right;
}
/* 哨兵划分（三数取中值） */
partition(nums: number[], left: number, right: number): number {
// 选取三个候选元素的中位数
let med = this.medianThree(
nums,
left,
Math.floor((left + right) / 2),
right
);
// 将中位数交换至数组最左端
this.swap(nums, left, med);
// 以 nums[left] 为基准数
let i = left,
j = right;
while (i < j) {
while (i < j && nums[j] >= nums[left]) {
j--; // 从右向左找首个小于基准数的元素
}
while (i < j && nums[i] <= nums[left]) {
i++; // 从左向右找首个大于基准数的元素
}
this.swap(nums, i, j); // 交换这两个元素
}
this.swap(nums, i, left); // 将基准数交换至两子数组的分界线
return i; // 返回基准数的索引
}
quick_sort.dart
/* 选取三个候选元素的中位数 */
int _medianThree(List<int> nums, int left, int mid, int right) {
int l = nums[left], m = nums[mid], r = nums[right];
if ((l <= m && m <= r) || (r <= m && m <= l))
return mid; // m 在 l 和 r 之间
if ((m <= l && l <= r) || (r <= l && l <= m))
return left; // l 在 m 和 r 之间
return right;
}
/* 哨兵划分（三数取中值） */
int _partition(List<int> nums, int left, int right) {
// 选取三个候选元素的中位数
int med = _medianThree(nums, left, (left + right) ~/ 2, right);
// 将中位数交换至数组最左端
_swap(nums, left, med);
// 以 nums[left] 为基准数
int i = left, j = right;
while (i < j) {
while (i < j && nums[j] >= nums[left]) j--; // 从右向左找首个小于基准数的元素
while (i < j && nums[i] <= nums[left]) i++; // 从左向右找首个大于基准数的元素
_swap(nums, i, j); // 交换这两个元素
}
_swap(nums, i, left); // 将基准数交换至两子数组的分界线
return i; // 返回基准数的索引
}
quick_sort.rs
/* 选取三个候选元素的中位数 */
fn median_three(nums: &mut [i32], left: usize, mid: usize, right: usize) -> usize {
let (l, m, r) = (nums[left], nums[mid], nums[right]);
if (l <= m && m <= r) || (r <= m && m <= l) {
return mid; // m 在 l 和 r 之间
}
if (m <= l && l <= r) || (r <= l && l <= m) {
return left; // l 在 m 和 r 之间
}
right
}
/* 哨兵划分（三数取中值） */
fn partition(nums: &mut [i32], left: usize, right: usize) -> usize {
// 选取三个候选元素的中位数
let med = Self::median_three(nums, left, (left + right) / 2, right);
// 将中位数交换至数组最左端
nums.swap(left, med);
// 以 nums[left] 为基准数
let (mut i, mut j) = (left, right);
while i < j {
while i < j && nums[j] >= nums[left] {
j -= 1; // 从右向左找首个小于基准数的元素
}
while i < j && nums[i] <= nums[left] {
i += 1; // 从左向右找首个大于基准数的元素
}
nums.swap(i, j); // 交换这两个元素
}
nums.swap(i, left); // 将基准数交换至两子数组的分界线
i // 返回基准数的索引
}
quick_sort.c
/* 选取三个候选元素的中位数 */
int medianThree(int nums[], int left, int mid, int right) {
int l = nums[left], m = nums[mid], r = nums[right];
if ((l <= m && m <= r) || (r <= m && m <= l))
return mid; // m 在 l 和 r 之间
if ((m <= l && l <= r) || (r <= l && l <= m))
return left; // l 在 m 和 r 之间
return right;
}
/* 哨兵划分（三数取中值） */
int partitionMedian(int nums[], int left, int right) {
// 选取三个候选元素的中位数
int med = medianThree(nums, left, (left + right) / 2, right);
// 将中位数交换至数组最左端
swap(nums, left, med);
// 以 nums[left] 为基准数
int i = left, j = right;
while (i < j) {
while (i < j && nums[j] >= nums[left])
j--; // 从右向左找首个小于基准数的元素
while (i < j && nums[i] <= nums[left])
i++; // 从左向右找首个大于基准数的元素
swap(nums, i, j); // 交换这两个元素
}
swap(nums, i, left); // 将基准数交换至两子数组的分界线
return i; // 返回基准数的索引
}
quick_sort.kt
/* 选取三个候选元素的中位数 */
fun medianThree(nums: IntArray, left: Int, mid: Int, right: Int): Int {
val l = nums[left]
val m = nums[mid]
val r = nums[right]
if ((m in l..r) || (m in r..l))
return mid // m 在 l 和 r 之间
if ((l in m..r) || (l in r..m))
return left // l 在 m 和 r 之间
return right
}
/* 哨兵划分（三数取中值） */
fun partitionMedian(nums: IntArray, left: Int, right: Int): Int {
// 选取三个候选元素的中位数
val med = medianThree(nums, left, (left + right) / 2, right)
// 将中位数交换至数组最左端
swap(nums, left, med)
// 以 nums[left] 为基准数
var i = left
var j = right
while (i < j) {
while (i < j && nums[j] >= nums[left])
j-- // 从右向左找首个小于基准数的元素
while (i < j && nums[i] <= nums[left])
i++ // 从左向右找首个大于基准数的元素
swap(nums, i, j) // 交换这两个元素
}
swap(nums, i, left) // 将基准数交换至两子数组的分界线
return i // 返回基准数的索引
}
quick_sort.zig
// 选取三个候选元素的中位数
fn medianThree(nums: []i32, left: usize, mid: usize, right: usize) usize {
var l = nums[left];
var m = nums[mid];
var r = nums[right];
if ((l <= m && m <= r) || (r <= m && m <= l))
return mid; // m 在 l 和 r 之间
if ((m <= l && l <= r) || (r <= l && l <= m))
return left; // l 在 m 和 r 之间
return right;
}
// 哨兵划分（三数取中值）
fn partition(nums: []i32, left: usize, right: usize) usize {
// 选取三个候选元素的中位数
var med = medianThree(nums, left, (left + right) / 2, right);
// 将中位数交换至数组最左端
swap(nums, left, med);
// 以 nums[left] 为基准数
var i = left;
var j = right;
while (i < j) {
while (i < j and nums[j] >= nums[left]) j -= 1; // 从右向左找首个小于基准数的元素
while (i < j and nums[i] <= nums[left]) i += 1; // 从左向右找首个大于基准数的元素
swap(nums, i, j); // 交换这两个元素
}
swap(nums, i, left); // 将基准数交换至两子数组的分界线
return i; // 返回基准数的索引
}
Code Visualization
11.5.5 Tail recursion optimization¶
Under certain inputs, quick sort may occupy more space. For a completely ordered input array, assume the sub-array length in recursion is \(m\), each round of pivot partitioning produces a left sub-array of length \(0\) and a right sub-array of length \(m - 1\), meaning the problem size reduced per recursive call is very small (only one element), and the height of the recursion tree can reach \(n - 1\), requiring \(O(n)\) stack frame space.
To prevent the accumulation of stack frame space, we can compare the lengths of the two sub-arrays after each round of pivot sorting, and only recursively sort the shorter sub-array. Since the length of the shorter sub-array will not exceed \(n / 2\), this method ensures that the recursion depth does not exceed \(\log n\), thus optimizing the worst space complexity to \(O(\log n)\). The code is as follows:
quick_sort.py
def quick_sort(self, nums: list[int], left: int, right: int):
"""快速排序（尾递归优化）"""
# 子数组长度为 1 时终止
while left < right:
# 哨兵划分操作
pivot = self.partition(nums, left, right)
# 对两个子数组中较短的那个执行快速排序
if pivot - left < right - pivot:
self.quick_sort(nums, left, pivot - 1) # 递归排序左子数组
left = pivot + 1 # 剩余未排序区间为 [pivot + 1, right]
else:
self.quick_sort(nums, pivot + 1, right) # 递归排序右子数组
right = pivot - 1 # 剩余未排序区间为 [left, pivot - 1]
quick_sort.cpp
/* 快速排序（尾递归优化） */
void quickSort(vector<int> &nums, int left, int right) {
// 子数组长度为 1 时终止
while (left < right) {
// 哨兵划分操作
int pivot = partition(nums, left, right);
// 对两个子数组中较短的那个执行快速排序
if (pivot - left < right - pivot) {
quickSort(nums, left, pivot - 1); // 递归排序左子数组
left = pivot + 1; // 剩余未排序区间为 [pivot + 1, right]
} else {
quickSort(nums, pivot + 1, right); // 递归排序右子数组
right = pivot - 1; // 剩余未排序区间为 [left, pivot - 1]
}
}
}
quick_sort.java
/* 快速排序（尾递归优化） */
void quickSort(int[] nums, int left, int right) {
// 子数组长度为 1 时终止
while (left < right) {
// 哨兵划分操作
int pivot = partition(nums, left, right);
// 对两个子数组中较短的那个执行快速排序
if (pivot - left < right - pivot) {
quickSort(nums, left, pivot - 1); // 递归排序左子数组
left = pivot + 1; // 剩余未排序区间为 [pivot + 1, right]
} else {
quickSort(nums, pivot + 1, right); // 递归排序右子数组
right = pivot - 1; // 剩余未排序区间为 [left, pivot - 1]
}
}
}
quick_sort.cs
/* 快速排序（尾递归优化） */
void QuickSort(int[] nums, int left, int right) {
// 子数组长度为 1 时终止
while (left < right) {
// 哨兵划分操作
int pivot = Partition(nums, left, right);
// 对两个子数组中较短的那个执行快速排序
if (pivot - left < right - pivot) {
QuickSort(nums, left, pivot - 1); // 递归排序左子数组
left = pivot + 1; // 剩余未排序区间为 [pivot + 1, right]
} else {
QuickSort(nums, pivot + 1, right); // 递归排序右子数组
right = pivot - 1; // 剩余未排序区间为 [left, pivot - 1]
}
}
}
quick_sort.go
/* 快速排序（尾递归优化）*/
func (q *quickSortTailCall) quickSort(nums []int, left, right int) {
// 子数组长度为 1 时终止
for left < right {
// 哨兵划分操作
pivot := q.partition(nums, left, right)
// 对两个子数组中较短的那个执行快速排序
if pivot-left < right-pivot {
q.quickSort(nums, left, pivot-1) // 递归排序左子数组
left = pivot + 1 // 剩余未排序区间为 [pivot + 1, right]
} else {
q.quickSort(nums, pivot+1, right) // 递归排序右子数组
right = pivot - 1 // 剩余未排序区间为 [left, pivot - 1]
}
}
}
quick_sort.swift
/* 快速排序（尾递归优化） */
func quickSortTailCall(nums: inout [Int], left: Int, right: Int) {
var left = left
var right = right
// 子数组长度为 1 时终止
while left < right {
// 哨兵划分操作
let pivot = partition(nums: &nums, left: left, right: right)
// 对两个子数组中较短的那个执行快速排序
if (pivot - left) < (right - pivot) {
quickSortTailCall(nums: &nums, left: left, right: pivot - 1) // 递归排序左子数组
left = pivot + 1 // 剩余未排序区间为 [pivot + 1, right]
} else {
quickSortTailCall(nums: &nums, left: pivot + 1, right: right) // 递归排序右子数组
right = pivot - 1 // 剩余未排序区间为 [left, pivot - 1]
}
}
}
quick_sort.js
/* 快速排序（尾递归优化） */
quickSort(nums, left, right) {
// 子数组长度为 1 时终止
while (left < right) {
// 哨兵划分操作
let pivot = this.partition(nums, left, right);
// 对两个子数组中较短的那个执行快速排序
if (pivot - left < right - pivot) {
this.quickSort(nums, left, pivot - 1); // 递归排序左子数组
left = pivot + 1; // 剩余未排序区间为 [pivot + 1, right]
} else {
this.quickSort(nums, pivot + 1, right); // 递归排序右子数组
right = pivot - 1; // 剩余未排序区间为 [left, pivot - 1]
}
}
}
quick_sort.ts
/* 快速排序（尾递归优化） */
quickSort(nums: number[], left: number, right: number): void {
// 子数组长度为 1 时终止
while (left < right) {
// 哨兵划分操作
let pivot = this.partition(nums, left, right);
// 对两个子数组中较短的那个执行快速排序
if (pivot - left < right - pivot) {
this.quickSort(nums, left, pivot - 1); // 递归排序左子数组
left = pivot + 1; // 剩余未排序区间为 [pivot + 1, right]
} else {
this.quickSort(nums, pivot + 1, right); // 递归排序右子数组
right = pivot - 1; // 剩余未排序区间为 [left, pivot - 1]
}
}
}
quick_sort.dart
/* 快速排序（尾递归优化） */
void quickSort(List<int> nums, int left, int right) {
// 子数组长度为 1 时终止
while (left < right) {
// 哨兵划分操作
int pivot = _partition(nums, left, right);
// 对两个子数组中较短的那个执行快速排序
if (pivot - left < right - pivot) {
quickSort(nums, left, pivot - 1); // 递归排序左子数组
left = pivot + 1; // 剩余未排序区间为 [pivot + 1, right]
} else {
quickSort(nums, pivot + 1, right); // 递归排序右子数组
right = pivot - 1; // 剩余未排序区间为 [left, pivot - 1]
}
}
}
quick_sort.rs
/* 快速排序（尾递归优化） */
pub fn quick_sort(mut left: i32, mut right: i32, nums: &mut [i32]) {
// 子数组长度为 1 时终止
while left < right {
// 哨兵划分操作
let pivot = Self::partition(nums, left as usize, right as usize) as i32;
// 对两个子数组中较短的那个执行快速排序
if pivot - left < right - pivot {
Self::quick_sort(left, pivot - 1, nums); // 递归排序左子数组
left = pivot + 1; // 剩余未排序区间为 [pivot + 1, right]
} else {
Self::quick_sort(pivot + 1, right, nums); // 递归排序右子数组
right = pivot - 1; // 剩余未排序区间为 [left, pivot - 1]
}
}
}
quick_sort.c
/* 快速排序（尾递归优化） */
void quickSortTailCall(int nums[], int left, int right) {
// 子数组长度为 1 时终止
while (left < right) {
// 哨兵划分操作
int pivot = partition(nums, left, right);
// 对两个子数组中较短的那个执行快速排序
if (pivot - left < right - pivot) {
// 递归排序左子数组
quickSortTailCall(nums, left, pivot - 1);
// 剩余未排序区间为 [pivot + 1, right]
left = pivot + 1;
} else {
// 递归排序右子数组
quickSortTailCall(nums, pivot + 1, right);
// 剩余未排序区间为 [left, pivot - 1]
right = pivot - 1;
}
}
}
quick_sort.kt
/* 快速排序（尾递归优化） */
fun quickSortTailCall(nums: IntArray, left: Int, right: Int) {
// 子数组长度为 1 时终止
var l = left
var r = right
while (l < r) {
// 哨兵划分操作
val pivot = partition(nums, l, r)
// 对两个子数组中较短的那个执行快速排序
if (pivot - l < r - pivot) {
quickSort(nums, l, pivot - 1) // 递归排序左子数组
l = pivot + 1 // 剩余未排序区间为 [pivot + 1, right]
} else {
quickSort(nums, pivot + 1, r) // 递归排序右子数组
r = pivot - 1 // 剩余未排序区间为 [left, pivot - 1]
}
}
}
quick_sort.zig
// 快速排序（尾递归优化）
fn quickSort(nums: []i32, left_: usize, right_: usize) void {
var left = left_;
var right = right_;
// 子数组长度为 1 时终止递归
while (left < right) {
// 哨兵划分操作
var pivot = partition(nums, left, right);
// 对两个子数组中较短的那个执行快速排序
if (pivot - left < right - pivot) {
quickSort(nums, left, pivot - 1); // 递归排序左子数组
left = pivot + 1; // 剩余未排序区间为 [pivot + 1, right]
} else {
quickSort(nums, pivot + 1, right); // 递归排序右子数组
right = pivot - 1; // 剩余未排序区间为 [left, pivot - 1]
}
}
}