时间复杂度

最好时间复杂度	最坏时间复杂度
O(nlogn)	O(n²)
当每一次划分的point使得一边是1，一边是n-1时，就是最坏情况
快速排序的时间复杂度分析

主要步骤

1. 寻找x，划分边界，x是可以随意取的
2. 调整区间，使得左边都小于<=x,右边都>=x
3. 递归处理左右两边

注意： 调整后的区间交界点不一定等于x，因为左右两个区间还是乱序，x的位置是不确定的

实现方式

暴力

开两个数组，遍历数据，小于等于x的放在a数组中，大于x放在b数组中，最后合并到一起

双指针

题目和讲解

1. 首先因为我们的循环体内是先会进行一次++，所以定义两个指针i，j为l-1和r+1.
2. 对于i来说就是要从左向右找到第一个大于等于x的数停下来，j就是要从右向左找到第一个小于于等于x的数停下来，然后交换两个数，这样可以全程保证i左边的一定小于x，j右边的一定大于x
3. 递归处理左右 快速排序算法的证明与边界分析

#include <bits/stdc++.h>
using namespace std;

const int N=1e6+10;

int m[N];
int n;

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

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&m[i]);
    }
    
    quick_sort(m,0,n-1);
    for(int i=0;i<n;i++)
    {
        printf("%d ",m[i]);
    }
    return 0;
}