Java快速排序模板

快速排序模板，简洁、好记。
partition函数中的左右指针最后总是相等，因而鲁棒性强，可扩展性好，可在很多算法中复用。

private void quickSort(int[] a, int i, int j) {
    if (i < j) {
        int mid = partition(a, i, j);
        quickSort(a, i, mid - 1);
        quickSort(a, mid + 1, j);
    }
}

private int partition(int[] a, int i, int j) {
    int l = i, r = j, pivot = a[i];
    while (l < r) {
        while (l < r && a[r] >= pivot) r--;
        while (l < r && a[l] <= pivot) l++;
        if (l != r) swap(a, l, r);
    }
    swap(a, i, l);  // 将第 i 个元素与 l 或 r 位置的元素调换都可以，因为 l 总是与 r 相等
    return l;  // 返回 l 还是 r 都可以，因为 l 总是与 r 相等
}

private void swap(int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}