从排序这个小问题说起（算法一）

原创我是可乐可乐

程序设计 = 算法 + 数据结构

一. 序

一直想说说算法，但是算法给人的感觉不怎么亲切。提到算法，最大的感受可能就是晦涩难懂。

我之前曾写过两篇铺垫文章，主要说明衡量算法好坏的基础和标准。有了这部分基础，我们就可以稍微深入的聊聊算法了。后台回复『复杂度』阅读那两篇文章。

聊算法之前，需要明确两点：

其一，学习或者了解算法不要太功利，人一旦功利就不聪明了。今天所做的事所看的书，可能一辈子也没什么用，但是却可以让你的精神世界和物质世界多一些可能。
其二，算法确实有一定难度，一定程度上来说也是其魅力所在。但是算法也不是那么难，很可能只是因为你觉得算法应该很难，结果你看到算法就觉得很难，这有点墨菲定律的意思。

我们应该清楚，我们是学习算法，而不是研究或者发明算法。这就像你只是要学习如何开车，而不必在乎造车的复杂过程是一个意思。发明算法是个含金量很高的事，计算机科学家托尼·霍尔（Tony Hoare）因为发明了最常用的快速排序算法，而获得了英国女王伊丽莎白二世授予的爵士爵位。

我们生活在一个凡事都追求效率的时代，我们不可能一切都从头开始，有很多事情，都已经有很成熟的处理框架，我们要做的就是尽可能掌握使用更好框架的能力。算法便是这样，我们只要理解和使用已有的成熟的算法，就可以一览众山小了。

如果你还要问学习算法有什么用？我只能说，无用之用。做人不要太功利。

二. 算法入门

算法如何入门？思来想去，还是决定从计算机中最常见的算法——排序算法开始！

排序，简单的讲，就是按照某个特定的指标，按照递增或递减的顺序排列。比如说，一群人站在一起，我们可以根据他们的身高进行排序，也可以根据年龄进行排序，当然还可以按照智商高低排序。而要达到排序目的使用的操作方法就是排序算法了。

在计算机科学中，排序还分为内排序和外排序。内排序指的是需要排序的数据可以全部加载在内存中，包括暂时存储在外部磁盘存储器上的内存信息。外排序则是指排序内容无法全部加载到内存，大部分内容都存在外存储器中，需要分批加载到内存，然后调整排序。具有27亿活跃用户的Facebook，如果需要按照某个维度为用户排序，涉及的数据量之大，就不可能一下子全部加载到内存中处理，这就属于外排序了。我们一般说的排序算法，其实都是针对内排序而言的。接下来提到排序算法，默认都是针对内排序。

排序算法有什么用？毫不夸张的讲，排序算法可以说是现实问题与计算机程序的桥梁。电商购物网站展示商品是需要排序的，支付宝的消费订单是要排序的，Excel表格最常用的功能之一也是排序。

排序算法有多少种呢？问这种问题总有点孔乙己的感觉。有多少种排序算法不重要，重要的是理解从直观到抽象排序算法的转变，层层递进，步步深化。

2.1 选择排序(Selection sort)

给定6、3、5、7四个数，怎样把它们从小到大排序呢？你肯定会说，一眼就看出来了，3、5、6、7。是的，四个数字一眼就看出来了，要是给你一万个数字呢？这就得让计算机来解决了吧。我不妨猜一下你排序的方法，你首先扫描这四个数字，很快找到最小的数字3，然后在剩下的数字中找到了5，以此类推。

这其实就是一种排序算法，基本原理就是一遍一遍的扫描数据，每次找到里面最小或者最大的数据，把这个数放到最开始的位置。然后从第二个数开始扫描剩余的数据，找到次小的数，将其放到第二个位置。以此类推，直到需要扫描的数字只剩一个。这种排序算法被称之为选择排序(Selction sort)。

以6、3、5、7四个数为例：

