快速排序的实现思想其实很简单，可以简单的描述成下面的递归形式，

qsort(array)
        设置分界点;
        把所有小于分界点的值作为左子列;
        把所有大于分界点的值作为右子列;
        qsort(左子列);
        qsort(有子列);
}


但是，实际用c/c++实现起来，就不见得一下可以写出来了，

以下是我的实现

#define SWAP(p1, p2) do { \
        int tmp = *(p1); \
        *(p1) = *(p2); \
        *(p2) = tmp; \
} while (0)


//====================================================
// 划分数组，并返回分界点
//====================================================
int partition(int array[], int left, int right)
{
        int l=left, r=right-1; /*用数组的最后1个元素分区*/

        while (l < r) {
                /*查找交换元素*/
                if (array[l] < array[right]) {
                        l++;
                        continue;
                }

                if (array[r] > array[right]) {
                        r--;
                        continue;
                }

                /*交换元素，调整索引*/
                SWAP(array+l, array+r);
                l++;
                r--;
        }

        /*此时数组l,r索引已经相遇，即l==r*/
        if (array[l] < array[right]) l++;
        SWAP(array+l, array+right);

        return l;
}


//快速排序
void qsort(int array[], int left, int right)
{
        if (left >= right) return;

        int pos = partition(array, left, right);
        if (pos == -1) return;

        qsort(array, left, pos-1);
        qsort(array, pos+1, right);
}


我认为快速排序中主要的东西就是partition方法，如果把partition
提取出来实现，则快速排序算法也就比较简单了。网上有qsort比较简
洁的c++实现，即没有把partition方法分离出来，但是一步到位的做法
比较难，我还是更喜欢先实现，再优化的方式。。。