快速排序优化：随机化基准值避免复杂度退化
为什么需要随机化选取基准值？
- 选第一个元素作为基准：升序/降序数组会让快排复杂度退化为 O(n²)
- 选中间元素作为基准：存在 "Anti-QuickSort" 恶意数据，同样会退化为 O(n²)
- 随机化基准：从根本上避免被构造的数据 Hack，保证平均 O(n log n) 复杂度
// 这里要加入随机化取pivot，也就是基准的原因是
/*
你上面取第一个是pivot，这个是你自己构造了一个数组，让这个数组的第一个数字，刚好是这个数组的中间
的那个数字
出题人完全可以构造一个恶心的数据可以让你的复杂度退化导N的2
选第一个： 升序/降序数组就能杀掉你。
选中间： 有一种数据叫 "Anti-QuickSort"，专门通过复杂的交错顺序让“选中间”的快排退化成 O(n^2)
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime> // 用于随机数种子
template <typename T>
void QuickSort(T a[], int l, int r) {// 1. 递归终止条件if (l >= r) return;// 2. 随机化基准值（防止被 Hack 到 O(n^2)）// 在 [l, r] 范围内随机选一个索引，并将其值作为 pivotT pivot = a[l + rand() % (r - l + 1)];// 3. 双指针核心逻辑 (Hoare Partition)int i = l - 1, j = r + 1;while (i < j) {// 从左往右找第一个 >= pivot 的数do i++; while (a[i] < pivot);// 从右往左找第一个 <= pivot 的数do j--; while (a[j] > pivot);// 如果指针没相遇，交换这两个数if (i < j) std::swap(a[i], a[j]);}// 4. 递归处理左右两部分// 注意：Hoare 划分后，区间被分为 [l, j] 和 [j + 1, r]QuickSort(a, l, j);QuickSort(a, j + 1, r);
}// 为了方便调用，封装一个带长度参数的版本
template <typename T>
void QuickSort(T a[], int len) {if (len <= 1) return;srand(time(0)); // 初始化随机数种子QuickSort(a, 0, len - 1);
}