题目描述

快速排序(两个模板)

时间复杂度

$O(nlogn)$

C++ 代码

#include<iostream>
using namespace std;
const int N=1e5+10;

int a[N];
void quick_sort(int a[],int l,int r)//全局变量可以不用当做参数传进去
{
    if (l>=r) return ;
    int i=l-1,j=r+1,tmp=a[l+r>>1];    //这里一定是左右边界的左右边界处
    while(i<j)
    {
        // do i++; while(a[i]<tmp);
        // do j--; while (a[j]>tmp);
        while(a[++i]<tmp);          //这样写更容易记忆
        while (a[--j]>tmp);
        if (i<j) swap(a[i],a[j]);

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

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    quick_sort(a,0,n-1);
    for (int i=0;i<n;i++)
        cout<<a[i]<<' ';
    return 0;
}

C++ 代码

#include<iostream>
using namespace std;
const int N=1e5+10;

int a[N];
void quick_sort(int a[],int l,int r)
{
    if (l>=r) return ;
    int i=l-1,j=r+1,tmp=a[l+r+1>>1];    //这里一定是左右边界的左右边界处
    while(i<j)
    {
        // do i++; while(a[i]<tmp);
        // do j--; while (a[j]>tmp);
        while(a[++i]<tmp);
        while (a[--j]>tmp);
        if (i<j) swap(a[i],a[j]);

    }
    quick_sort(a,l,i-1);
    quick_sort(a,i,r);
}

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    quick_sort(a,0,n-1);
    for (int i=0;i<n;i++)
        cout<<a[i]<<' ';
    return 0;
}