30天挑战数据结构和算法之第4、5天归并排序

本期的主题是归并排序。之所以将这个排序算法用两天时间去完成，也是为了能更好地消化它。我之前将它翻译成合并排序，但是看了很多参考文献对其命名后，将它改了过来。

先看一下visualgo.net上的伪代码。

split each element into partitions of size 1

recursively merge adjacent partitions

  for i = leftPartIdx to rightPartIdx

    if leftPartHeadValue <= rightPartHeadValue

      copy leftPartHeadValue

    else: copy rightPartHeadValue

copy elements back to original arrays

咋一看确实挺复杂的，其实就是用到了递归。递归其实并没有想象中的复杂，只是很多人并不理解而已。如果对数据结构的栈有一定了解的话，理解递归就不难了。递归就是不停地将变量压栈出栈的操作。

归并排序的核心思想就是分而治之。分治思想是一种思维方式，它强调将原问题分解成几个规模较小但类似于原问题的子问题，然后用递归的方式去求解子问题，最终合并这些子问题为原问题的解。递归是分治思想的一个具体实现。

分治思想在每层递归的时候都会有两个步骤：

• 分解：将原问题分解为若干子问题，递归求解各子问题
• 解决：合并子问题的解，得到原问题的解

来看javascript是如何实现归并排序算法的。

function MyMergeSort() {
	this.sort = function(originalArray) {
		if (originalArray.length <= 1) {
			return originalArray;
		}

		var middleIndex = Math.floor(originalArray.length / 2);
		var leftArray = originalArray.slice(0, middleIndex);
		var rightArray = originalArray.slice(middleIndex, originalArray.length);

		var leftSortedArray = this.sort(leftArray);
		var rightSortedArray = this.sort(rightArray);

		return this.mergeSortedArrays(leftSortedArray, rightSortedArray);
	}

	this.mergeSortedArrays = function(leftArray, rightArray) {
		var sortedArray = [];

		while (leftArray.length && rightArray.length) {
			var minimumElement = null;

			if (leftArray[0] <= rightArray[0]) {
				minimumElement = leftArray.shift();
			} else {
				minimumElement = rightArray.shift();
			}

			sortedArray.push(minimumElement);
		}

		if (leftArray.length) {
			sortedArray = sortedArray.concat(leftArray);
		}

		if (rightArray.length) {
			sortedArray = sortedArray.concat(rightArray);
		}

		return sortedArray;
	}
}

var sorter = new MyMergeSort();
var notSortedArr = [15, 8, 5, 12, 10, 1, 16, 9, 11, 7, 20, 3, 2, 6, 17, 18, 4, 13, 14, 19];
var sortedArr = sorter.sort(notSortedArr);
console.log(sortedArr);

然后是ruby的实现版本

def my_merge_sort(array)
	return array if array.size <= 1
	mid = array.size / 2
	left = array[0...mid]
	right = array[mid...array.size]
	merge(my_merge_sort(left), my_merge_sort(right))
end

def merge(left, right)
	sorted = []
	until left.empty? or right.empty?
		left.first <= right.first ? sorted << left.shift : sorted << right.shift
	end
	sorted + left + right
end

list = [15, 8, 5, 12, 10, 1, 16, 9, 11, 7, 20, 3, 2, 6, 17, 18, 4, 13, 14, 19]
newlist = my_merge_sort(list)
print newlist, "\n"

最后是java的版本

import java.util.Arrays;

public class MyMergeSort {
	public static int[] sort(int[] array) {
		if (array.length == 1) {
			return array;
		}
		int mid = array.length / 2;
		int[] left = sort(Arrays.copyOfRange(array, 0, mid));
		int[] right = sort(Arrays.copyOfRange(array, mid, array.length));

		return merge(left, right);
	}

	public static int[] merge(int[] leftArray, int[] rightArray) {
		int leftLen = leftArray.length, rightLen = rightArray.length;
		int[] sortedArray = new int[leftLen + rightLen];
		int index = 0;

		for (int i = 0, j = 0; i < leftLen || j < rightLen; ) {
			if (j == rightLen || (i < leftLen && leftArray[i] < rightArray[j])) {
				sortedArray[index++] = leftArray[i++];
			} else {
				sortedArray[index++] = rightArray[j++];
			}
		}

		return sortedArray;
	}

	public static void main(String[] args) {
		int[] arr = {15, 8, 5, 12, 10, 1, 16, 9, 11, 7, 20, 3, 2, 6, 17, 18, 4, 13, 14, 19};
		int[] newarr = sort(arr);
		System.out.println(Arrays.toString(newarr));
	}
}

总的来说，该算法还是比起之前几个算法上手起来有点难度。

下面来算算归并算法的时间复杂度。

我们首先将归并算法按照分治思想的两个步骤，分别求解各自的时间复杂度。

分解，将原问题分解成2个子问题，每个子问题的规模是原问题的1/2。对于一个规模为n/2的子问题，需要T(n/2)的时间。所以，总共需要2T(n/2)的时间来求解2个子问题。
解决，合并算法的时间复杂度为O(n)。

所以，最后可以得出时间复杂度的计算公式为T(n) = 2T(n/2) + O(n)，对于这个表达式的求解最终的结果为T(n) = O(nlgn)。为什么是这个结果，可以看看这张图。

归并算法的最优、最差以及平均时间复杂度都为O(nlgn)。

空间复杂度则为O(n)。因为在合并的时候，开辟了n个数组。

总结，归并排序是比之前任何一个排序，在大量输入的情况下，效率都要高的一种算法。时间复杂度中的lgn，也就是以2为底的对数函数，产生的原因就是基于递归，它是分治思想的具体实现。