`

insertion sort

JavaScriptJ#XHTMLHTML 
阅读更多
insertion sort

------
insertion sort 原理

不断将数据插入已排序的序列，每次插入时，逐个比较，直到找到比自己大的则插入，

时间：o(n^2)
内存：o(1)

------
例子：

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

/**
 * insertion sort (插值排序)，时间: o(n^2),内存: 1,
 * 
 * @param inputArr
 * @return
 */
function insertionSort(inputArr) {
	// 1个临时变量
	var tmp;
	// 比较次数
	var compareCount = 0;
	// 移动次数
	var moveCount = 0;
	// 循环次数
	var cycleCount = 0;
	forOne: for ( var i = 0; i < inputArr.length; i++) {
		cycleCount++;
		forTwo: for ( var j = 0; j < inputArr.length; j++) {
			cycleCount++;
			compareCount++;
			if (inputArr[i] <= inputArr[j]) { // 替换值，将 j~i 之间的值后羿一位，
				tmp = inputArr[i];
				for ( var k = i; k >= j + 1; k--) {
					cycleCount++;
					inputArr[k] = inputArr[k - 1];
					moveCount++;
				}
				inputArr[j] = tmp;
				continue forOne;
			}
		}
	}
	alert("输入长度："+inputArr.length+",\n比较次数：" + compareCount + ",\n移动次数：" + moveCount + ",\n循环次数：" + cycleCount);
	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/sort_test.js"></script>
</head>
<body>
<input type="button" value="insertion sort" onclick="alert(insertionSort(arr_one));" />
</body>
</html>


------


------
分享到：
| js 的 null & undefined 判断
评论
发表评论

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

相关推荐

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