划分的invariant
画invariant示意图，加上待处理共三段，两指针指向第一段最右、第三段最左。
从左到右划分：首元素t作pivot后，分三段：<t、>=t、待处理；初始化两指针使第一段<t为空 m=l、全是第三段待处理 i=l+1，主循环右移待处理指针i，见pp p112。记住这种写法。
|t| <t | >=t | ? |
l m i u
int t = a[l];
int m = l;
for (int i = l + 1; i <= u; i++) {
if (a[i] < t) swap(++m, i); // 往左抛
}
swap(m, l);
从右到左划分：首元素t作pivot后，分三段：待处理、<t、>=t；初始化两指针使第三段>=t为空 m=u+1、全是第一段待处理 i=u，主循环左移待处理指针i，见pp p210。不用记这种写法。
|t| ? | <t | >=t |
l i m u
int t = a[l];
int m = u + 1;
for (int i = u; i > l; i--) {
if (a[i] >= t) swap(--m, i); // 往右抛
}
swap(--m, l);
双向划分：首元素t作pivot后，分三段：<=t、待处理、>=t，两端范围都带等号；初始化两指针使第一段<=t为空 i=l、第三段>=t为空 j=u+1，loop中用do...while移动i、j指针，见pp p114。不用记这种写法。
|t| <=t | ? | >=t |
l i j u
int partition(int l, int u) {
if (l >= u) return;
swap(l, randint(l, u));
int t = a[l];
int i = l, j = u + 1;
while (true) {
do { i++; } while (i <= u && a[i] < t); // 停下时>=t
do { j--; } while (j > l && a[j] > t); // 停下时<=t
if (i > j) break;
swap(i, j);
}
swap(j, l);
return j;
}
loop中用while移动i、j指针，写法微调，记住这种写法。
// 双向划分
int partition(int l, int u) {
if (l >= u) return l;
swap(l, randint(l, u));
int t = a[l];
int i = l + 1, j = u; // 初始时多个步进
while (true) {
while (i <= u && a[i] < t) i++; // 停下时>=t
while (j > l && a[j] > t) j--; // 停下时<=t
if (i > j) break;
swap(i, j);
i++; j--; // 循环中也多个步进
}
swap(j, l);
return j;
}
三路划分：将数组分为<t、=t、>t三段
从左到右划分，遇到<t的往左抛，遇到>t的往右抛，=t的就会留在中间。
用i指向<t的待写入位置，j指向待处理位置，k指向>t的待写入位置。
|t| <t | =t | ? | >t |
l i j k u
int t = a[l];
int i = l+1, j = l+1, k = u;
while (j <= k) {
if (a[j] < t) { swap(j,i); i++; j++; }
else if (a[j] > t) { swap(j, k); k--; } // 因为从右边换过来的还待处理，不用j++
else { j++; }
}
swap(--i, l);
另：二路划分若用三路划分往两端抛的思路写，同样从左到右划分，但比标准写法繁琐：
int t = a[l];
int i = l + 1, j = u; // i指向<t的待写入部分，j指向>=t的待写入部分
while (i <= j) {
if (a[i] < t) { i++; }
else { swap(i, j); j--; }
}
swap(j, l);