快排【算法导论】

注：学习算法导论，按照标准伪代码理解翻译为java实现，如有兴趣理解整个过程的细节，建议阅读《算法导论》第7章：快速排序。

void quickSort(int[] A, int p, int r) {
    if (p < r) {
        int q = partition(A, p, r);
        quickSort(A, p, q -1);
        quickSort(A, q + 1, r);
    }
}

int partition(int[] A, int p, int r) {

    int x = A[r];
    int i = p - 1;
    int temp;
    for (int j = p; j < r; j++) {
        if (A[j] <= x) {
            i += 1;
            temp = A[i];
            A[i] = A[j];
            A[j] = temp;
        }
    }
    temp = A[i + 1];
    A[i + 1] = A[r];
    A[r] = temp;
    return i + 1;
}