Algorithm之排序之归并排序

Algorithm之排序之归并排序

一、归并介绍

动画1：


动画2：



归并排序（英语：Merge sort，或 mergesort），
是创建在归并操作上的一种有效的排序算法，效率为O(n log n)。

1945年由约翰·冯·诺伊曼首次提出。

该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，
且各层分治递归可以同时进行。


时间复杂度      O(n log n)
时间复杂度最优  O(n)
时间复杂度平均  O(n log n)
空间复杂度      O(n)


执行过程：
通过动画可以看出，归并排序的执行过程是：先分再排。
——先将最大集合分成小集合，递归直至最小的单个集合。
——再对小集合进行排序组成二级小集合。
——以此类推而形成最大的集合。


二、具体实现

1、Javascript:

Array.prototype.merge_sort = function() {
	if (this.length == 1) return this;
	var mid = this.length >> 1;
    var merge = function(left, right) {
		var _final = [];
		while (left.length && right.length)
			_final.push(left[0] <= right[0] ? left.shift() : right.shift());
		return _final.concat(left.concat(right));
	};
	return merge(this.slice(0, mid).merge_sort(), this.slice(mid).merge_sort());    
};

// Array.prototype.shift()
//     The shift() method removes the first element 
//     from an array and returns that element. 

测试：

var arr = [1,23,14,8,10,9,235,21];


// merge_sort() 方法返回一个新数组
arr.merge_sort();
// [1, 8, 9, 10, 14, 21, 23, 235]


// 并未改变原来的数组。
arr
// [1, 23, 14, 8, 10, 9, 235, 21]

2、Java 版本：

static void merge_sort_recursive(int[] arr, int[] result, int start, int end) {
	if (start >= end)
		return;
	int len = end - start, mid = (len >> 1) + start;
	int start1 = start, end1 = mid;
	int start2 = mid + 1, end2 = end;
	merge_sort_recursive(arr, result, start1, end1);
	merge_sort_recursive(arr, result, start2, end2);
	int k = start;
	while (start1 <= end1 && start2 <= end2)
		result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
	while (start1 <= end1)
		result[k++] = arr[start1++];
	while (start2 <= end2)
		result[k++] = arr[start2++];
	for (k = start; k <= end; k++)
		arr[k] = result[k];
}

public static void merge_sort(int[] arr) {
	int len = arr.length;
	int[] result = new int[len];
	merge_sort_recursive(arr, result, 0, len - 1);
}

引自：
https://zh.wikipedia.org/wiki/归并排序


-