图书馆刘大妈除了要帮我找对象，还教我排序算法

1

一次关于排序的偶遇

今天，在图书馆发生了一件事。

图书馆书架

新来的志愿者小王被安排将归还的书整理回书架，初次被委派工作的小王瞬间充满热情。然而。。。

面对地上一大堆书籍，小王瞬间懵了，手足无措，望书兴叹。

此时老图书馆管理员刘大妈向小王款款走来：小伙子，今年几岁了，有没有女朋友，大妈帮你介绍一个，你喜欢什么类型。。。

小王瞬间再次懵了：大妈，现在是科普频道，不是《非诚勿扰》。。。

刘大妈此时才缓过神来：像你这样整理，不知道要整理到何年何月，一般呢，你就这么排书，随便在这堆书当中抽出一本书，把比它大号的放在左边，比它小号的书放右边，完了以后，你们继续在每一堆继续这样排，这样排得快。

小王在旁边一听，感觉怎么这么熟悉：我的天，竟然连图书馆管理员都学排序算法吧！这图书馆有...

要知道快速排序算法是人类当今最最常用的，计算效率方面最优秀的排序算法！管理员刘大妈竟然深谙此道，把这个算法用到排书上。

快速排序的过程示

快速排序算法（Quick Sort），顾名思义他的排序速度很快。快速排序算法在1959年由英国科学家托尼·霍尔（Tony Hoare）发明。

2

快速排序怎么来的？

1959年，托尼·霍尔当时在莫斯科国立大学作为访问学生，参与到莫斯科国家物理实验室的一个机器翻译（Machine Translation）项目。其中有一个技术点是，需要对俄语句子进行排序。

霍尔首先想到的是插入排序，可是霍尔嫌弃它的效率太低了。为此，霍尔详尽各种办法，终于想到了一个更好的排序思路（快速排序的雏形），并且写出了代码。原本准备开始大展拳脚之时，没想到算法中还存在一些不能被排序的部分，无奈之下，霍尔只能选择搁置了。

博士毕业回到英国以后，霍尔在埃利奥特兄弟公司（Elliott Brothers, Ltd.）任职。

有一天，霍尔的老板让他用希尔排序（Shellsort）的代码对一份材料进行处理。霍尔告诉他的老板：

BOSS，我觉得希尔排序还是慢了，我有一个新的算法，效率可以更快，你信不信？

霍尔的老板一听，这怎么可能，还有比希尔排序更快的算法。“小兄弟，我也是技术出身，你可别逗我，怎么会有比希尔排序更快的算法。行，我赌六便士，赌你做不出来。”

霍尔自然接下挑战，这一次霍尔很快就把新算法写出来了，从时间复杂度上完胜希尔排序。

霍尔的老板虽然输掉了赌注，但是非常赏识眼前这位年轻人。后来霍尔参加了由Dijkstra（传送门）举办的ALGOL 60培训班，了解到ALGOL 60具备实现递归的能力，促使他设计了ALGOL 60的一个商用版本。

ALGOL ，为算法语言（ALGOrithmic Language）的缩写，是计算机发展史上首批产生的高级程式语言家族。

这个版本在执行效率和可靠性上都在当时ALGOL 60的各个版本中首屈一指，不仅受到了老板的重视，荣升公司的首席工程师，而且受到了国际学术界的重视。由于在编程语言定义和设计方面的基础性贡献，霍尔获得了1980年的图灵奖。

中国版的ALGOL 60的教材。ALGOL 60作为人类最早期的高级语言，拥有世界范围内的影响力。

3

什么是快速排序？

快速排序是目前处理大数据最快的排序算法之一。快速排序的思路非常清晰，简单地说，就是对要排序的数，随意以一个基准分成两部分，其中一部分比另一部分要小。然后再继续分别对这两部分进行排序。

快速排序具体的算法步骤如下：

Step 1：基准选取：从数列中选取一个元素，称为基准（pivot）。

Step 2：数列分割：重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面。最终该基准就处于数列的中间位置。这个是分割操作（partition）。

Step 3：递归执行：对小于基准值元素的子数列和大于基准值元素的子数列分别执行快速排序。

举个例子，我们尝试用快速排序对这个数列进行升序排列：

Step 1：首先，需要找一个基准，我们就找第一个数字6，作为基准。

Step 2：我们要达到一个目标，用基准将数列分割成两部分，得到以下这种排列：

其中，6左边的所有数字不大于6，6右边的所有数字不小于6。为了实现这个效果，需在数列内部执行元素的移位。

首先，设置两个变量，分别是变量i和变量j。变量i和变量j起始位置分别是1和10，我们可以假想他们是两列马车，分别往对面方向开。

马车i的任务是一步步往右走，如果遇到大于基准6的数字就停下来。马车j的任务则相反，一步步往左走，如果遇到小于基准6的数字就停下来。后来，马车i停在了7上，马车j停在了5上，这个时候我们对调7和5的位置。

交换位置以后的结果如下：

交换以后，马车i继续往右走，马车j继续往左走，马车i停在了9上，马车j停在了4上。此时再次进行交换。

第2次交换位置以后的结果如下：

交换以后，马车i继续往右走，马车j继续往左走。假设马车j先走，马车j停在了3上，马车i再走，走到3这里与马车j碰上停下来了，此时马车i和马车j的探测任务完成了。我们将基准数6与3进行交换。

第3次交换位置以后的结果如下：

这样，对于数列的分割就完成了。

Step 3：继续对分割出来的两部分数列，继续进行快速排序的递归操作。

执行完这3步以后，快速排序的操作就完成了，序列变成有序序列。

4

快速排序的时间复杂度

同一问题，比如以排序为例，同样的排序问题，可以用不同的算法来解决。而算法设计的优劣将影响到算法的工作效率，那么如何比较不同算法之间的工作效率呢？

算法的时间复杂度，解决了这个效率比较的问题。时间复杂度是一个函数，它定性描述了算法的运行时间，通常用大O符号来表述。

常见的算法时间复杂度由小到大依次为：

常数阶Ο(1)＜对数阶Ο(logn)＜线性阶Ο(n)＜线性对数阶Ο(nlogn)＜平方Ο(n²)＜立方阶Ο(n³)＜…＜指数阶Ο(2ⁿ)＜阶乘阶Ο(n!)。

科学家们发明了大量的排序算法，我们可以总结几种常用的排序算法的时间复杂度在时间复杂度上的表现：

冒泡排序的时间复杂度为Ο(n²)，表示随着数据规模n的增加，所耗费的时间呈n²速度增长。而快速排序的时间复杂度为Ο(nlogn)，比Ο(n²)降低了一个数量级，具有重大的理论意义与实际价值。（小智写过归并算法和堆排序的相关介绍）

这就是研究排序算法的原因所在。如果排序算法仍然沿用O(n²)数量级的算法，尤其是在数据量日益增加的今天，所耗费的计算资源将大大增加，稍微大一点规模的数据将无法处理。