仅用不到20行代码实现快排-C++版

int _PARTITION(vector &A, int p, int r) {
    int x = A[r];
    int i = p - 1;
    for (int j = p; j < r; j++) {
        if (A[j] < x) {
            i++;
            std::swap(A[i], A[j]);
        }
    }
    std::swap(A[i + 1], A[r]);
    return i + 1;
}

void quicksort(vector &A, int p, int r) {
    if (p < r) {
        int q = _PARTITION(A, p, r);
        quicksort(A, p, q - 1);
        quicksort(A, q + 1, r);
    }
}

大学本科的时候一直没搞清楚如何快速排序，看了算法导论才明白其中的原理，其实就是分治思想。建议直接看原文，里面有理论的推导，不只是告诉你怎么做，而且告诉你为什么

当数据基本有序时，使用插入排序效率高。

快速排序最坏情况下会退化到插入排序