【七类排序】之第四种：快速排序

惰性又发作， 有点不想写下去了， 坚持一步算一步吧。。终于进入了n*log n的时代， 到了快速排序， 虽然可以不理n^2了， 但是思想千万别忘。

注：若无特殊说明， 排序以递增为目的。
快速排序（Quick Sort）是由C.R.A Hoare在60年代提出的。 其策略是 交换划分与分治法。 尤其是后者---分治法是很常用很重要的算法策略， 许多公司面试经常考察。 快排的重要性， 我觉得要了解其原理，并且3分钟内写出快排的核心代码部分是有必要的， 2分钟内算基本合格。

我们假设n个元素的数组a[0..n-1],快速排序算法每个步骤和策略是：
1：选择一个基准元素a[k]
2：让大于等于a[k]的数组元素在其右边，小于a[k]的在其左边
3：对a[k]左右边区间的元素重复1,2步，直到左右区间小于等于一个1。

步骤3是快速排序分治策略的体现，然而， 单独的分治法又不能诠释步骤2. 步骤2的实现是最难的一步。于是， 我将步骤2称作交换划分。那么，分治可以通过递归实现， 那么该如何实现交换划分？ 笔者这里介绍一个自己摸索出来的实现方式。 欢迎大家给出更简洁高校的代码， the easier, the better!
交换划分的算法方法如下：

我们选定基数int standard=a[start]作为划分基数， 然后 用两个指针， p=start,区间起始位置 ,q=end, 区间结束位置。

若p<q 则做如下两步：
一：指针q从右向左扫描，直至扫描到小于standard的元素。
赋值给a[p]，p++。
二：指针p从左向右扫描， 直至扫描到大于或等于standard的元素。（为什么是大于或等于？ 请看算法步骤2第一句话）.
赋值给a[q]，q--。

做完以上两步后，判断p是否等于q， 若p<q， 则继续重复”一"和“二”。p与q终有相遇之时， 即最后将使得p=q，则停止。
千万不要忘记了一件事， 那就是，standard要放回数组， 即a[p](或a[q])=standard， 这样a[p]（或a[q]）左边都是小于standard的元素， 右边则是大于等于standard的元素

以上，通过交换划分， 我们成功的将元素隔离开来， 接下来是分治。 即用同样的方法处理a[start..p-1]和a[p+1..end]， 递归即可。
举例说明交换划分的过程, 设数组a[0..7]一共有8个元素，

0	1	2	3	4	5	6	7
27	13	46	25	88	72	19	56

第一次交换划分过程如下。

初始化，p=0, q=7, standard=a[p]=27

q=7， 往左边扫描， 发现接下来小于standard的值是a[q]=19, 此时q=6。 将a[q]赋值给a[p]，p++，得到数组：

0	p=1	2	3	4	5	q=6	7
19	13	46	25	88	72	19	56

p=1, 继续往右边扫描， 接下来大于等于standard的值是a[p]=46， 此时p=2。将a[p]赋值给a[q],q--, 得到数组：

0	1	p=2	3	4	q=5	6	7
19	13	46	25	88	72	46	56

步骤“一”和“二”走了一遍， 此时p=2小于q=5,两者并未相遇 重复。

q=5， 往左边扫描， 发现接下来小于standard的值是a[q]=25, 此时q=3。 将a[q]赋值给a[p]，p++，得到数组：

0	1	2	p=q=3	4	5	6	7
19	13	25	25	88	72	46	56

突然发现此时p=q， 已经相遇， 于是将standard放回， a[p]=27, 最终得到如下数组：

0	1	2	p=q=3	4	5	6	7
19	13	25	27 (standard放回)	88	72	46	56

此时左边都是小于standard的元素， 右边反之。  交换划分完成。

紧接着只需要如法炮制（a[0]..a[2]）以及(a[4]..a[7])， 递归实现即可。

实现代码如下：
void Qsort(int start, int end) {
        if (start<end)   //想想为什么要判断
        {
                int standard,p,q;
                // swap(a[p], a[(start+end)/2]); 取中间位置的值为基准数， 用不用也不影响正确性。
                p=start; q=end; standard=a[p];
                while (p<q)
                {
                        //步骤1
                        while (a[q]>=standard && p<q) q--;
                        if (p<q)
                                a[p++]=a[q];

                        //步骤2
                        while (a[p]<standard && p<q) p++;
                        if (p<q)
                                a[q--]=a[p];
                }
                a[p]=standard; //把standard放回数组， 划分交换完毕

                //分治
                Qsort(start,p-1);
                Qsort(p+1,end);
        }
}


红色部分说明： 笔者描述的快速排序算法， 初始化时选择的基准值standard为a[p], 即该段数组区间的第一个值。 考虑最坏情况，若数组本身有大段的有序， 逆序特征， 划分交换步骤的复杂度将较高， 递归的深度将出现极端情况（仔细思考交换划分和分治的过程， 为什么？）。 因此， 我们可以
1:选取中间的元素作为基准值，standard=a[(start+end)/2]
2:随机选择一个元素做基准值， standard=a[random(start,end)]。
这样将能改善这种情况。


