分治法-函数式编程入门使用Elixir

分治法是将问题分成两个或多个部分，这些部分可以独立处理，最后可以组合起来。这种技巧不仅用在递归算法里，也能用来解决其他问题。例如，假设要建一个新闻主页，其中包含最新文章、头条新闻、体育新闻、文化新闻。如果想一次从数据库中获取所有内容，则SELECT查询将难以编写和维护。更好的方式是将查询按内容分为几个较小的独立操作。最后，将所有查询结果聚合起来生成新闻主页。递归函数也可以采用类似的方法。让我们用这种方法解决列表的排序问题。

我们希望构建一个接收列表的函数，它返回按升序排列的列表。在函数式编程中，数据是不可变的，我们无法更改原来列表的顺序，所以需要建立一个新列表。在生成新列表的过程中，我们必须保证所有元素是按升序排列的。想用一个函数一次完成所有操作是很难的；相反，我们可以将原来的列表分成两半。这样我们就得到了两个要排序的列表，但它们都比原来的列表小。继续切分下去，最终我们会得到仅包含一个元素的列表。一个元素列表本身就是按升序排列的！然后我们用排序的方式逐步把这些列表合并起来。

让我们开始编写排序函数。首先，我们需要将列表分成两半。Elixir的Enum.split/2函数可以用来拆分列表，也能将列表一分为二。请在IEx中尝试：

Enum.split/2返回一个包含两个列表的元组，其中第一个列表的元素数量由我们给定的参数决定。原列表项的其余部分放在第二个列表中。如果要将原列表分成两半，我们需要知道它一共有多少元素。我们可以用Elixir函数Enum.count/1计算列表的元素总数，然后将其除以二。在IEx中试试：

当列表中的元素数量为奇数时，计算结果出现了浮点数，但是切分函数不接受浮点数，否则会产生错误。我们还需要一个整数除法。我们可以使用Elixir Kernel.div/2函数。试试：

现在我们可以将所有这些函数组合在一起，以递归方式将列表分成两半。这是排序算法的第一步；第二步是以升序的方式建立新的列表。创建sort.ex文件，输入以下代码：

我们创建了一个ascending函数，现在它只切分列表，但很快就会对元素进行排序。前两个子句（空列表和只包含一个元素的列表）是我们的边界条件。更长的列表将被后面函数子句一分为二。我们还使用了Elixir的内置函数，例如Enum.split/2和Enum.count/1。

我们将列表切分，直到只剩一个元素。现在要用这些单项列表来构建新的升序列表。我们需要一个合并函数，它将最小的元素放在列表的开头。这样，如果我们尝试合并[9]和[5]，结果将是[5，9]。由于参数是有序列表，我们知道第一个元素就是最小的。然后我们可以提取两个列表中的第一个项，比较它们的大小，将较小的值放在新列表里。如果我们尝试合并[5，9]与[1，2]，结果将是[1，2，5，9]。递归执行下去，就能生成一个新的升序列表。让我们看看合并[5，9]和[1，4，5]时函数是如何工作的：(www.xing528.com)

我们来编写合并函数：

前两个子句很简单。如果我们尝试将某个列表与空列表合并，则结果还是这个列表。子句head_a <= head_b表示list_a的第一个元素更小。于是我们提取 list_a的第一个元素，并使用表达式[head_a | merge（tail_a，list_b）]将它放在新列表的第一个位置。对于新列表的其余元素，我们以递归方式调用merge，参数是列表a的其余元素和整个list_b。子句head_a > head_b执行相反的操作，将list_b的第一个元素提取并放入新列表的第一个位置。

使用merge/2函数，我们现在可以合并我们切分的所有列表并构建一个新列表。让我们在ascending函数中添加对merge/2函数的调用：

将列表传递给merge/2函数之前，必须确保列表是有序的。这就是我们在合并之前对ascending函数进行递归调用的原因。它将以递归方式合并切分列表，如下所示：

在这个排序函数中，ascending的递归调用可以独立工作；所有的递归调用不会相互干扰。例如，我们可以进行并行计算，但最后我们需要将两个结果用merge函数连接起来。可以在IEx中尝试我们的Sort模块：

成功了！排序算法运行无误。这个算法叫归并排序。^[2]它是最著名的分治算法之一。

你可能已经注意到，分治法与减治法非常相似。主要的区别在于，减治法的重点是不断化简问题直到找到基本情形，而分治法是将问题分成两个或多个部分，这些部分可以独立处理，最后组合在一起。正如你看到的，递归会执行大量函数调用，这可能会导致性能下降。下一节将学习创建节省机器资源的递归函数。