看到知乎上有这个讨论，程序员能20分钟徒手写出一个没bug的快速排序吗？

void quicksort(int l, int u){
    int i, m;
    if(l >= u) return;
    m = l;
    for(i = l+1; i<= u; i++)
        if(x[i] < x[l]) // buggy!
            swap(++m, i);

    swap(l, m);

    quicksort(l, m-1);
    quicksort(m+1, u);

}

还有何磊的解释

上面是他在 beautiful code 上的代码。
最核心的部分就是开始的那个for循环和swap了（paritition），这要怎么背呢？当然是用循环不变式了！
[l+1, m] 位置保存着当前已处理元素之中所有的小于pivot的元素
i指向的是下一个待处理的元素
第l个元素是pivot
循环开始时，[l+1, m]是空集，已处理元素也是空的，所以循环不变式成立。
for循环每轮把i加了1，这样就有可能破坏循环不变式，
怎么办呢，当然是：
在i加1之前，如果发现当前i指向的值小等于pivot，就将m自增1，并且和i指向的元素交换。
这样，循环不变式又成立啦。
在for循环结束后，循环不变式依然是成立的（根据数学归纳法~）
那么，它告诉了我们什么性质呢？
[l+1, m]之间包含了l 到 u 之间的小于 pivot 的元素，且第l个元素是pivot。
于是，我们只要将第l个元素和第m个元素交换，就完成了partition的操作，即：pivot在第m个元素上，m元素之前的值都小于pivot，之后的值都大等于pivot。

非常简洁，非常酷炫，但是有点bug（注意我注释的那一行）
这个partition在大量duplicate key的情况下，会把这些key全部放到左边或者右边。导致不公平的切分。

看懂理解之后，实在是太惊艳了，回想之前的快排，是这么写的。。http://zrj.me/archives/229，真是挫啊。。。