下载掌阅APP，畅读海量书库
立即打开
“一颗给你。一颗给我。一颗给你。一颗给我。”你正在校园里。此时阳光明媚，你和你最好的朋友分一袋糖。“一颗给你。一颗给我。”你当时没有意识到，以这种方式分糖，就是在实施一种算法。
算法是一系列可以用来解决信息问题的步骤。
在这阳光明媚的一天，你用一种算法公平地分享你的糖。这个算法输入的是袋中糖的数量，输出的是你和你朋友各自得到的糖的数量。如果袋子里的糖的总数恰好是偶数，那么你们俩得到的糖数量相同。如果总数是奇数，那么你的朋友最后会比你多得到一颗。
算法就像菜谱。它是一系列简单步骤的列表，如果遵循这些步骤，就可以将一组输入转换为所需要的输出。不同之处在于，算法处理的是信息，而食谱应对的是食物。通常，一个算法是在代表信息的物理量中运行的。
对于解决给定的问题，常常有多个算法可以选择。你还可以数出糖的总数，用心算把总数除以2，然后分出正确的糖的数量来分享糖。结果是一样的，但是用到的算法，即获得输出的方法是不同的。
一个算法可以写成一个指令列表。大多数情况下，这些指令是按顺序依次执行的。偶尔的情况下，下一条要执行的指令并不是下一个顺序步骤，而是列表中其他地方的一条指令。例如，某个指令可能要求算法执行人返回到前面的步骤，并从那里继续往下执行。像这样向后跳转，从而允许重复执行一组步骤，这是许多算法中的一个强大特性。“一颗给你。一颗给我。”这一组步骤在分享糖的算法中反复出现。重复步骤的操作被称为 迭代 （iteration）。
如果袋子中的糖数量是偶数，则下面的迭代算法就够用了：
重复以下步骤：
给你的朋友一颗糖。
给你自己一颗糖。
当袋子变空时，停止重复。
在算法的呈现中，比如上面这个算法，为了清晰起见，步骤通常写成一行一行的样式。通常用缩进来将相互关联的步骤进行分组。
如果袋子中糖的数量可能是偶数也可能是奇数，算法就会变得稍微复杂一些。里面必须包含一个决策步骤。大多数算法都包含决策步骤，决策步骤要求算法执行者在两种可能的行动方案中做出选择。要执行哪个行动方案取决于一个 条件 （condition）。一个条件就是一个命题，这个命题要么为真，要么为假。最常见的决策构造——“如果-那么-否则”（if-then-else）——结合了一个条件和两个可能的行动方案。“如果”条件为真，“那么”就执行紧随其后的一个或多个步骤。“如果”条件为假，就执行“否则”之后的一个或多个步骤。
考虑到糖数量为奇数的可能性，必须在算法中加入以下决策步骤：
如果这是第一颗糖，或者你刚刚已经分到一颗糖，
那么就把这颗糖给你的朋友，
否则就把这颗糖给你自己。
这里的条件是 复合条件 （compound condition），意思是它由两个（或多个）简单条件组成。简单条件分别是“这是第一颗糖”和“你刚刚已经分到一颗糖”。这两个简单条件由一个“或”运算联结在一起。如果其中任何一个简单条件为真，则复合条件为真。在复合条件为真的情况下，就完成“把这颗糖给你的朋友”这一步。否则，就执行“把这颗糖给你自己”这一步。完整的算法如下：
以一袋糖作为输入。
重复以下步骤：
从袋子里拿出一颗糖。
如果这是第一颗糖，或者你刚刚已经分到一颗糖，
那么就把这颗糖给你的朋友，
否则就把这颗糖给你自己。
当袋子变空时，停止重复。
把空袋子丢进垃圾桶。
现在糖就被公平地分掉了。
这是一个整洁并能以高效方式实现目标的算法，所有好的算法都是这样。
信息问题每天都会浮现。想象一下一个实习图书管理员第一天上班的情景。1 000本崭新的书刚刚送到，就躺在地上的盒子里。老板希望这些书能尽快按照作者姓名的字母顺序被摆放在书架上。这是一个信息问题，有算法可以解决它。
大多数人会凭直觉使用一种叫作插入排序（Insertion Sort）的算法（图I.1）。插入排序的运行方式如下：
图I.1 插入排序的执行
以一摞未排序的书作为输入。
重复以下步骤：
拿起一本书。
读一下作者的名字。
在书架上扫视一圈，直到找到该把书插进去的地方。
把插入点后面的所有书都挪后一格。
插入新书。
当地板上没有书时，停止重复。
这些书现在就排序完成了。
在这期间任何时刻，地板上的书都是未排序好的。书一本接一本地被转移到书架上。每本书都是按字母顺序放进书架的。因此，书架上的书总是井然有序。
插入排序很容易理解和操作，但速度很慢。之所以速度慢，是因为每从地板上拿一本书，图书管理员都要扫视或挪动已经在书架上的书。刚开始的时候，书架上的书很少，所以扫视和挪动的速度很快。最终，这位图书管理员负责的书架上会有近1 000本书。平均而言，将一本书放进正确的位置需要500次 操作 （operation），操作内容是比对作者的名字或者挪书。因此，对所有的书进行排序平均需要50万（1 000×500）次操作。假设单次操作需要1秒钟。在这种情况下，使用插入排序将需要花费大约17个工作日。老板会不高兴的。
1962年，计算机科学家托尼·霍尔（Tony Hoare）发明了一种更快的算法——快速排序（Quicksort）。1938年，霍尔出生于斯里兰卡，父母是英国人。他在英国接受教育，就读于牛津大学，后来以讲师身份进入学术界。他的排序方法属于分治（divide-and-conquer）算法。快速排序比插入排序要复杂得多，但是顾名思义，它也要快得多。
快速排序（图I.2）先将这堆书分拆成两摞书。分拆是由一个 分区点字母 （pivot letter）决定的。若书的作者姓名字母顺序在分区点字母之前，则把书放在当前这一摞左边新的一摞里。若书的作者姓名字母顺序在分区点字母之后，则放进右边的一摞。然后，得到的两摞书进一步使用新的分区点字母进行分拆。这样一来，这些书摞就按字母顺序排列好了。最左边的一摞书是作者姓名字母在字母表中排第一位的书。其后一摞是排在第二位的书，以此类推。对于最大的一摞，重复这个分拆过程，直到这最大的一摞只包含5本书。然后使用插入排序对这些摞分别排序。最后，把排序好的这些摞书按顺序依次转移到书架上。
图I.2 快速排序的执行
为了达到最快速度，所选的分区点字母应该能把一摞书对半分拆。
假设最开始的一摞包含作者姓名字母从A到Z的书。第一个分区点的最佳选择可能是M。这样便可以分拆出两摞书：A—L摞和M—Z摞（图I.2）。如果A—L摞比较大，接下来再次分拆。A—L的一个不错的分区点可能是F。在这次分拆之后，将会得到三摞书：A—E摞、F—L摞和M—Z摞。接下来分拆M—Z摞，以此类推。如果有20本书，最后分拆的结果可能是：A—C摞、D—E摞、F—L摞、M—R摞和S—Z摞。这些摞再各自用插入排序分别排序，然后一摞接一摞地转移到书架上。
可以这样写出完整的快速排序算法：
以一摞未排序的书作为输入。
重复以下步骤：
选择最厚的一摞书。
为两边的书摞留出空间。
选择一个分区点字母。
重复以下步骤：
从选定的那一摞书中取出一本书。
如果书的作者姓名字母顺序在分区点字母之前，
那么把书放在左边的一摞里，
否则就把书放进右边的一摞里。
当选定的那一摞变空时，停止重复。
当最厚的一摞只有5本书或更少时停止重复。
使用插入排序将每一摞书分别排序。
把这些书摞依次放到书架上。
这些书现在就排序完成了。
快速排序使用了两个重复的步骤序列，或称 循环 （loop），其中一个循环放进了另一个循环之中。外层重复步骤组处理所有的书摞，内层组则处理单个书摞。
对于处理大量的图书，快速排序要比插入排序快得多。这里面的秘诀在于，分拆单个书摞的速度很快。每本书只需要与分区点字母进行比较。对其他书不需要做任何操作——既不需要比较作者的名字，也不需要挪动书。在快速排序之后进行插入排序是高效的，因为每个书摞已经变得很小。对1 000本书进行排序，采用快速排序只需要大约10 000次操作就可以达成。操作的确切次数取决于分区点将书摞对半分的精确程度。按每次操作用时1秒钟计算，完成这项工作只需要不到3个小时——相比于17个工作日，这是一个很大的改进。老板会很高兴的。
显然，算法的速度很重要。算法是根据其 计算复杂度 （computational complexity）来评级的。计算复杂度将执行算法所需的步骤数与输入数量联系起来。快速排序的计算复杂度显著低于插入排序。
快速排序被称为分治算法，因为它将原来的大问题分解成小问题，先分别解决这些小问题，然后将部分解组合成完整解。我们将在此后的章节中看到，分治法是算法设计中一个强有力的策略。
人们发明了许多算法用于排序，包括合并排序（Merge Sort）、堆排序（Heapsort）、内向排序（Introsort）、蒂姆排序（Timsort）、立方体排序（Cubesort）、希尔排序（Shell Sort）、冒泡排序（Bubble Sort）、二叉树排序（Binary Tree Sort）、循环排序（Cycle Sort）、图书馆排序（Library Sort）、耐心排序（Patience Sorting）、顺滑排序（Smooth-sort）、链排序（Strand Sort）、锦标赛排序（Tournament Sort）、鸡尾酒排序（Cocktail Sort）、梳子排序（Comb Sort）、地精排序（Gnome Sort）、解混洗排序（UnShuffl e Sort）、分块排序（Block Sort）和奇偶排序（Odd-Even Sort）。所有这些算法都能对数据进行排序，但每个算法都有其独特之处。有些算法比其他算法更快，有些算法比其他算法需要更多的存储空间，少数几个算法要求输入是以特定方式备好的。某些算法则已经被更新、更高效的算法取代了。
如今，算法与计算机已密不可分。根据定义，计算机是执行算法的机器。
如前所述，算法是用来解决问题的一种抽象方法。算法可以由人或计算机执行。在计算机执行算法之前，算法必须被编码为计算机可以执行的指令列表。计算机指令列表被称为 程序 （program）。计算机的最大优势是它能一个接一个地自动高速执行大量指令。令人惊讶的是，计算机不需要支持种类繁多的指令。一些基本的指令类型就足够用了。它所需要的只是对数据存储与提取、算术、逻辑、重复和决策的指令。算法可以被分解成诸如此类的简单指令并由计算机执行。
要执行的指令列表和要进行运算的数据被称为计算机 软件 （software）。在现代计算机中，软件被编码为微观导线上的电子电压电平。计算机 硬件 （hardware），也就是物理机器本身，每次执行程序的一条指令。程序执行引发输入数据被处理，并导致输出数据的创建。
计算机的巨大成功有两个原因。首先，计算机执行算法的速度比人快很多。一台计算机每秒可以执行数十亿次操作，而人或许只能执行10次。其次，计算机硬件是 通用 （general-purpose）的，这意味着它可以执行任何算法。只要换个软件，计算机就能执行完全不同的任务。这给了计算机很大的灵活性。计算机可以执行各种各样的任务——从文字处理到电子游戏。这种灵活性的关键在于，由程序支配通用硬件的工作。没有软件，硬件就是空闲的。是程序使硬件动起来。
算法是对计算机必须做什么的抽象描述。因此，在解决问题时，算法至关重要。算法是必须做的事情的蓝图。程序是对算法的精确的、机器可执行的公式化呈现。要解决一个信息问题，首先必须找到合适的算法。只有这样才能把程序写进计算机。
20世纪中叶，计算机的发明使算法的数量、种类和复杂性都呈爆发式增长。曾经被认为不可能解决的那些问题，现在经常交给廉价的计算机来解决。每天都有新的程序在发布，这扩大了计算机可以承担的任务范围。
算法嵌入我们的台式计算机里、汽车里、电视机里、洗衣机里、智能手机里、手腕设备里，并且很快就会嵌入我们的身体里。我们在与朋友交流、加快工作进度、玩游戏和寻找灵魂伴侣这些事上，使用了大量的算法。毫无疑问，算法让我们的生活变得更容易了。它们还为人类提供了前所未有的获取信息的途径。从天文学到粒子物理学，算法增进了我们对宇宙的理解。最近，一些尖端算法显示出了超越人类的智能。
所有这些算法都是人类思维别出心裁且优雅的创造物。这本书讲述的是算法如何从古代学者晦涩的著作中脱颖而出，成为现代计算机世界的驱动力之一。