首页 > 代码库 > [转] js_常见算法
[转] js_常见算法
js模拟螺旋矩形算法
1 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 2 <html xmlns="http://www.w3.org/1999/xhtml"> 3 <head> 4 <meta http-equiv="content-type" content="text/html;charset=utf-8" /> 5 <meta name="generator" content="editplus" /> 6 <meta name="author" content="" /> 7 <meta name="keywords" content="" /> 8 <meta name="description" content="" /> 9 <title> new document </title>10 11 </head>12 13 <body>14 <div id="container"></div>15 <script type="text/javascript">16 var cal = function(len){17 var helix = [[],[],[],[],[],[]];18 var min = 0;19 var max = len - 1;20 var row = 0;21 var col = 0;22 for(var i=0; i < len * len; i++) {23 helix[row][col]=i+1;24 if(row == min && col < max) {25 col = col + 1;26 }27 else if(row < max && col == max) {28 row = row + 1;29 }30 else if(row == max && col > min) {31 col = col - 1;32 }33 else if(row > min && col == min) {34 row = row - 1;35 }36 if(row - 1 == min && col == min){37 min = min + 1;38 max = max - 1;39 }40 }41 return helix;42 };43 44 var helix = cal(6);45 var html = ‘‘;46 for(var i=0; i < helix.length; i++) {47 for(var j=0; j < helix[i].length; j++) {48 if(helix[i][j]<10){49 helix[i][j]="0"+helix[i][j];50 }51 html += helix[i][j] + ‘ ‘;52 }53 html += ‘<br />‘;54 }55 var container=document.getElementById("container");56 container.innerHTML =html;57 </script>58 </body>59 </html>
js最短路径
1 <html><head><title>use A* to find path...</title></head> 2 <body style="margin:0px"> 3 <script> 4 /* 5 written by hjjboy 6 email:tianmashuangyi@163.com 7 qq:156809986 8 */ 9 var closelist=new Array(),openlist=new Array(); 10 var gw=10,gh=10,gwh=14; 11 var p_start=new Array(2),p_end=new Array(2); 12 var s_path,n_path=""; 13 var num,bg,flag=0; 14 var w=30,h=20; 15 function GetRound(pos){ 16 var a=new Array(); 17 a[0]=(pos[0]+1)+","+(pos[1]-1); 18 a[1]=(pos[0]+1)+","+pos[1]; 19 a[2]=(pos[0]+1)+","+(pos[1]+1); 20 a[3]=pos[0]+","+(pos[1]+1); 21 a[4]=(pos[0]-1)+","+(pos[1]+1); 22 a[5]=(pos[0]-1)+","+pos[1]; 23 a[6]=(pos[0]-1)+","+(pos[1]-1); 24 a[7]=pos[0]+","+(pos[1]-1); 25 return a; 26 } 27 function GetF(arr){ 28 var t,G,H,F; 29 for(var i=0;i<arr.length;i++){ 30 t=arr[i].split(","); 31 t[0]=parseInt(t[0]);t[1]=parseInt(t[1]); 32 if(IsOutScreen([t[0],t[1]])||IsPass(arr[i])||InClose([t[0],t[1]])||IsStart([t[0],t[1]])||!IsInTurn([t[0],t[1]])) 33 continue; 34 if((t[0]-s_path[3][0])*(t[1]-s_path[3][1])!=0) 35 G=s_path[1]+gwh; 36 else 37 G=s_path[1]+gw; 38 if(InOpen([t[0],t[1]])){ 39 if(G<openlist[num][1]){ 40 openlist[num][0]=(G+openlist[num][2]); 41 openlist[num][1]=G; 42 openlist[num][4]=s_path[3]; 43 } 44 else{G=openlist[num][1];} 45 } 46 else{ 47 H=(Math.abs(p_end[0]-t[0])+Math.abs(p_end[1]-t[1]))*gw; 48 F=G+H; 49 arr[i]=new Array(); 50 arr[i][0]=F;arr[i][1]=G;arr[i][2]=H;arr[i][3]=[t[0],t[1]];arr[i][4]=s_path[3]; 51 openlist[openlist.length]=arr[i]; 52 } 53 if(maptt.rows[t[1]].cells[t[0]].style.backgroundColor!="#cccccc"&&maptt.rows[t[1]].cells[t[0]].style.backgroundColor!="#0000ff"&&maptt.rows[t[1]].cells[t[0]].style.backgroundColor!="#ff0000"&&maptt.rows[t[1]].cells[t[0]].style.backgroundColor!="#00ff00") 54 { 55 maptt.rows[t[1]].cells[t[0]].style.backgroundColor="#FF00FF"; 56 //maptt.rows[t[1]].cells[t[0]].innerHTML="<font color=white>"+G+"</font>"; 57 } 58 } 59 } 60 function IsStart(arr){ 61 if(arr[0]==p_start[0]&&arr[1]==p_start[1]) 62 return true; 63 return false; 64 } 65 function IsInTurn(arr){ 66 if(arr[0]>s_path[3][0]){ 67 if(arr[1]>s_path[3][1]){ 68 if(IsPass((arr[0]-1)+","+arr[1])||IsPass(arr[0]+","+(arr[1]-1))) 69 return false; 70 } 71 else if(arr[1]<s_path[3][1]){ 72 if(IsPass((arr[0]-1)+","+arr[1])||IsPass(arr[0]+","+(arr[1]+1))) 73 return false; 74 } 75 } 76 else if(arr[0]<s_path[3][0]){ 77 if(arr[1]>s_path[3][1]){ 78 if(IsPass((arr[0]+1)+","+arr[1])||IsPass(arr[0]+","+(arr[1]-1))) 79 return false; 80 } 81 else if(arr[1]<s_path[3][1]){ 82 if(IsPass((arr[0]+1)+","+arr[1])||IsPass(arr[0]+","+(arr[1]+1))) 83 return false; 84 } 85 } 86 return true; 87 } 88 function IsOutScreen(arr){ 89 if(arr[0]<0||arr[1]<0||arr[0]>(w-1)||arr[1]>(h-1)) 90 return true; 91 return false; 92 } 93 function InOpen(arr){ 94 var bool=false; 95 for(var i=0;i<openlist.length;i++){ 96 if(arr[0]==openlist[i][3][0]&&arr[1]==openlist[i][3][1]){ 97 bool=true;num=i;break;} 98 } 99 return bool;100 }101 function InClose(arr){102 var bool=false;103 for(var i=0;i<closelist.length;i++){104 if((arr[0]==closelist[i][3][0])&&(arr[1]==closelist[i][3][1])){105 bool=true;break;}106 }107 return bool;108 }109 function IsPass(pos){110 if((";"+n_path+";").indexOf(";"+pos+";")!=-1)111 return true;112 return false;113 }114 function Sort(arr){115 var temp;116 for(var i=0;i<arr.length;i++){117 if(arr.length==1)break;118 if(arr[i][0]<=arr[i+1][0]){119 temp=arr[i];120 arr[i]=arr[i+1];121 arr[i+1]=temp;122 }123 if((i+1)==(arr.length-1))124 break;125 }126 }127 function main(){128 GetF(GetRound(s_path[3]));129 Sort(openlist);130 s_path=openlist[openlist.length-1];131 closelist[closelist.length]=s_path;132 openlist[openlist.length-1]=null;133 if(openlist.length==0){alert("找不到路径");return;}134 openlist.length=openlist.length-1;135 if((s_path[3][0]==p_end[0])&&(s_path[3][1]==p_end[1])){136 getPath();137 }138 else{maptt.rows[s_path[3][1]].cells[s_path[3][0]].style.backgroundColor="#00ff00";setTimeout("main()",100);}139 }140 function getPath(){141 var str="";142 var t=closelist[closelist.length-1][4];143 while(1){144 str+=t.join(",")+";";145 maptt.rows[t[1]].cells[t[0]].style.backgroundColor="#ffff00";146 for(var i=0;i<closelist.length;i++){147 if(closelist[i][3][0]==t[0]&&closelist[i][3][1]==t[1])148 t=closelist[i][4];149 }150 if(t[0]==p_start[0]&&t[1]==p_start[1])151 break;152 }153 alert(str);154 }155 function setPos(){156 var h=(Math.abs(p_end[0]-p_start[0])+Math.abs(p_end[1]-p_start[1]))*gw;157 s_path=[h,0,h,p_start,p_start];158 }159 function set(id,arr){160 switch(id){161 case 1:162 p_start=arr;163 maptt.rows[arr[1]].cells[arr[0]].style.backgroundColor="#ff0000";break;164 case 2:165 p_end=arr;maptt.rows[arr[1]].cells[arr[0]].style.backgroundColor="#0000ff";break;166 case 3:167 n_path+=arr.join(",")+";";maptt.rows[arr[1]].cells[arr[0]].style.backgroundColor="#cccccc";break;168 default:169 break;170 }171 }172 function setflag(id){flag=id;}173 </script>174 <table id="maptt" cellspacing="1" cellpadding="0" border="0" bgcolor="#000000">175 <script>176 for(var i=0;i<h;i++){177 document.write("<tr>");178 for(var j=0;j<w;j++){179 document.write(‘<td onclick="set(flag,[‘+j+‘,‘+i+‘]);" bgcolor="#ffffff" width="20" height="20"></td>‘);180 }181 document.write("</tr>");182 }183 </script>184 </table>185 <a href=http://www.mamicode.com/"javascript:setflag(1);">设置起点</a><br>186 <a href=http://www.mamicode.com/‘javascript:setflag(2);‘>设置终点</a><br>187 <a href=http://www.mamicode.com/‘javascript:setflag(3);‘>设置障碍点</a><br>188 <input type="button" onclick="setPos();main();this.disabled=true;" value=http://www.mamicode.com/"find">189 </body>190 </html>
js_常见排序算法
1 <html><head><script> 2 Array.prototype.swap = function(i, j) 3 { 4 var temp = this[i]; 5 this[i] = this[j]; 6 this[j] = temp; 7 } 8 9 Array.prototype.bubbleSort = function() 10 { 11 for (var i = this.length - 1; i > 0; --i) 12 { 13 for (var j = 0; j < i; ++j) 14 { 15 if (this[j] > this[j + 1]) this.swap(j, j + 1); 16 } 17 } 18 } 19 20 Array.prototype.selectionSort = function() 21 { 22 for (var i = 0; i < this.length; ++i) 23 { 24 var index = i; 25 for (var j = i + 1; j < this.length; ++j) 26 { 27 if (this[j] < this[index]) index = j; 28 } 29 this.swap(i, index); 30 } 31 } 32 33 Array.prototype.insertionSort = function() 34 { 35 for (var i = 1; i < this.length; ++i) 36 { 37 var j = i, value = http://www.mamicode.com/this[i]; 38 while (j > 0 && this[j - 1] > value) 39 { 40 this[j] = this[j - 1]; 41 --j; 42 } 43 this[j] = value; 44 } 45 } 46 47 Array.prototype.shellSort = function() 48 { 49 for (var step = this.length >> 1; step > 0; step >>= 1) 50 { 51 for (var i = 0; i < step; ++i) 52 { 53 for (var j = i + step; j < this.length; j += step) 54 { 55 var k = j, value = http://www.mamicode.com/this[j]; 56 while (k >= step && this[k - step] > value) 57 { 58 this[k] = this[k - step]; 59 k -= step; 60 } 61 this[k] = value; 62 } 63 } 64 } 65 } 66 67 Array.prototype.quickSort = function(s, e) 68 { 69 if (s == null) s = 0; 70 if (e == null) e = this.length - 1; 71 if (s >= e) return; 72 this.swap((s + e) >> 1, e); 73 var index = s - 1; 74 for (var i = s; i <= e; ++i) 75 { 76 if (this[i] <= this[e]) this.swap(i, ++index); 77 } 78 this.quickSort(s, index - 1); 79 this.quickSort(index + 1, e); 80 } 81 82 Array.prototype.stackQuickSort = function() 83 { 84 var stack = [0, this.length - 1]; 85 while (stack.length > 0) 86 { 87 var e = stack.pop(), s = stack.pop(); 88 if (s >= e) continue; 89 this.swap((s + e) >> 1, e); 90 var index = s - 1; 91 for (var i = s; i <= e; ++i) 92 { 93 if (this[i] <= this[e]) this.swap(i, ++index); 94 } 95 stack.push(s, index - 1, index + 1, e); 96 } 97 } 98 99 Array.prototype.mergeSort = function(s, e, b)100 {101 if (s == null) s = 0;102 if (e == null) e = this.length - 1;103 if (b == null) b = new Array(this.length);104 if (s >= e) return;105 var m = (s + e) >> 1;106 this.mergeSort(s, m, b);107 this.mergeSort(m + 1, e, b);108 for (var i = s, j = s, k = m + 1; i <= e; ++i)109 {110 b[i] = this[(k > e || j <= m && this[j] < this[k]) ? j++ : k++];111 }112 for (var i = s; i <= e; ++i) this[i] = b[i];113 }114 115 Array.prototype.heapSort = function()116 {117 for (var i = 1; i < this.length; ++i)118 {119 for (var j = i, k = (j - 1) >> 1; k >= 0; j = k, k = (k - 1) >> 1)120 {121 if (this[k] >= this[j]) break;122 this.swap(j, k);123 }124 }125 for (var i = this.length - 1; i > 0; --i)126 {127 this.swap(0, i);128 for (var j = 0, k = (j + 1) << 1; k <= i; j = k, k = (k + 1) << 1)129 {130 if (k == i || this[k] < this[k - 1]) --k;131 if (this[k] <= this[j]) break;132 this.swap(j, k);133 }134 }135 }136 137 function generate()138 {139 var max = parseInt(txtMax.value), count = parseInt(txtCount.value);140 if (isNaN(max) || isNaN(count))141 {142 alert("个数和最大值必须是一个整数");143 return;144 }145 var array = [];146 for (var i = 0; i < count; ++i) array.push(Math.round(Math.random() * max));147 148 array.push("９９");149 150 txtInput.value = http://www.mamicode.com/array.join(" ");151 txtOutput.value = http://www.mamicode.com/"";152 }153 154 function demo(type)155 {156 var array = txtInput.value =http://www.mamicode.com/= "" ? [] : txtInput.value.replace().split(" ");157 for (var i = 0; i < array.length; ++i) array[i] = parseInt(array[i]);158 var t1 = new Date();159 eval("array." + type + "Sort()");160 var t2 = new Date();161 lblTime.innerText = t2.valueOf() - t1.valueOf();162 txtOutput.value = http://www.mamicode.com/array.join(" ");163 }164 165 166 function search()167 {168 var txtSearch =document.getElementById("txtSearch");169 var array = txtInput.value =http://www.mamicode.com/= "" ? [] : txtInput.value.replace().split(" ");170 var arrayResult = new Array();171 var t1 = new Date();172 alert(array.length);173 for (var i = 0; i < array.length; ++i)174 {175 176 if( array[i].indexOf( txtSearch.value ) >= 0 ) {177 arrayResult.push(array[i]);178 }179 }180 181 //eval("array." + type + "Sort()");182 var t2 = new Date();183 lblTime.innerText = t2.valueOf() - t1.valueOf();184 txtOutput.value = http://www.mamicode.com/arrayResult.join(" ");185 }186 187 188 </script></head>189 <body onl oad=generate()>190 <table style="width:100%;height:100%;font-size:12px;font-family:宋体">191 <tr>192 <td align=right>193 <textarea id=txtInput readonly style="width:100px;height:100%"></textarea>194 </td>195 <td width=150 align=center>196 检索 <input id="txtSearch" value=http://www.mamicode.com/"" style="width:50px"><br><br>197 随机数个数<input id=txtCount value=http://www.mamicode.com/500 style="width:50px"><br><br>198 最大随机数<input id=txtMax value=http://www.mamicode.com/1000 style="width:50px"><br><br>199 <button onclick=generate()>重新生成</button><br><br><br><br>200 耗时(毫秒)：<label id=lblTime></label><br><br><br><br>201 <button onclick=demo("bubble")>冒泡排序</button><br><br>202 <button onclick=demo("selection")>选择排序</button><br><br>203 <button onclick=demo("insertion")>插入排序</button><br><br>204 <button onclick=demo("shell")>谢尔排序</button><br><br>205 <button onclick=demo("quick")>快速排序(递归)</button><br><br>206 <button onclick=demo("stackQuick")>快速排序(堆栈)</button><br><br>207 <button onclick=demo("merge")>归并排序</button><br><br>208 <button onclick=demo("heap")>堆排序</button><br><br>209 <button onclick=search()>检索</button><br><br>210 </td>211 <td align=left>212 <textarea id=txtOutput readonly style="width:100px;height:100%"></textarea>213 </td>214 </tr>215 </table>216 </body></html>
[转载]
http://www.w3cfuns.com/blog-5425789-5399153.html
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。