本文不是快速排序教程，而是记录其中值得关注的细节。

快速排序的思想很简单，接触过的人应该很容易记住，就是按一定的策略选一个pivot，然后按照一定的策略把pivot移到合适的位置，使得前面的都比它小，后面的都比它大，一样的两边都可以放，最后分别处理前后两个部分。伪代码如下：

quicksort a[], lo, hi:
	if lo >= hi, return;
	p = partition(a, lo, hi);
	quicksort(a, lo, p - 1);
	quicksort(a, p + 1, hi);

所以关键就是这个partition函数的内容，一旦处理不好，就退化成O(N^2)的时间复杂度；最好的情况是O(NlogN)，因为每一轮都要遍历所有元素N，最少有LogN轮，也就是每次都对半划分的时候会达到最小。

划分一般有两种策略，一个是单指针法，一个是双指针法，单指针法从左往右，不断扩大小于pivot元素的边界，代码如下所示：

int partition(int[] a, int lo, int hi){
		int i = lo - 1, j = lo;
		int t, pivot = a[hi];
		while (j < hi) {
      	if (a[j] < pivot) {
         		i++; //border of smaller elements
             t = a[j];
             a[j] = a[i];
              a[i] = t;
          }
            j++;
        }
        // i+1 is the positon
        t = a[hi];
        a[hi] = a[i + 1];
        a[i + 1] = t;
        return i + 1;
}

这里用i标识小于pivot元素的边界，具体的解释可以参考各种资料，因为这不是本文的重点；

然后是双指针法，代码如下：

int partition(int[]a, int lo, int hi){
    int i = lo - 1, j = hi;
    int t, v = a[hi];
    while (true) {
        while (a[++i] < v)
            if(i == hi)
                break;
        while (v < a[--j])
            if (j == lo)
                break;
        if (i >= j)
            break;
        t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    t = a[i];
    a[i] = a[hi];
    a[hi] = t; 
	return i;
}

要注意的是，这里的下标选择具有很大的随机性，+1或者-1或者是本身都不要紧，重要的是不要搞混边界就可以，所以当我们去网上找这类的代码，会有千奇百怪的边界选择，但是有些是不太好的，这里选的这两种应该是较好的选择。但是即使如此，还有很多值得一提的问题。

问题一般都发生在边界或特殊case，所以来想想有哪些特例。第一是输入已经有序；第二是输入全部倒序；第三是输入元素全部相同；第三种其实是第一种和第二种的交集；想着这些特例再来看具体的问题。

首先来看pivot元素的选取，这里一般有三种策略：

  1. 选取第一个或者最后一个元素

    当输入数据是随机的时候，这种选法并没有问题，效果也很好。但是如果输入数据是是上面三种特殊的情况，就会导致pivot是数组的最值，然后所有的元素都会集中在一边，然后算法就会从本身的logN轮退化成N轮，时间复杂度就会变成N^2；

  2. 随机选取一个

    这种方法比第一种好一点，但是有可能也会随机选到最大最小值从而导致算法的失败；

  3. 选择三个数，取中间的元素作为pivot

    这个方法比上面两种都好，不会出现pivot一边没有数据的情况，其实还有别的好处，下面会提到；

接下来来看上面第一种partition算法，其中的一段：

while (j < hi) {
	if (a[j] < pivot) {
    	i++; //border of smaller elements
        t = a[j];
        a[j] = a[i];
        a[i] = t;
    }
        j++;
}

这里基本是没问题的，但问题就在第二行这个不等号，万一所有的数据都相同，这个不等号一直都不成立，导致所有元素集中在一边；就算改成<=，当所有的元素都相同时，不等号一直成立，还是会导致所有元素“一边倒”，从而导致最差时间复杂度。

最后来看第二种partition算法，这里是选取a[hi]作为pivot，基本也是没有问题，但如果元素已经有序或逆序，会导致最坏复杂度；但是令人惊喜的是，如果所有元素都相同，这里会很好的处理，原因就在这里的两个内循环和它的不等号：

while (a[++i] < v)
	if(i == hi)
    	break;
while (v < a[--j])
    if (j == lo)
        break;

如果所有元素都相同时，这里的i和j会交替前进，而不会产生一边倒，因为这里分别使用了<和>，可以体会一下；

此外，这里的两个break其实是为了数组边界越界，但其中第一个是冗余的判断，因为已经选取a[ hi ]作为pivot，而这里使用<，一个元素永远不可能小于本身，所以这里一定不会越界；所以这里的a[ hi ]起的就是哨兵的作用，有效防止了数组的越界；

同时，为了在下面使用哨兵判断数组越界，可以使用如下策略：采用上面提到的取三数，取其中间元素作为pivot的策略；假设我们选取pivot值的伪代码如下：

choosePivotValue(int[]a, int lo, int hi):
    mid = lo + (hi - lo)/2;
    sort(a[lo], a[mid], a[hi]);//so that a[lo] <= a[mid] <= a[hi]
	swap(a[mid], a[hi - 1]);
	return a[hi - 1]

这里选取的是a[ hi - 1 ]这个元素作为pivot值，注意到这里a[ hi ] > pivot，所以可用作下面的哨兵；

那上面的程序就变成：（伪代码）

int partition(int[]a, int lo, int hi){
    int i = lo, j = hi - 1; // changed
    int t;
    pivot = choosePivotValue(a, lo, hi);//pseudo code
    while (true) {
        while (a[++i] < pivot)
                ;
        while (pivot < a[--j])
                ;
        if (i >= j)
            break;
        t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    t = a[i];
    a[i] = a[hi - 1];
    a[hi - 1] = t; 
	return i;
}

这里有些小的改变，从上面的选取函数回来之后，一定有a[lo] < pivot && a[ hi ] > pivot，所以这里的下标就可以从lo和hi - 1开始，注意下面是++i和- -j，这就是跳过了第一个和最后两个元素；这个写法是正确的，更加简洁，但是边界值处理容易出错；

这里不管怎么选取pivot，最终倒要将它们放到数组的两端，从而在循环时可以忽略它们，否则要处理的问题就很复杂，上面的双指针法，是把pivot放到右边，所以出循环的饿时候，是和i元素交换，如果放到左边，出循环时就得和j交换，这是很容易出错的；和右边交换意味着要把大的元素放过去，而i停止的地方刚好是大的元素，如果和左边交换，意味着要把小的元素放过去，而j停止的地方就是小的元素；

还有一点要注意的是，上面的代码，其中内循环部分有人会写成：

while(a[i] < pivot)i++;
while(a[j] > pivot)j++;

试想，如果所有元素都相同，这里就是死循环了，因为ij始终不变；所以++放里面是正确的，其他情况类似。

此外，快速排序虽然快，但是在小数组时效果不如插入排序好，所以可以将插入排序集成到里面，当子数组小于某个值的时候，用插入排序，效果会更好；为了避免调用栈开销，可以化递归为非递归。

所以，总结来说就是：Every character counts. 代码里，每个符号都不是随意写的。

写这篇的原因，是因为发现以往有很多细节没有注意，理解算法，不应该止于理解大意。