第一次扫描发现3最小，将3与第一个数交换，变成3、6、5、7
第二次从6开始向后扫描，发现5最小，将5与第二个数6交换，变成3、5、6、7
第三次从第三个数6开始扫描，发现没有比6小的数，而且剩余的数只剩下一个7了，排序结束

这种算法好不好呢？之前介绍算法复杂度的文章中提到过，选择排序的算法复杂度是O(n²)。这里不再赘述，直观的感觉就是比较慢。

这种算法有没有问题呢？如果给序列1、2、3、4排序，人眼一看就知道，已经是有序的了。但是计算机没有这种能力，它只会按照人设计的算法去执行。用选择排序算法，计算机依然会先拿第一个数和2、3、4比较，然后再拿2与3、4比较，以此类推。也就是说，计算机还是会执行所有无效步骤。

是否可以改进呢？可以的。我们上面的操作，每次只找到最小或最大的两个数中的一个，那为什么不每扫描一遍数据，就把最小和最大的数都找出来呢？把最小的放到数据开头，最大的放到数据末尾。当然，这种方法还是无法解决有序数据需要多次扫描的问题。

2.2 冒泡排序(Bubble sort)

选择排序，每次扫描都是找到一个最小或最大的数，做一次数据交换，那是不是可以从第一个数据开始，就做交换呢？以7、5、3、6为例：

第一步，7和5比，发现7比5大，交换位置变成5、7、3、6
第二步，比较7和3，发现7比3大，交换位置变成5、3、7、6
第三次比较7和6，发现7比6大，交换位置变成5、3、6、7
这样一遍扫描下来最大的数7被移到了最后。第二遍扫描只需要扫描5、3、6就可以了。然后重复以上步骤。

这种排序方法一般被称为冒泡排序(Bubble sort)，据说这种称呼很直观，但我觉得除了平添误解，并没有什么卵用。用这种算法解决有序数据1、2、3、4的排序会怎样呢？第一遍扫描，发现不需要做任何交换，也就是说，每一个数都比后一个数小，说明数据已经有序了，不需要继续扫描了。对于计算机程序实现而言，只需要增加一个变量，记录每一次扫描是否发生过数据交换，如果没有，就完成排序。这样对于有序数据只需要扫描一次就可以完成排序了。是不是很厉害。当然，冒泡排序的算法复杂度依然是O(n²)。

2.3 插入排序(Insertion sort)

再问一遍，茴香豆的“茴”有几种写法呢？打牌晓得吧？玩扑克时，摸完整副牌，我们手里的牌就是有序的。怎么做到的呢？

我们摸到第一张牌时，不管三七二十一，先放手里，然后摸第二张牌时，要是比第一张小就放最前面，反之放最后面。摸第三张时，和已有的两张牌相比，找到合适的位置插入。这种排序算法就被称之为插入排序(Insertion sort)。算法复杂度依然是O(n²)。

你可能会说，如果手里的牌是1、2、3、4、5，下一张牌摸到6，还需要从1开始比较吗？是不是很蠢。是的，可以肯定地告诉你，计算机就是这么蠢。但是我们可以简单优化一下，比如每次记住手中所有牌中间那张牌的大小，如果下一次摸到的牌大于中间值，就从后向前查找，反之则从前往后查找。这样可以减少一半的查找次数。当然，这种优化不会改变算法复杂度。

以上介绍了最简单的三种排序算法，思想层面理解不难，编程上也是几行代码就可以搞定，这里就不撸代码了。

三. 小结分析

不难看出，算法也有1+1=2的一面，也就是简单直观。也可以看到，算法在部署时，做一些简单的优化，虽然不能从算法复杂度层面提高效率，但是却可以很好的应付一些糟糕的情况。

当然，要想降低算法复杂度，即从本质上提升排序效率，则需要完全不一样的思维方式。后面我会再介绍几种高效的排序算法，你不防先简单思考一下，是否能想到更好的排序方法呢？简单提示一下，以上提到的算法，之所以慢，本质上是因为做了一堆没用的事（做了太多不必要的比较），你不防从少做事的角度去思考。