前言
每次做快速排序的时候，一直都有很恼人的bug出现在我的分区算法之中。写这篇文章的目的，就是要彻底让自己明白分区是怎么做的。
分区算法有多种的实现。简要说有
- 选择第一个为哨兵。第二个元素和最后一个元素分别为i和j。每次i先走，遇到大于等于哨兵的值时候停下来。然后到j，找到小于哨兵的停下来。然后交换ij。重复此过程。直到i超过j，交换j与哨兵的位置。简称为两边交换法。
- 选择任意位置元素为哨兵。i在第一个元素（非哨兵），j在最后一个元素。哨兵的值拿出来，标记哨兵的位置为空，准备插入下一个值。j先走，找到一个小于哨兵的值p0，将j的位置的值拿出来，哨兵值放到j的位置。p0则成为待放置的值。然后i走，找到第一个大于等于哨兵值的位置P0，就把p0放到i位置，然后P0候选。以此类推。简称为插队法。（这个方法没有深究，因此描述可能会有错）
本文讨论的是两边交换法。
流程
我们不讨论0个元素,1个元素和2个元素的特殊情况。
令数组长度为s。
算法首先选择第一个为哨兵。然后设置i为1，j为s-1。
i先走，找到一个大于等于pivot的数。然后j走，找到一个小于pivot的数。然后交换这两个数。那么，在某次交换完毕后，数组一定是下面这样的。
|0| |i| |j| |
---------------------------------------------------
|p| val < p | ? | val >= p |
---------------------------------------------------
中间未知区域可能有数字，也可能没有。
那么，因为当前i和j位置已经判断过了。我们下一次开始的时候，就先把i加一，j减一。
我设定i会超过j，while循环将会判断i <= j。这样的话，就能保证i和j相遇的时候，会得到ij指向的元素与哨兵的大小比较结果，然后移动。如果i和j相遇了就停止，好像就要另外判断当前元素与哨兵的情况。我也不太清楚哪个实现较好。
此时，有如下的情况。
?区域没有元素
此时，由于?区域没有元素，i和j就交错了，变成
|0| |j|i| |
---------------------------------------------------
|p| val < p | val >= p |
---------------------------------------------------
此时我们发现，j停在了val<p区域，而i停在了val>=p区域。这是一条非常重要的条件（算法书应该叫不变式invariant）。因为我们在任何i和j停下来的时刻，都要确保满足这个不变式。
?区域有一个元素
就像这样的，这时i还没加1，j还没减1。
|0| |i| |j| |
---------------------------------------------------
|p| val < p |n| val >= p |
---------------------------------------------------
然后i += 1, j -= 1，就成为
|0| |i j| |
---------------------------------------------------
|p| val < p | n | val >= p |
---------------------------------------------------
i和j相遇了。此时，又有两种情况
n < p
此时，由于n比p小，然后i会往前走一步，循环结束。如下
|0| |j|i| |
---------------------------------------------------
|p| val < p n| val >= p |
---------------------------------------------------
这时我们发现，i依然停在了val >= p的区域，j停在了val < p的区域。
n >= p
想一下这个情况也是一样的，最后依然保持了上面的不变式。
?区域有两个元素
此时，i和j各自指向一个未知的数字。要么两个数字均是小于p的，要么均大于等于p，要么是一个大于一个小于。计算一下的话，发现最后停止的时候，不变式是维持的。
更多的元素就不再讨论了。
极端案例
但是，仍然有两种较为极端的情况。
若没有val < p区域或val >= p区域呢？
没有val < p区域
|0|i| |j|
---------------------------------------------------
|p| val >= p |
---------------------------------------------------
i在开始时就会立即停下来，而j则能够一直走，直到穿过i，成为了
|j|i| |
---------------------------------------------------
|p| val >= p |
---------------------------------------------------
此时发现，不变式被破坏了。但是其实没关系，这件事下文再讲。
没有val >= p 区域
循环停止的时候，是这样的。
|0| |j|i|
---------------------------------------------------
|p| val < p |
---------------------------------------------------
发现，不变式也被破坏了。难道我们需要对这种情况特殊处理吗？
循环停止时的处理
我们先不考虑极端情况的话，对于上述其他情况应该怎么办呢？很明显可以看到，我们都可以将哨兵元素，与j位置的元素进行交换即可。因为j的位置一定站在小于p的区域，而哨兵又大于p，不属于这个区域。如果我们把j位置与哨兵交换，恰好哨兵就与右边区域连起来了。
如果循环停止时候如此
|0| |j|i| |
---------------------------------------------------
|p| val < p n| val >= p |
---------------------------------------------------
我们交换j与哨兵
| |j|i| |
---------------------------------------------------
| val < p |p val >= p |
---------------------------------------------------
恰好就分好两个区域了。计算下其他情况也是这样的。
极端情况处理
如果我们还是用上面的方法，可行吗？
假如是这种情况
|j|i| |
---------------------------------------------------
|p| val >= p |
---------------------------------------------------
发现j与哨兵位置重合了，交换不会有变化，所以是可以的。
如果是另外一个
|0| |j|i|
---------------------------------------------------
|p| val < p |
---------------------------------------------------
交换哨兵与j位置，发现
|0| |j|i|
---------------------------------------------------
| val < p |p|
---------------------------------------------------
刚好组成了两个区域，左边小于p，右边大于等于p。就算i是超尾了，因为我们不会动i的元素，所以问题不大。
综上，循环结束的时候，我们可以采取这种方式来处理哨兵的交换。
代码
结合上述的描述，就可以写出代码了。
void swap(int *array, int i1, int i2) {
int temp = array[i1];
array[i1] = array[i2];
array[i2] = temp;
}
/**
*
* @param array
* @param start 开始位置
* @param end 结束位置（不包含）
* @return 分区的位置，是高区域的开始
*/
int partition(int *array, const int start, const int end) {
if (end <= start + 1)
return start;
else if (end - 2 == start) {
// 针对只有两个元素的情况
if (array[start] > array[end - 1]) {
swap(array, start, end - 1);
}
return end - 1;
}
int pivot = array[start];
// 初始位置的设定
int low = start + 1;
int high = end - 1;
// high将会停止在小于pivot的数上，而low停止在大于等于pivot的数上
while (low <= high) {
while (array[low] < pivot && low <= high)
low++;
while (array[high] >= pivot && low <= high)
high--;
// 避免多余的交换和high low的位置变化
if (low > high)
break;
swap(array, low, high);
low++;
high--;
}
// pivot交换
swap(array, start, high);
return high;
}
