快排模板

算法分析

快速排序的思想主要是基于分治思想，是一种不稳定排序，主要包括三个部分：

• 1、分界点的选择，分界点的选择，常见的有取 a[l]、a[r]、a[l+r>>1]

​ 当取a[l]时候，如果数据递增的，其复杂度最高 $O(n^2)$

​ 当取a[r]时候，如果测试用例的最大值刚好是最后一个时,就会无限递归!

• 2、区间的调整

​ 1、初始化 i = l-1 和 j = r+1

​ 2、先判断再循环，使用 do{…;} while{…;}结构

​ 3 、其他情况容易出现 TLE 因为死循环而超时，具体见代码分析

• 3、递归处理左右区间

​ 边界条件，当 l>=r 或者 l==r 时候代表只有一个数据，当前循环结束，退出即可

​ 1、使用两个空数组分别存储 > 和 < 的数，最后再存回原数组，线性复杂度，但是空间复杂度高

​ 2、双指针相遇作为判断条件，分别移动，时间复杂度 $O(nlogn)$，

模板

void quick_sort(int a[], int l, int r)
{
    if (l >= r) return;  

    int i = l - 1, j = r + 1, x = a[l + r >> 1];
    while (i < j)
    {
    /* 用下面的也一样
        while (a[++i] < x);
        while (a[--j] > x);
        if (i < j) swap(a[i], a[j]);
    */
        do i++; while (a[i] < x);
        do j--; while (a[j] > x);
        if (i < j) swap(a[i], a[j]);
    }

    quick_sort(a, l, j), quick_sort(a, j + 1, r);
}

代码分析

快排算法的边界情况很多，建议直接背一个模板，否则可能会出现各种TLE或者Segmentation Fault的问题

1、分界点的选择，分界点的选择，常见的有取 a[l]、a[r]、a[l+r>>1]

​ 当取a[l]时候，如果数据递增的，其复杂度最高 $O(n^2)$

​ 当取a[r]时候，如果测试用例的最大值刚好是最后一个时,就会无限递归!

2、x取q[(l+r)/2]是对的，但是l+r+1就不对

3、if(x<y) 这个也很重要，当数据只有两个时候会出现都不移动或者只移动一侧，从而导致死循环

4、使用 do while 结构，是为了保证指针能往下走所以要先++再判断，否则用while可能出现停留在原地不动的死循环

完整代码

#include<iostream>
using namespace std;

const int N = 1e5 + 10;
int n;
int a[N];

void quick_sort(int a[], int l, int r)
{
    if (l >= r) return;  

    int i = l - 1, j = r + 1, x = a[l + 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]);
    }

    quick_sort(a, l, j), quick_sort(a, j + 1, r);
}

int main() {

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    quick_sort(a, 1, n);
    for (int i = 1; i <= n; i++) cout << a[i] << " ";

    return 0;
}

方法二

void QuickSort(ElemType A[], int low, int high) {
    if (low < high) {           //递归跳出的条件
        //Partition()就是划分操作，将表A[low..high]划分为满足上述条件的两个子表
        int pivotpos = Partition(A, low, high); //划分
        QuickSont(A, 1ow, pivotpos - 1); //依次对两个子表进行递归排序
        QuickSort(A, pivotpos + 1, high);
    }
}

int Partition(ElemType A[], int low, int high) { //- 趟划分
    ElemType pivot = A[1ow];        //将当前表中第一个元素设为枢轴，对表进行划分
    while (low < high) {            //循环跳出条件
        while (1ow < high && A[high] >= pivot)
            --high;
        A[low] = A[high];       //将比枢轴小的元素移动到左端
        while (low < high && A[low] <= pivot)
            ++1ow;
        A[high] = A[low];       //将比枢轴大的元素移动到右端
    }
    A[low] = pivot //枢轴元素存放到最终位置
        return low;
}