JavaScript排序算法——希尔排序

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

<html xmlns="http://www.w3.org/1999/xhtml">

<head>

<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />

<title>希尔排序</title>

<!--<link rel="stylesheet" type="text/css" href="../style/fdt.css" />-->

<script type="text/javascript" src="../js/jquery-1.6.2.min.js"></script>

<script type="text/javascript" src="../js/jquery.easydrag.handler.beta2.js"></script>

<script type="text/javascript">

	$(document).ready(

		function() { 

			var array_1 = [9,8,7,6,5,4,3,2,1];

			alert(array_1);

			/*shellSort*/

		    alert(shellSort(array_1));

		}

	); 

</script>

<style type="text/css">

	* { padding:0; margin:0; }

	body {

		padding: 100px;

		font-size: 15px;

	}

</style>

<script type="text/javascript">

	function shellSort(array){

		var stepArr = [1031612713, 217378076, 45806244, 9651787, 2034035, 428481, 90358, 19001, 4025, 1750, 836, 701, 301, 132, 57, 23, 10, 4, 1]; // reverse() 在维基上看到这个最优的步长 较小数组

		var i = 0;

		var stepArrLength = stepArr.length;

		var len = array.length;

		var len2 =  parseInt(len/2);

		for(;i < stepArrLength; i++){

			if(stepArr[i] > len2){

				continue;

			}

			stepSort(stepArr[i]);

		}

		// 排序一个步长

		function stepSort(step){

			//console.log(step) 使用的步长统计

			var i = 0, j = 0, f, tem, key;

			for(;i < step; i++){// 依次循环列

				for(j=1; step * j + i < len; j++){//依次循环每列的每行

					tem = f = step * j + i;

					key = array[f];

					while((tem-=step) >= 0){// 依次向上查找		<-

											//					<----

											//					<-------

						if(array[tem] > key){

							array[tem+step] = array[tem];

						}else{

							break;

						}

					}

					array[tem + step ] = key;

				}

			}

	}

	return array;

}

</script>

</head>

<body>

	<div>希尔排序</div>

</body>

</html>