void quickSort(int left, int right, vector<int>& arr) {
if (left >= right) return;

int i = left, j = right;
int pivot = arr[left]; // 选择 left 位置的元素作为枢轴,通常会选择中位数或随机元素作为枢轴以避免最坏情况的性能。
while (i < j) {
while (i < j && arr[j] > pivot) j--; // 从右向左找第一个小于等于 pivot 的数
while (i < j && arr[i] < pivot) i++; // 从左向右找第一个大于等于 pivot 的数
if (i < j) {
swap(arr[i], arr[j]);
i++;
j--;
}
}
swap(arr[left], arr[i]); // 将枢轴放到正确的位置

quickSort(left, i - 1, arr); // 对左半部分进行快速排序
quickSort(i + 1, right, arr); // 对右半部分进行快速排序
}