public static void QuickSort(int[] arr, int l, int r) {
if (r <= l) return;
int pivot = partition(arr, l, r);
QuickSort(arr, l, pivot - 1);
QuickSort(arr, pivot + 1, r);
}
static int partition(int[] arr, int l, int r) {
// pivot表示当前标杆,counter用于计数比arr[pivot]小的值
int pivot = r, counter = l;
// 比arr[pivot]小的值都放在最左边
for (int i = l; i < r; ++i) {
if (arr[i] < arr[pivot]) {
int tmp = arr[i];
arr[i] = arr[counter];
arr[counter] = tmp;
++ counter;
}
}
// 处理标杆
int tmp = arr[counter];
arr[counter] = arr[pivot];
arr[pivot] = tmp;
return counter;
}