Quick Sort 快速排序 · QuickSort.cpp
快排和他的名字一样，是一个排序比较快的算法，它的核心思想是选定一个基准p，将数组中小于p的放在一边，大于p的放在一边，分成两个子数组，之后再分别对这两个子数组进行排序，不断重复直到整个数组有序
一、复杂度与特性
| 项目 | 值 | 说明 |
|---|---|---|
| 时间（最好） | O(n log n) | 每次划分都恰好对半：递归树高log n 层，每层合计扫一遍 O(n) |
| 时间（平均） | O(n log n) | 期望比较次数 ≈2n·ln n ≈ 1.39·n·log₂n |
| 时间（最坏） | O(n²) | 每次都选到极值当基准 ⇒ 划分成0 和 n-1 两段、递归 n 层 |
| 空间 | O(log n) 平均，O(n) 最坏 | 原地排序，不额外开数组，只花递归栈 |
| 稳定性 | 否 | 划分时的远距离交换会打乱相等元素的相对次序 |
| 比较次数 | n·log n | 一趟划分 O(n)，一共log n 层 |
二、代码
void quick_sort(std::vector<int> &a, int l, int r)
{
if (r - l <= 0)
return;
std::swap(a[l], a[r]);
int p = a[l]; // 也可以为其它位置
int i = l - 1, j = r + 1; // 两个指针分别指向最左边和最右边
while (true)
{
do
{
++i;
} while (a[i] < p);
do
{
--j;
} while (a[j] > p);
if (i >= j) // 判断是否已经分好
break;
std::swap(a[i], a[j]);
}
quick_sort(a, l, j);
quick_sort(a, j + 1, r);
}要点：
- 快排中基准元素的选取很重要，选的好与不好差距很大（最好是随机选取，并且不能留在区间右端）
- 出口条件是长度小于等于一，也就是
l>=r i >= j时必须先break再交换；否则会交换一对本该分离两侧的元素导致划分失效。- 划分里的交换是远距离的，无法保证稳定性，如[2a, 2b, 0] 排完是 [0 2b 2a]，两个2顺序颠倒了
- 内层必须严格小于大于，否则指针会冲过区间另一端导致划分不均
- 递归点用
j而不是i
附件下载
- QuickSort.cpp（1,022 B · 41 行）
- QuickSort.md（3 KB · 53 行）