快速排序 (Quick Sort)

int partition(int a[], int l, int r) {
    int pivot = a[r];  // 选择最后一个元素作为基准
    int i = l - 1;     // i 指向小于等于基准的最后一个元素

    for (int j = l; j < r; j++) {
        if (a[j] <= pivot) {
            i++;
            swap(a[i], a[j]);  // 小元素移到左边
        }
    }
    swap(a[i + 1], a[r]);  // 基准放到正确位置
    return i + 1;
}

void quickSort(int a[], int l, int r) {
    if (l < r) {
        int p = partition(a, l, r);  // 分区
        quickSort(a, l, p - 1);      // 递归排序左半部分
        quickSort(a, p + 1, r);      // 递归排序右半部分
    }
}