1.1 实现快速排序
★★ 中等考点： 分治、基准值选择、排序优化
参考答案：
- 快速排序是分治思想的经典应用：选基准值 → 分区（小于基准在左、大于在右）→ 递归排序两侧；
- 优化点：
- 三数取中选择基准值，避免已排序数组退化到 O(n²) 最坏情况；
- 小数组（长度 < 10）改用插入排序，减少递归开销；
- 尾递归优化（只递归小的一侧）；相同元素聚集优化（三路快排）。
- 平均 O(n log n)，最坏 O(n²)，空间 O(log n)（递归栈）；不稳定排序；
- 代码示例：
template<typename T>
void QuickSort(TArray<T>& Array, int32 Left, int32 Right) {
if (Left >= Right) return;
if (Right - Left < 10) { InsertionSort(Array, Left, Right); return; } // 小数组
T Pivot = Array[Left + (Right - Left) / 2]; // 三数取中
int32 i = Left, j = Right;
while (i <= j) {
while (Array[i] < Pivot) i++;
while (Array[j] > Pivot) j--;
if (i <= j) { Swap(Array[i], Array[j]); i++; j--; }
}
QuickSort(Array, Left, j);
QuickSort(Array, i, Right);
}- UE 的
TArray::Sort()基于 Introsort（快排 + 堆排 + 插入排序混合），可自定义比较器。