`

merge sort

XHTMLHTML 
阅读更多
merge sort

合并排序

------
merge sort 原理

采用 divide-and-conqure，即 分而治之，

将问题分成最小的单元，然后从最小的解决，再不断合并，合并中继续解决，直到完成，

------
例子：

* js 代码 
	var arr_merge= [ 78, 13, 6, 177, 26, 90, 288, 45, 62 ];

	/**
	 * merge sort (合并排序)，时间: o(n*lg(n)),内存: n,
	 * 
	 * @param inputArr
	 * @return
	 */
	function mergeSort(inputArr) {
		/**
		 * 将1组数组 合并1次，数量大概减半
		 * 
		 * @param arrs
		 * @return
		 */
		function mergeArrOnce(arrs) {
			var len = Math.ceil(arrs.length / 2);
			var arrNew = new Array(len);
			for ( var i = 0; i < arrNew.length; i++) {
				if (i * 2 == arrs.length - 1) { // 最后1次 仅有1个数组
					arrNew[i] = mergeTwoArr(arrs[i * 2]);
				} else {
					arrNew[i] = mergeTwoArr(arrs[i * 2], arrs[i * 2 + 1]);
				}
			}
			return arrNew;
		}
		/**
		 * 按元素大小，合并2个数组
		 */
		function mergeTwoArr(arrOne, arrTwo) {
			if (typeof(arrOne)=='number' && typeof(arrTwo)=='number') { // 排序2个数字，生成1个数组
				if (arrOne < arrTwo) {
					return new Array(arrOne, arrTwo);
				} else {
					return new Array(arrTwo, arrOne);
				}
			} else if (typeof(arrOne)=='number' && arrTwo == undefined) { // 仅1个数字
				return [arrOne];
			} else if (arrTwo == undefined) { // 如果仅有1个数组，则直接返回
				return arrOne;
			} else {// 2个都是数组
				var len = arrOne.length + arrTwo.length;
				var arrNew = new Array(len);
				var indexOne = 0, indexTwo = 0;
				for ( var i = 0; i < len; i++) {
					if (arrOne[indexOne] < arrTwo[indexTwo]) {
						arrNew[i] = arrOne[indexOne++];
					} else {
						arrNew[i] = arrTwo[indexTwo++];
					}
					if (indexOne==arrOne.length) { // arrOne 结束了，（最近一次添加的是 arrOne）
						return arrNew.slice(0,i+1).concat(arrTwo.slice(indexTwo,arrTwo.length));
					} else if (indexTwo==arrTwo.length) { // arrTwo 结束了，（最近一次添加的是 arrTwo）
						return arrNew.slice(0,i+1).concat(arrOne.slice(indexOne,arrOne.length));
					} 
				}
				return arrNew;
			}
		}
		while(inputArr.length>1) {
			inputArr = mergeArrOnce(inputArr);
		}
		return inputArr;
	}


* html 代码 
	<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
	<html>
	<head>
	<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
	<script type="text/javascript" src="js/merge_sort.js"></script>
	</head>
	<body>
	<input type="button" value="merge sort" onclick="alert(mergeSort(arr_merge));" />
	</body>
	</html>


------
分享到：
| eclipse 的 fullscreen plugin
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

Magicbox
Global site tag (gtag.js) - Google Analytics