1.1快排

void quick_sort(int q[], int l, int r) //l是数组最左边的下标，r是数组最右边的下标。
{
    if (l >= r) return; //数组中只有一个数或没有数。

    int i = l - 1, j = r + 1, x = q[l + r >> 1]; //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);
}

上砖为acwing上的模板 。

注意到第三句砖码有 x=q[l+r>>1] , l+r>>1意思为和除以2取整。

数组中的数从 i 的位置开始向后与 x 比较大小，小于 x 则 i++，继续向后比较后面的数与 x 的大小；大于 x 则跳出此循环转入 j 与 x 的比较循环中（见下行）。

数组中的数从 j 的位置开始向前与 x 比大小，大于x则 j--，继续向前比较与x的大小，小于x时跳出此循环。

如果两个循环都跳出来了，且 i 在 j 的前面，则交换下标为 i 的数与下标为 j 数的位置。每次迭代都会使得一个在前面的且大于 x 的数与一个在后面的且小于 x 的数交换位置。

当 j<=i 时，跳出最外层的while循环，此时前半部分都是小于 x 的数，后半部分都是大于 x 的数。

接着是两个内嵌的调用，把刚才的前半部分和后半部分内部也重新排列成小的在前部分，大的在后部分，以此类推，直到排序的区间小到不能再小。

下面这个模板是内部调用 quicksort 的时候用 i-1 和 i 替换 j 和 j+1 。需要注意的是 x 必须= q[r] ，而不是 q[l] 或 q[l+r>>1] ，不然会出现边界问题。 

void quicksort(int q[],int l,int r){
    if(l>=r) return;
    int i=l-1,j=r+1,x=q[r];
    while(i<j){
        do i++;while(x>q[i]);
        do j--;while(x<q[j]);
        if(i<j) swap(q[i],q[j]);  
    }
	quicksort(q,l,i-1);quicksort(q,i,r);
}

来看一道例题： 

#include<iostream>
using namespace std;
const int N=1e5+10;
int n;
int a[N]={0};
void quicksort(int q[],int l,int r){
    if(l>=r) return;
    int i=l-1,j=r+1,x=q[l+r>>1];
    while(i<j){
        do i++;while(x>q[i]);
        do j--;while(x<q[j]);
        if(i<j) swap(q[i],q[j]);  
    }
	quicksort(q,l,j);quicksort(q,j+1,r);
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    quicksort(a,0,n-1);
    for(int i=0;i<n;i++){
        printf("%d ",a[i]);
    }
    return 0;
}