快速排序
入门平均性能最优的通用排序算法，理解 pivot 分区是关键。
// 自定义输入
用你自己的数组跑一遍
速度 中
待机 ⌨1int partition(int arr[], int lo, int hi) {
2 int pivot = arr[hi];
3 int i = lo - 1;
4 for (int j = lo; j < hi; j++) {
5 if (arr[j] <= pivot) {
6 i++;
7 swap(arr[i], arr[j]);
8 }
9 }
10 swap(arr[i + 1], arr[hi]);
11 return i + 1;
12}
13
14void quickSort(int arr[], int lo, int hi) {
15 if (lo >= hi) return;
16 int pivotIdx = partition(arr, lo, hi);
17 quickSort(arr, lo, pivotIdx - 1);
18 quickSort(arr, pivotIdx + 1, hi);
19}
复杂度分析
时间 O(n log n)
空间 O(log n)
最坏 O(n²)
算法讲解
快速排序选取一个基准元素 pivot，将数组分为小于等于 pivot 和大于 pivot 两部分。
分区完成后 pivot 已在最终位置，再递归处理左右子数组。
平均时间复杂度 O(n log n)，但最坏情况（如极端不平衡分区）会退化到 O(n²)。
当前演示使用末尾元素作为 pivot，便于观察分区与递归过程。