快速排序(模板)

快速排序原理如下：

我们在排序的时候，用到了划分的思想，随机选择一个中轴，双指针i, j，指针i从左往右扫描，指针j从右往左扫描，如果i < j 则进行交换，并且继续循环，直到遇到中轴，这时候我们的i和j均为中轴（理由：因为i，j相等）。我们在中轴左右递归，假设递归到了最后，也就交换了最后两个数。

时间复杂度分析，我们每次从l 扫描到 r，复杂度为T(n)，左边递归，右边递归，时间复杂度为T(1/2 n), 接着继续往下进行

void quick_sort(int *q, int l, int r) {
    if(l >= r) return;
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while(i < j) {
        do i++; while(q[i] < x);
        do j--; while(q[j] > x);
        if(i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j); quick_sort(q, j + 1, r);
}

快速排序(模板)

原文：https://www.cnblogs.com/littlepage/p/13507143.html