快排边界值取中点的模版

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5;

int n;
int A[N];

void quicksort(int A[], int l, int r) {
    if (l>=r) return;

    int x=A[(l+r)/2], i=l-1, j=r+1;
    while (i<j) {
        do ++i; while (A[i]<x);
        do --j; while (A[j]>x);
        if (i<j) swap(A[i], A[j]);
    }

    quicksort(A, l, j);
    quicksort(A, j+1, r);
    // 如果是A[(l+r+1)/2], 那么是
    // quicksort(A, l, i-1);
    // quicksort(A, i, r);
}

int main() {
    scanf("%d", &n);
    for (int i=0; i<n; i++) scanf("%d", &A[i]);

    quicksort(A, 0, n-1);

    for (int i=0; i<n; i++) printf("%d ", A[i]);

    return 0;
}

边界问题

关键预防在递归划分的时候出现空集和原来的集合，导致无限循环。具体来说，划分的时候i或者j不能是l或者r，否则如果i为l，quicksort(A, l, i-1)就会出现空集。

至于为什么是j和j+1而不是j-1和j，是因为j有可能到l，那么根据之前所说的为了防止空集的出现，就需要通过j和j+1的划分来得到两个非空子集。并且j是不可能小于l的。