算法考试一般不直接考，面试喜欢考
方法一：
建立两个辅助数组A[] B[]
将比枢数小的放在A，大的放在B
再将AB中数放回原数组即完成一趟排序
较为简单，不附代码
方法二：（最为常用）
双指针遍历，两边向内遍历
左指针l直到找到第一个比枢大的数，右指针r找到第一个比枢小的数，若此时l>r，二者交换

普通快排：

#include <bits/stdc++.h> 
using namespace std;

#define Max 100005

int n;
int q[Max];

void quick_sort(int q[],int l,int r)
{
    if(l>=r) return;
    int x=q[l];//以第一个元素为枢
    int 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);//递归左半段
    /*j也可以写成i-1，但是同时要调整上面的x=q[l],因为会有边界问题*/ 
    quick_sort(q,j+1,r);//递归右半段 
}

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

    quick_sort(q,0,n-1); 

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

    system("PAUSE");
    return 0;
}

数据强化后的快排，题目785

#include <iostream>
#include <algorithm>

using namespace std;
const int M =100010;
int n,q[M];

void quick_sort(int q[],int l,int r)
{
    if(l>=r) return;
    int x=rand()%(r-l+1)+l,i=l-1,j=r+1;//取l到r之间的一个随机数
    swap(q[x],q[l]);
    x=q[l];
    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);
}

int main() {

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

    quick_sort(q,0,n-1);

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

    system("PAUSE");
    return 0;
}