快速排序模板

#include <bits/stdc++.h>

using namespace std;
const int maxn=1e5+5;
int a[maxn],n;

void quickSort(int *a,int l,int r)
{
    if(l>=r)
        return;
    int i=l,j=r,t=a[i];
    while(i<j)
    {
        while(i<j&&a[j]>=t)
            j--;
        a[i]=a[j];
        while(i<j&&a[i]<=t)
            i++;
        a[j]=a[i];
    }
    a[i]=t;
    quickSort(a,l,i-1);
    quickSort(a,i+1,r);
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for(int i=0;i<n;i++)
        cin >> a[i];
    quickSort(a,0,n-1);
    for(int i=0;i<n;i++)
        printf("%d ",a[i]);
    printf("\n");
    return 0;
}

#include <bits/stdc++.h>

using namespace std;
const int maxn=1e5+5;
int a[maxn],n;

void quickSort(int *a,int l,int r)
{
    if(l>=r)
        return;
    int i=l-1,j=r+1,t=a[(l+r)>>1];
    while(i<j)
    {
        do
        {
            i++;
        }while(a[i]<t);
        do
        {
            j--;
        }while(a[j]>t);
        if(i<j)
            swap(a[i],a[j]);
    }
    quickSort(a,l,j);
    quickSort(a,j+1,r);
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for(int i=0;i<n;i++)
        cin >> a[i];
    quickSort(a,0,n-1);
    for(int i=0;i<n;i++)
        printf("%d ",a[i]);
    printf("\n");
    return 0;
}