总结：快排的思想， 很多人都知道， 其核心在于实现划分交换。 而根据笔者经验来看，这是最容易出错的地方，徐多人自主实现的时候会出纰漏， 要么就是判断条件出错， 要么就是忘了步骤，大家一定在理解原理的基础上写代码。 同时，该部分的实现方式也很多种多样， 欢迎高人提出更精简， 更方便于理解的形式。 最后，笔者向各位提一个要求，面试的时候，无论怎么写，该排序能在2分钟之内流畅地写完。

要不要研究一下不用递归写这个。。。。
感觉这个要求就有点蛋疼了。 不过应该不算太难。 开一个stack 存 start end 这两个指针就行

ilhrx 发表于 2012-12-4 07:18
要不要研究一下不用递归写这个。。。。
感觉这个要求就有点蛋疼了。 不过应该不算太难。 开一个stack 存 s ...

有什么公司的面试题有过这个要求吗？

如果没有或者很少， 代码还是要保证KISS守则的。

我印象中， 能一口气写完快排不出错的人， 不是很多。
如果你有什么更简洁的写法都欢迎提出来。

楼主写得用心啊，赞一个！
俺把我以前用的qsort贴出来供参考（年代久远了，PASCAL写的，见谅）：

1. procedure qsort(l,r:longint);
   
2. var
   
3.    i,j:longint;
   
4. begin
   
5.    i:=l;
   
6.    j:=r;
   
7.    m:=dat[(l+r) div 2];
   
8.    repeat
   
9.       while dat[i]<m do
   
10.          inc(i);
    
11.       while dat[j]>m do
    
12.          dec(j);
    
13.       if i<=j then
    
14.          begin
    
15.          t:=dat[i];
    
16.          dat[i]:=dat[j];
    
17.          dat[j]:=t;
    
18.          inc(i);
    
19.          dec(j);
    
20.          end;
    
21.    until i>j;
    
22.    if j>l then
    
23.       qsort(l,j);
    
24.    if i<r then
    
25.       qsort(i,r);
    
26. end;

复制代码

我想有两点值得LZ注意一下。
一是你处理等于号的方式会导致在数据重复时退化（例如，如果待排序的所有数都是一样的，这个算法就变成O(n^2)了）
二是建议把start<end放在递归调用之前，这样可以减少一层递归深度。

俺本科学的ME，现在刚开始往CS转，所以现在还是中学信息学竞赛的思维。如果俺的东西有问题的话请提出来讨论吧～谢谢

lunaughty 发表于 2012-12-4 16:54
楼主写得用心啊，赞一个！
俺把我以前用的qsort贴出来供参考（年代久远了，PASCAL写的，见谅）：我想有两点 ...

这个pascal快排的版本，一看明显就是有OI经验选手的写法， 你给这份代码的确是我所知最短的， 可我感觉不是很利于教学上的理解。

关于你说的两点是正确的。

Sorry~没意识到这是个教学贴哈哈。以后有问题多来版上讨论:)

lunaughty 发表于 2012-12-4 20:15
Sorry~没意识到这是个教学贴哈哈。以后有问题多来版上讨论:)

不是的， 我能力有限， 给不出那份精简代码的完美教案。

因为算法默写出来永远不如自己按照理解写出来。 你如果有对精简代码给予很好的解释的能力， 每一步为什么需要这样做？欢迎提出来。

嗯我表述能力不行，我试试简单讲一下吧。
首先是代码的正确性：我的代码的思路是维护两个指针i,j，保证所有在i左边的数都小于等于标准值，所有在j右边的数都大于等于标准值。每次repeat循环都尽量让i,j靠拢，当它们靠在一起之后就跳出。
跳出后同样有所有在i左边的数都小于等于标准值，所有在j右边的数都大于标准值。这样一来就满足了分治的条件。递归即可。

其次是关于等号的处理：前面两个while循环中之所以不写等号，是为了在大量数据重复时使i,j向中间靠拢的速度相等（每个repeat循环移动一步），避免i,j靠拢时偏向一边的情况。
当然这样也不能保证不退化，反正快排的nlogn都是摊还分析出来的，真的需要严格nlogn的话就用堆排好了。

希望对大家有帮助

北美农民 发表于 2012-12-4 11:25
有什么公司的面试题有过这个要求吗？

如果没有或者很少， 代码还是要保证KISS守则的。

KISS 守则？求科普

现在刷leetcode 有时候就会有遍历二叉树 不用递归之类的要求。不过这些东西跟算法无关，感觉很tricky的东西

ilhrx 发表于 2012-12-5 01:50
KISS 守则？求科普

现在刷leetcode 有时候就会有遍历二叉树 不用递归之类的要求。不过这些东西跟算法无 ...

KISS=Keep It Short&Simple

可能两个S我理解有出入， 但终究是为了readable and maintainable