首页 > 代码库 > 难以写对的quicksort
难以写对的quicksort
摘要：quicksort是Donald发明的算法，是平均性能最好的内排序算法。本文通过对照quicksort的标准写法和自己的写法，发现了一些隐藏的编程陷阱，故记录下来以供学习交流。
关键字：C/C++算法 程序设计 快速排序
1 quicksort的主要思想
从待排序的数组元素中选取一个作为中值元素（pivot），将原数组划分（partition）为2部分：小于pivot的放到左边，大于pivot的放到右边，然后对左右两边的子数组进行递归处理。如果能够保证每次划分都是均匀的话，由T(n)=2*T(n/2)+O(n)，可以得到其算法的平均时间复杂度为O(nlgn)，当然，如果不能保证的话，quicksort就退化成了O(n^2)的算法。
不幸的是，所谓的划分对于数组而言，其实就是swap。这也就意味着把一个思想转变成代码时，需要考虑一些实现上的细节问题。
2 我的第一版quicksort实现
代码如下：（partition子函数被省掉了）
void quick_sort(int A[], int length){
if(length>1){
int pivot = A[0];
inti=1, j=length-1;
while(i<j){
while(A[i]<pivot && i<length) ++i;
while(j>=0&& A[j]>pivot) --j;
if(i<j && i<length && j>=1){
swap(A[i], A[j]);//use std::swap
++i;
--j;
}
}
swap(A[0], A[j]);
quick_sort(A, j);
quick_sort(&A[j+1], length-j-1);
}
}
说明：
（1） C语言里如何描述一个数组？通常只需要数组元素的起始地址A（或&A[0]），和长度length即可
（2） 有些代码里选择pivot元素时，会从第1个、中间的、最后一个共3个元素中选择一个中间值，有的则使用了随机函数，不过本文更关心的是“如何写对quicksort”，对pivot如何选择并不关心，这里简单选择第一个A[0]作为pivot
（3） Partition部分：使用2个索引i,j，分别从左右向中间扫描，如果A[i]<pivot或A[j]>pivot，继续扫描，直到遇到相反的情形：A[i]>=pivot且A[j]<=pivot，这时交换A[i]、A[j]的位置。
不幸的是，上面的第一版代码是错的！先不忙参考正确的版本是怎么写的，让我们先写点测试代码吧。
3 测试代码
void display(int A[], int length){
for(inti=0; i<length; ++i) cout<<A[i]<<",";
cout<<endl;
}
#define TEST(A) {\
quick_sort(A, LENGTH(A));\
display(A, LENGTH(A));\
}
#define LENGTH(A) sizeof(A)/sizeof(A[0])
int main(int argc, char** argv){\
{intA[]={1,2}; TEST(A)}
{intA[]={2,1}; TEST(A)}
{intA[]={1,2,3}; TEST(A)}
{intA[]={3,2,1}; TEST(A)}
{intA[]={2,2,2}; TEST(A)}
{intA[]={1,2,3,4}; TEST(A)}
{intA[]={4,3,2,1}; TEST(A)}
{intA[]={2,3,2,1}; TEST(A)}
{intA[]={5,4,3,2,1}; TEST(A)}
{intA[]={1,2,3,4,5}; TEST(A)}
{intA[]={3,1,3,3,2}; TEST(A)}
}
输出：
2,1,
1,2,
1,3,2,
2,1,3,
2,2,2,
1,2,4,3,
1,2,3,4,
1,2,2,3,
1,3,2,4,5,
1,2,3,5,4,
1,2,3,3,3,
惨不忍睹。哪里错了？
4 看一下标准写法
代码来源：《计算机算法设计与分析（第4版）》（王晓东,电子工业出版社），及《编程珠玑》中的qsort3。
int partition(int A[], int p, int r){
int i=p, j=r+1;
int x =A[p];
while(1){
while(A[++i]<x&&i<r);
while(A[--j]>x);
if(i>=j)
break;
swap(A[i], A[j]);
}
A[p]=A[j];
A[j]=x;
return j;
}
void quicksort(int A[], int p, int r){
if(p<r){
intq=partition(A, p, r);
quicksort(A, p, q-1);
quicksort(A, q+1, r);
}
}
5 代码分析
首先注意到的是，这个实现里数组用3个参数来表示：起始地址A、起始下标p、结束下标r，A在整个代码里是不变的。q代表partition操作后pivot应该被放置的位置。用这个版本的代码进行测试：没有问题。那么第一个版本的代码到底错在哪里呢？
OK，现在对照一下前后的实现，看看差别到底在什么地方？
1、 首先，我的quick_sort在swap(A[i],A[j])之后进一步移动了i,j的位置，但这是画蛇添足，不需要的；
2、 其次，标准quicksort写法里i,j初始化为范围外的值！这里intx=A[p];一行表明pivot选择跟我的做法是一样的，就是第一个元素，但是i,j分别初始化为p,r+1，这个就不一样了。但是这个有关系吗？
3、 内层的2个while循环，我的quick_sort是先使用，再做++,--（移动操作）。而标准quicksort写法则是先++,--，然后再做判断。那么，可以认为这两者本质上都应该是可以的
但是，设想一下，假如i,j向中间“挤压”的过程中，遇到的元素全部等于pivot呢？这种情况下，我的代码会导致死循环，然而标准quicksort写法很神奇地没有任何问题！
4、 再次检查内层的2个while循环：
a) 第一个内层while循环的条件（或者理解为“循环不变量”，请参考《编程珠玑》一书！），
我的quick_sort写成了：A[i]<pivot&& i<length
而标准quicksort写法是：A[++i]<x&&i<r
靠！你看出差别在哪里里吗？我使用的约束条件只要求i不要越过数组的下标范围，而标准写法加强了这一约束，进一步要求i不要越过j的初始位置！！！
b) 那么，再看第二个内层while循环，依据前面的推论，也应该有A[--j]>x && j>p，可惜的是，标准quicksort写法直接把&& j>p部分省掉了。虽然这么做也许有道理，但我不建议这么做，——破坏代码的结构对称性也就是损失了代码的美感，没必要这么做啊。j>p相当于j>=p+1，在我的版本里写成j>=1。
OK，终于找到最关键的地方，修改：
void quick_sort(int A[], int length){
if(length>1){
intpivot = A[0];
inti=1, j=length-1;
while(i<j){
while(A[i]<=pivot && i<length-1) ++i;
while(j>=1 && A[j]>pivot)--j;
if(i<j && i<length && j>=1){
swap(A[i], A[j]);//use std::swap
}
}
swap(A[0],A[j]);
quick_sort(A, j);
quick_sort(&A[j+1], length-j-1);
}
}
结果：还是错的！
到底遗漏了什么？！OMG。
首先，注意到只有2个元素{1，2}的case居然是错的，这种情况下，我们来在大脑里模拟执行一下程序（模拟不了用调试也可以）：i，j初始化时都是1；然后while(i<j)不满足，直接跳过；如果这时候直接swap(A[0],A[j]);的话…靠，这样不反过来了嘛！加上一个guard/check：if(A[0]>A[j])swap(A[0],A[j]);
void quick_sort(int A[], int length){
if(length>1){
intpivot = A[0];
inti=1, j=length-1;
while(i<j){
while(A[i]<=pivot && i<length-1) ++i;
while(j>=1&& A[j]>pivot) --j;
if(i<j && i<length && j>=1){
swap(A[i], A[j]);//use std::swap
++i;
--j;
}
}
if(A[0]>A[j]) swap(A[0],A[j]); //fix case {1,2}
quick_sort(A, j);
quick_sort(&A[j+1], length-j-1);
}
}
OK，做了这1处修改后再测试：现在没问题了。
实际上，回过头来可以发现，这处修改正好就是为了解决2个元素的如{1,2}做快速排序的边界情况。因为大的数组做快速排序递归调用，最终仍然会在某个点上回到2个元素的情况，如果对这2个元素的排序错误，则显然，最终结果也就错了。
标准写法里的int i=p, j=r+1;实际上是相当精辟的，实际上初始化位置是待partition部分的范围外位置。这实际上统一了边界条件，使得对{1,2}这种2个元素的情况不需要再做特殊处理。而我的代码把i,j的初始化值放到待partition部分的范围内部边界位置，这就导致了额外的条件判断处理。
6 结论
quicksort实在不是一个容易写对的算法。当然，我也不建议死记硬背这些经典算法的代码，那样的话，实际上还是没有真正理解这个算法。虽然我自己的版本的快速排序代码最终通过测试，但额外却多了不少检查条件，相对来说，似乎不如标准写法简洁（优美？）
下面是总结的经验教训：
（1） 为算法编写完善的测试用例，必要的地方可使用断言；
（2） 尤其要注意循环不变式（while循环的条件）和赋值操作的前提条件（if语句），因为这些是保证程序正确性最重要的地方。
最后留个课后作业：假如选择最后一个元素作为pivot，则函数quick_sort需要做哪些修改呢？
难以写对的quicksort