小知识点

x=l+r>>1 取l,r中间值
>>右移操作

⭐ if(l>=r) return; //一定要写，不然内存过不去

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

⭐ 只能用j，不能用i

快排模板

1.选中间值
2.移动和交换
3.递归

void quick_sort(int l,int r){
    if(l>r) return ;  //不合法情况，返回

    取x为l,r中间值
    i=l-1，j=r+1

    while(i<j){
        do-while  //l右移，直到值大于设定x
        do-while  //r左移，直到值小于设定x
        if(i<j) swap(q[i],q[j]); //当移到同一个元素就没必要交换了
    }
    //递归
    quick_sort(l, j);
    quick_sort(j + 1, r);

}

C++ 代码

快排

void quick_sort(int l,int r){
    if(l>=r) return; 
    int x=q[l+r>>1],i=l-1,j=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(l,j);
    quick_sort(j+1,r);
}

题解

#include<iostream>
#include<cstdio>

using namespace std;
const int N=100005;
int q[N],n;
void quick_sort(int l,int r){
    if(l>=r) return;
    int x=q[l+r>>1],i=l-1,j=r+1;
    while(i<j){
        //使用do-while避免死循环
        do i++; while(q[i]<x);
        do j--; while(q[j]>x);
        if(i<j) swap(q[i],q[j]);
    }
    quick_sort(l,j);
    quick_sort(j+1,r);
}

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

    return 0;
}

STL

#include<iostream>
#include<algorithm>

using namespace std;
const int N=1e5+10;
int q[N],n;

//从大到小排
bool cmp(int a,int b){
    return a>b;
}
//从小到大排
bool cmp(int a,int b){
    return a<b;
}

int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&q[i]);


    sort(q,q+n,cmp);
    //sort(q,q+n);  //默认从小到大
    //sort(数组首地址,数组最后一个地址的后一个地址,cmp规定排序方式（可以自己写）);

    for(int i=0;i<n;i++) printf("%d ",q[i]);


    return 0;
}