完成阅读您将会了解快速排序的：
- 算法思想
- 实现步骤
- 实践范例（C++/Rust）
1. 算法思想
快速排序（Quick Sort），简称快排，最早由 C.A.R.Hoare 在1962年于快速排序[1]一文提出。快速排序实质上运用分治（Divide & Conquer）思想，每次选取基准元素（Pivot Element），并将剩余元素在其左右分为小于与不小于基准元素的两个子序列（Sub-sequence），然后针对子序列递归地进行快速排序，如图1[2]。
快速排序为不稳定排序（Unstable Sort），即同值元素排序后未必保持原有相对位置，如图2-3[3]。快速排序时间复杂度为\(O(n^2)\)，但实际运用中，摊销（Amortized）时间复杂度为\(O(n\lg n)\)。快速排序是一种原址排序（In-place Sort）算法，额外的空间复杂度为\(\Theta (1)\)。快速排序算法适合硬件高速缓存（Cache）优化，拥有很好的实际运行效率，并被广泛使用。
2. 实现步骤
- 选择基准元素；（序列尾，本文程序范例中随机选取基准）
- 将不小于和不大于基准元素的元素分区为左右两个子序列，与此同时基准元素本身已完成排序，如图4[3:1]；
- 递归排序子序列。
3. 实践范例（C++/Rust）
问题描述：
为无序数组A做单调不减排序。
输入：无序数组A
输出：有序数组A
解答思路：
运用快速排序算法对A进行原址排序。
伪代码1：分区
变量说明：A\(\rightarrow\)待排序数组；l\(\rightarrow\)子序列左闭边界；r\(\rightarrow\)子序列右闭边界；p\(\rightarrow\)分区点；iter\(\rightarrow\)迭代替量
伪代码2：快速排序A
变量说明：A\(\rightarrow\)待排序数组；l\(\rightarrow\)子序列左闭边界；r\(\rightarrow\)子序列右闭边界；p\(\rightarrow\)分区点
C++解答：传指针入参
constexpr auto _partition(auto l, auto r) noexcept {
auto p = l, iter = p - 1;
auto pivot = *r;
while (++iter < r)
if (*iter < pivot)
std::swap(*iter, *p++);
std::swap(*p, *r);
return p;
}
void quick_sort(auto l, auto r) noexcept {
srand(time(nullptr));
if (l < r) {
std::swap(*(l + rand() % (r - l + 1)), *r);
auto p = _partition(l, r);
quick_sort(l, p - 1);
quick_sort(p + 1, r);
}
}
Rust解答：
fn _partition<T: Clone + std::cmp::PartialOrd>(A: &mut Vec<T>, l: usize, r: usize) -> usize {
let (mut p, pivot) = (l, A[r].clone());
for i in l..r {
if A[i] < pivot {
A.swap(i, p);
p += 1;
}
}
A.swap(p, r);
p
}
pub fn quick_sort<T: Clone + std::cmp::PartialOrd>(A: &mut Vec<T>, l: usize, r: usize) {
if l < r {
A.swap(thread_rng().gen_range(l..=r), r);
let mut p = _partition(A, l, r);
quick_sort(A, l, p - 1);
quick_sort(A, p + 1, r);
}
}
4. 自我测试
伪代码实践：
快排递归版受栈内存限制，无法直接应用在大规模数据上，请将快排改写成迭代版。
LeetCode选荐：
让每一天足够精致，期待与您的再次相遇! ^_^