快速排序

思想

1.确定分界点X,q[l],q[l+r/2],q[r] 
 2.调整范围使得左面<x,右面>x  (核心部分)
 3.递归处理左右两段
 note:
 设置i,j两个左右指针进行元素的左右划分，分别指向左右边界，逐步向区间中间移动

算法模板

void quick_sort(int q[],int l,int r){
    if(l>=r)return;//一个元素不用再继续，直接返回。
    int x=q[l+r>>1],i=l-1,j=r+1;//随机设置x,最好为l+r>>1，有时间复杂度的要求，i,j需要向外扩一位，为了下面的i++,j--的进行
    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(q,l,j);//继续递归解决左右区间子问题
    quick_sort(q,j+1,r);
}

C++ 代码

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e6+10;
int q[N];
void quick_sort(int q[],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(q,l,j);//不能取到右边界x=q[r];
    quick_sort(q,j+1,r);
    //quick(q,l,i-1);不能取到左边界x=q[l];
    //quick(q,i,r);
}
int main(){
    int n;
    int l,r;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&q[i]);
    }
    l=0;
    r=n-1;
    quick_sort(q,l,r);
    for(int i=0;i<n;i++){
        printf("%d ",q[i]);
    }
    return 0;
}