动画｜经典的归并排序究竟怎么玩儿？

作者 | 菠了个菜

责编 | 郭芮

由于LeetCode上的算法题很多涉及到一些基础的数据结构，为了更好的理解后续更新的一些复杂题目的动画，推出一个新系列——《图解数据结构》，主要使用动画来描述常见的数据结构和算法，本文分析归并排序。

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

作为一种典型的分而治之思想的算法应用，归并排序的实现有两种方法：

• 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
• 自下而上的迭代；

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度，代价是需要额外的内存空间。

算法步骤

• 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
• 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
• 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
• 重复步骤 3 直到某一指针达到序列尾；
• 将另一序列剩下的所有元素直接复制到合并序列尾。

来源：https://github.com/hustcc/JS-Sorting-Algorithm。

算法演示

排序动画过程解释：

• 首先，将数字分割成两片区域；
• 再将数字分割成两片区域；
• 依次划分
• 直到每片区域只有一个元素
• 分割完成
• 接下来，将分割的每片区域进行合并组合
• 合并时，按照数字的升序移动，使得合并后的数字在组内按升序排列
• 当合并包含多个数字的组时，比较开头的数字，移动其中较小的数字
• 比如在动画中，比较开头的 4 和 3
• 其中 4 大于 3， 因此移动 3
• 按照同样的逻辑去比较该列剩余的头数
• 4 小于 7 ，所以移动 4
• 同样的逻辑去进行接下来的操作
• 递归的重复组的合并操作，直到所有数字都在一个组中。
• 完成归并排序。

代码实现

为了更好的让读者用自己熟悉的编程语言来理解动画，笔者将贴出多种编程语言的参考代码，代码全部来源于网上。

Java代码实现：

public class MergeSort implements IArraySort {
 @Override
 public int[] sort(int[] sourceArray) throws Exception {
 // 对 arr 进行拷贝，不改变参数内容
 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
 if (arr.length < 2) {
 return arr;
 }
 int middle = (int) Math.floor(arr.length / 2);
 int[] left = Arrays.copyOfRange(arr, 0, middle);
 int[] right = Arrays.copyOfRange(arr, middle, arr.length);
 return merge(sort(left), sort(right));
 }
 protected int[] merge(int[] left, int[] right) {
 int[] result = new int[left.length + right.length];
 int i = 0;
 while (left.length > 0 && right.length > 0) {
 if (left[0] <= right[0]) {
 result[i++] = left[0];
 left = Arrays.copyOfRange(left, 1, left.length);
 } else {
 result[i++] = right[0];
 right = Arrays.copyOfRange(right, 1, right.length);
 }
 }
 while (left.length > 0) {
 result[i++] = left[0];
 left = Arrays.copyOfRange(left, 1, left.length);
 }
 while (right.length > 0) {
 result[i++] = right[0];
 right = Arrays.copyOfRange(right, 1, right.length);
 }
 return result;
 }
}

Python代码实现：

def mergeSort(arr):
 import math
 if(len(arr)<2):
 return arr
 middle = math.floor(len(arr)/2)
 left, right = arr[0:middle], arr[middle:]
 return merge(mergeSort(left), mergeSort(right))
def merge(left,right):
 result = []
 while left and right:
 if left[0] <= right[0]:
 result.append(left.pop(0));
 else:
 result.append(right.pop(0));
 while left:
 result.append(left.pop(0));
 while right:
 result.append(right.pop(0));
 return result

JavaScript代码实现：

function mergeSort(arr) { // 采用自上而下的递归方法
 var len = arr.length;
 if(len < 2) {
 return arr;
 }
 var middle = Math.floor(len / 2),
 left = arr.slice(0, middle),
 right = arr.slice(middle);
 return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right)
{
 var result = [];
 while (left.length && right.length) {
 if (left[0] <= right[0]) {
 result.push(left.shift());
 } else {
 result.push(right.shift());
 }
 }
 while (left.length)
 result.push(left.shift());
 while (right.length)
 result.push(right.shift());
 return result;
}

GO代码实现：

func mergeSort(arr []int) []int {
 length := len(arr)
 if length < 2 {
 return arr
 }
 middle := length / 2
 left := arr[0:middle]
 right := arr[middle:]
 return merge(mergeSort(left), mergeSort(right))
}
func merge(left []int, right []int) []int {
 var result []int
 for len(left) != 0 && len(right) != 0 {
 if left[0] <= right[0] {
 result = append(result, left[0])
 left = left[1:]
 } else {
 result = append(result, right[0])
 right = right[1:]
 }
 }
 for len(left) != 0 {
 result = append(result, left[0])
 left = left[1:]
 }
 for len(right) != 0 {
 result = append(result, right[0])
 right = right[1:]
 }
 return result
}

如果你是iOS开发者，可以在GitHub上 https://github.com/MisterBooo/Play-With-Sort-OC 获取更直观可调试运行的源码。

作者简介：菠了个菜，本文首发于个人公众号「五分钟学算法」。「五分钟学算法」是致力于通过各种动画的形式来描绘出各种数据结构，并图解LeetCode原题的学习平台，一起学习，一起进步！

声明：本文为作者投稿，版权归其个人所有。