算法与数据结构(十五) 归并排序(Swift 3.0版)

上篇博客我们主要聊了堆排序的相关内容，本篇博客，我们就来聊一下归并排序的相关内容。归并排序主要用了分治法的思想，在归并排序中，将我们需要排序的数组进行拆分，将其拆分的足够小。当拆分的数组中只有一个元素时，则这个拆分的数组是有序的。然后我们将这些有序的数组进行两两合并，在合并过程中进行比较，合并生成的新的数组仍然是有序的。然后再次将合并的有序数组进行合并，重复这个过程，知道整个数组是有序的。

下方我们先给出两个有序数组合并的示意图以及代码，然后给出归并排序的相关内容。归并排序其实就是拆分+合并。废话少说，开始今天的内容。

一、合并两个有序数组

在本篇博客的第一部分我们先给出合并两个有序数组的示意图以及相关代码，在归并排序时，我们会使用到此部分的内容。下方会给出两个有数数组的合并，并且会给出相应的代码实现。

1.有序数组合并的示意图

因为两个有序数组在合并后的新的数组仍然是有序的，所以我们需要对有序数组中的元素进行比较。每次从两个数组中取出最小的那个元素，然后将两个元素进行比较，将最小的那个元素放入到新的数组中。下方就是有序数组合并的示意图。

• 首先从两个有序数组中取出最小的值，如下所示。我们将9和10取出后进行比较，将较小的9存入我们新的数组中。
• 重复上个步骤，如果有一个数组中的元素被取完，将另一个数组中剩余的元素直接追加到我们的新的数组中即可。

2.代码实现

根据上述示意图给出相关的代码实现并不困难，下方就是上述过程的代码实现。下方这个mergeArray()函数，就是将两个有序数组合并成一个新的有序数组的具体代码实现。mergeArray()的两个参数就是即将合并的两个有序数组，而返回值就是合并后新的有序的数组。代码比较简单，在此就不做过多赘述了。

二、归并排序

上述实现完两个有序数组合并成新的有序数组完毕后，接下来就该归并排序出场了。在归并排序过程中，会使用到上述的内容。因为我们将无序数列进行分割后，就会不断调用上述的合并代码，将小的有序的数组合并成较大的有序数组，再次合并，直到我们原始的数组是有序的为止。下方会给出相应的示意图以及归并排序的Swift代码实现。

1.归并排序示意图

下方就是我们归并排序的示意图，稍后的代码实现也是根据下方的示意图来写的。所以对下方示意图的充分理解还是很有必要的。在下方示意图中，从上往下就是我们归并排序的整个过程。我们需要排序的序列为[62, 88, 58, 47, 62, 35, 73, 51, 99, 37, 93]。下方是对每一步的解析：

• 首先我们将需要排序的序列进行拆分，拆分成足够小的数组。也就是拆分的数组中只有一个元素。无序数组拆分的所有数组因为其中只含有一个元素，所以都是有序的。我们就可以对这些有序的小数组进行合并了。
• 将拆分的多个有序数组调用第一部分实现的mergeArray()函数进行两两合并，合并后的新数组仍然是有序的。我们再次对这些合并产生的数组进行两两合并，直到所有被拆分的数组有重新被合并成一个大数组位置。这个重新合并生成的数组就是有序的，也就是归并排序所产生的有序序列。

下方就是拆分+多次合并的详细过程，最终我们得到的就是一个有序序列。如下所示：

2、上述过程的代码实现

根据上述的示意图，我们给出相应的代码实现应该是比较容易的。就是将我们的无序数组进行拆分，然后进行多次合并，最后合并成一个大的有序数组。下方代码就是对上述过程的描述。

• 在下方代码中的第一个框中就是将我们的无序数组进行拆分。被拆分的小的有序的数组存入到tempArray中，便于我们下方遍历进行合并。
• 第二个框就是对tempArray中被拆分的数组进行遍历，在遍历的过程中进行两两合并，将合并的数组再次存入到tempArray中，直到tempArray中只含有一个数组为止。

而tempArray最终的数组就是归并排序的最终结果。下方是整个过程，代码并不复杂。

上述代码的实现在有些数据结构的教程上是使用递归实现的，即使是不使用递归实现也比上述代码要麻烦。

三、测试用例

对上述代码的测试我们仍然会使用到我们之前的测试用例，因为上述排序类仍然遵循我们之前定义的SortType协议。下方就是本篇博客的测试用例，也是所有排序方式的测试用例。这个MergeSort类就是我们归并排序的类。

上述用例的输出结果如下，从输出结果中，我们就能明显的看出拆分和合并的整个过程。如下所示：

本篇博客对堆排序的介绍就先到这儿，下篇博客我们将会介绍“快速排序”的详细内容。本篇博客的相关代码依然会在github上进行分享，下方是github分享地址，如下所示：

github代码分享地址：https://github.com/lizelu/DataStruct-Swift/tree/master/AllKindsOfSort