function quickSort(arr, left, right) {
if (left >= right) return;
let pivot = partition(arr, left, right);
quickSort(arr, left, pivot - 1);
quickSort(arr, pivot + 1, right);
}
function partition(arr, left, right) {
let pivot = arr[left]; // 挖坑：取最左元素为基准
let i = left, j = right;
while (i < j) {
while (i < j && arr[j] >= pivot) {
j--; // 从右向左找小于基准的元素
}
if (i < j) {
arr[i] = arr[j]; // 填左坑，挖右坑
i++;
}
while (i < j && arr[i] <= pivot) {
i++; // 从左向右找大于基准的元素
}
if (i < j) {
arr[j] = arr[i]; // 填右坑，挖左坑
j--;
}
}
arr[i] = pivot; // 基准归位
return i;
}