059 | 快速排序：要想提高效率就要少做事情

上次讲到了好的算法和坏的算法区别有多大。再往前想一步，世界上已知的最好的算法是什么呢？在评判“最好”之前，我们还是要加一些限制条件，比如是一般情况下最好，还是恶劣的情况下最好。

为了便于理解这两种情况的差别，举个例子。从北京东三环到机场，最短的路线是从个三元桥到机场高速，大约40分钟。但是，如果东三环出现了有点意外的交通情况，这条路恐怕就要花两个小时。如果要避免在这种倒霉情况下误了飞机，一个办法是走东四环然后上第二机场高速，后者比较偏僻，车比较少，即便遇到交通事故，也不会堵死。通常来讲，它比第一条路线慢15分钟，但是，在极端情况下，它比第一条路线快半小时。稍微有点生活经验的朋友都会知道，世界上，没有绝对的最好。

类似的，计算机算法常常也是如此，最好的总是有附加条件。如果运行一个程序，实时性要求不是那么高，可能应该采用算法A；如果实时性要求非常严，比如下围棋进入了读秒阶段，就需要算法B了，因为后者在遇到倒霉的情况时不会太糟糕。讲会到排序这件事，目前世界上通常情况下孔的算法是一种叫做“快速排序”(Quiucsort)的算法，它是有英国科学家托尼·霍尔(Tony Hoare)与1959年想到的，1961发表的，这个算法也成功了今天世界计算机产业中使用最多的排序算法，霍尔因此获得了爵士头衔，也成为第一个获得这种头衔的科学家。那么，快速排序为什么快呢？原因很简单，它还是强调少做事情。其原理大概是这样的：

• 第一步，对于一大堆无序的数字，从中随机挑选一个，比如是53，这个被随机选上的数字被称为枢值，接下来，将所有要排序的数字分成两部分，第一部分是大于等于枢值53的，第二部分是小于枢值53的。在第一步完成后，一大堆无序的数字就变得稍微有序一点了。
• 第二步，从上面得到的两堆数字，分别采用第一步的方法各自再找一个枢值。对于第一堆，由于所有的数字都比53大，至少也等于53，因此，第二次随机挑选的枢值肯定是一个大于53的数字，比如79；类似地，对于第二堆，由于所有的数字都小鱼53，因此第二次随机挑选的枢值肯定小于它，比如4。接下来，再把两堆数字各自分成大于等于相应枢值的数字序列，以及小于枢值的数字序列。这样做下来，原来的一大堆数就变成了4小堆，它们分别是：小于4的数字，介于4到53之间的，介于53到79之间的，以及大于或等于79的。
• 再接下来，用同样的办法，4堆变8堆，8堆变16堆，很快所有的数字就排好序了。

这种算法通常情况下复杂度也是N * log(N)，和昨天介绍的归并排序相同。根据计算机科学的标准，它们同样好，不过在工程上，快速排序法(Quicksort algorithm)一般情况下比归并排序(Merging Sort Algorithm)快两倍，因此，在工程上还是有意义的。这也是为什么很多人用它的原因。至于为什么快速排序能够更快一些？这可以在计算机科学上证明，不过为了方便理解，我一个比方你就明白了。假如哟一个学区，里面有2000名高中学生，如果让大家到一个超级大的学校上课，再从中挑出学生中的尖子，效率一定高不了。这就相当于是昨天一开始讲的冒泡排序 ，每一个人都要和所有人去比。如果我们把2万人放到10所学校中，每所学校有2000人，从各个学校先各自跳出学习尖子，再彼此进行比较，这就有效得多了。这就是昨天说的归并排序原理。如果我们先划出几个分数线，根据个人成绩的高低把2000个学生分到十所学校去，第一所学校里学生成绩最好，第十所最差，再找出学习尖子，那就容易了，工作量最小，这就是快速排序的原理，这也是快速排序比昨天讲的归并排序快的原因（少干了太多太多没必要的比较）。

其实，计算机算法和组织的管理，乃至社会的管理，在道理上有想通性，想要提高效率就是要少做事情。一个社会的管理，要想效率高，最简单的办法就是对每一个作一些区分，而效率最低的办法就是刻意追求所有人一律平等，不作区分。可以想象，当一个学校的学生水平都比较接近，老师教起来就容易，因此按照成绩对学生作一个初步的划分是有道理的，特别是在资源不足的情况下。反之，如果一个学校的学生从100分的到0分的都有，那么老师教起来就困难了，如果想达到前面同样的效果，就必须投入资源。从对比快速排序和归并排序大约三倍的效率之差，我还得到一个启发，那就是为什么美国私营公司的效率会比政府高很多。美国的政府和社会要讲究民主和平等，但是美国的公司从来不讲这一套，公司里的大事从来不会和每一个员工商量，行政的层级就如同快速排序事先划定的枢值，有了三六九等，公司才有效率可言。因此，当一个年轻的员工新入职后，处于最低的层级时，不要指望公司的政策是照顾底层的员工，因为那样的组织没有效率，没有效率的组织在竞争中是要死掉的，当一个公司死掉后，任何理想都化为了泡影。所以，每个底层员工所思考的事情，是如何进入更高的层级，这也是我从来不强调底层思维的原因，如果大家将来想不断上升，必须要有高层思维。底层思维，后者心灵鸡汤（呵呵），无异于是一种毒药。如果你还在庆幸自己进入了一个最底层员工的工资和总经理的差不多的单位时，趁着年轻赶快离开，因为这样的公司也是要死掉的。

我从今天一开讲，快速排序是通常情况下最好的算法，但是，在极端的情况下，它的复杂度是N^2，和冒泡排序一样糟糕。而归并排序，即使在最坏的情况下，也能保证N*log(N)的复杂度，当然工程师们会想一些办法防止这种情况发生。从这个例子可以看出，世界上没有绝对的好，常常有一得便有一失。

在腾讯面试工程师时，曾经遇到过一个学习计算机的学生，总是不相信排序算法的速度是有极限的，我给他看数学上的证明，他因为数学基础有限看不明白，于是我在想，这个人和痴迷永动机的人没有什么区别，没有救了。话时间培训这样的人是瞎费工夫，最好的办法就像是芒格说的那样，将那种人排除在组织之外。

上面就是我从快速排序中悟出的生活里的思维方式，希望对你有所启发。



Q：从快速排序对效率的提高，你有什么对生活和工作的感悟？
A1：当今，有一个非常非常重要的能力，就是收集和处理信息的能力。繁杂的信息，根据轻重缓急，分为四类：

• • 重要而紧急的
  • 重要但不紧急的
  • 紧急但相对不重要的
  • 不重要且不紧急的
• 首先，找到一个显而易见的待办事项（枢纽），接着综合考虑紧迫性和重要性，分成两拨；再将两拨事情再找枢纽，就把所有的工作依照评分分成了四份。

A2：外包、找家政、找中介、找外卖等等背后的逻辑

• 值不值得做？ —》 能找人代替吗？ —》 找谁？ —》 代价能接受吗？ —》 有没有更好的办法？ 

​