`

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/归并排序


-
  • 大小: 92.1 KB
  • 大小: 13.1 KB
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics