对于这一类排序，我觉得先要弄懂其排序思想，可以通过看一些书籍或者文章（算法导论不错），在此基础上

要自己能够总结写出算法的伪代码，即使环境和条件改变，特别是一时不好下手写代码时很有必要先写下算法

伪代码，然后具体实现，时而看看写写，此类算法就能信手拈来。

快速排序是基于分治模式的。下面是算法导论中对一个定型数组A[p..r]排序分治过程的三个步骤：

分解（划分）：数组A[p..r]被划分为两个（可能空）子数组A[p..q-1]和A[q+1..r]，使得A[p..q-1]

中每个元素都小于等于A[q]，而且小于等于A[q+1..r]中的元素。下标q也在这个过程中计算。

解决：通过递归调用快速排序，对子数组A[p..q-1]，A[q+1..r]排序。

合并：因为是就地排序的，所以不需合并操作。整个数组A[p..r]已排序。

下面快速排序的实现过程可以很直观的表达这种思想：

Quciksort(A,p,r)

1   if p<r

2         then q←Parttion(A,p,r)

3                Quicksort(A,p,q-1)

4                Quicksort(A,q+1,r)

Parttion(A,p,r)

1    x← A[r]                //划分的中间点

2    i←p-1                  //i总是指向已划分的较小序列的最后一个数的地址

3    for j←p to r-1                //j用来扫描未被划分的数，从第一个未被划分的数开始

4         do if A[j] <= x

5              then i←i+1               //将紧接着已划分的较小序列的那个位置用来存放新扫描到的符合要求的数，即加入新数到以划分的较小序列

6                       exchange A[i]?A[j]

7    exchange A[i+1]?A[r]      //就是把pivotkey放到整个序列的中间，左边是较小序列，右边是较大序列，i未加1前还指向已划分的较小序列的最后一个数的地址，所以…

8    return i+1      //返回子序列划分点

参考代码如下：

int Partition(int data[],int start,int end)
{
    if (data =http://www.mamicode.com/= NULL)
    {
        throw new exception("invalid Parameters");
        //return -1;//可以自定义错误以免程序崩溃
    }
    int pivotkey = data[end];//划分的中间点，可以随机选取，这个点的选取和原序列的特性影响排序性能
    int small = start-1;//small总是指向已划分的较小序列的最后一个数的地址
    for (int j = start;j < end;j++)//j用来扫描未被划分的数，从第一个未被划分的数开始
    {
        if (data[j] > pivotkey)
        {//将紧接着已划分的较小序列的那个位置用来存放新扫描到的符合要求的数，即加入新数到以划分的较小序列
            small++;
            swap(data[small],data[j]);
        }
    }
    //这个++和上个++是一个意思，就是把pivotkey放到整个序列的中间，左边是较小序列，右边是较大序列
    small++;
    swap(data[small],data[end]);
    return small;
}

void swap(int &a,int &b)
{
    int temp = a;
    a = b;
    b = temp;
}

void QucikSort(int data[],int start,int end)
{
    if (start < end)
    {
        int index = Partition(data,start,end);//每次划分的分界点
        if (index > start)
        {
            QucikSort(data,start,index-1);
        }
        if (index < end)
        {
            QucikSort(data,index+1,end);
        }
    }
}

上述代码和算法使用的从头到尾扫描序列进行划分的。更常见的一种是从两头进行扫描，这个在很多书上

都能看到，并且有详细的例证序列展示每一步的执行后的序列变化，下面是基于这种扫描方法的代码，代

码很简洁，但光看代码可能不是一下子就能理解

参考代码如下：

int Partition(int *a,int low,int high)
{
    int pivotkey = a[low];//初试时以第一个数作为划分值
    while (low < high)   //从左右两边同时扫描，相遇时扫描完成，即划分序列完成
    {
        //从右边开始扫描，直到找到一个比划分值小的为止，将此值添加到较小序列中。
        //其实此时每次循环后low前面都是较小序列，high后面的都是较大序列，中间的是还没扫描到的
        while (low < high && a[high] >= pivotkey)
        {
        
            high++;
        }
        a[low] = a[high];
       
        //从左边开始扫描，直到找到一个比划分值大的为止，将此值添加到较大序列中。
        while (low < high && a[low] >= pivotkey)
        {
            low++;
        }
        a[high] = a[low];
    }

    //上面最后一次循环完，low已经等于high了，他们处在中间位置，此时中间位置的值可能是原值
    //也可能是其他的一个重复值，所以将pivotkey填入就是完成原数据数列了
    a[low] = pivotkey;
    return low;
}

关于性能分析后面总结排序再说明。

快速排序