首页 > 代码库 > 难以写对的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