常见算法是js实现汇总Word文件下载.docx
《常见算法是js实现汇总Word文件下载.docx》由会员分享,可在线阅读,更多相关《常见算法是js实现汇总Word文件下载.docx(23页珍藏版)》请在冰点文库上搜索。
=value&
&
startIndex<
stopIndex){
if(items[middleIndex]>
value){
stopIndex=middleIndex-1;
}else{
startIndex=middleIndex+1;
middleIndex=(startIndex+stopIndex)>
returnitems[middleIndex]!
=value?
false:
true;
/*十六进制颜色值的随机生成*/
functionrandomColor(){
vararrHex=["
0"
3"
4"
6"
7"
8"
9"
a"
b"
c"
d"
],
strHex="
#"
index;
6;
index=Math.round(Math.random()*15);
strHex+=arrHex[index];
returnstrHex;
/*一个求字符串长度的方法*/
functionGetBytes(str){
varlen=str.length,
bytes=len;
if(str.CharCodeAt>
255){
bytes++;
returnbytes;
/*插入排序*/
所谓的插入排序,就是将序列中的第一个元素看成一个有序的子序列,然后不段向后比较交换比较交换。
---------------------------------华丽丽的分割线-------------------------------------
functioninsertSort(arr){
varkey;
for(varj=1;
j<
arr.length;
j++){
//排好序的
vari=j-1;
key=arr[j];
while(i>
=0&
arr[i]>
key){
arr[i+1]=arr[i];
i--;
arr[i+1]=key;
returnarr;
/*希尔排序*/
希尔排序,也称递减增量排序算法具体描述:
http:
//zh.wikipedia.org/zh/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F
其实说到底也是插入排序的变种
functionshellSort(array){
varstepArr=[1750,701,301,132,57,23,10,4,1];
//reverse()在维基上看到这个最优的步长较小数组
vari=0;
varstepArrLength=stepArr.length;
varlen=array.length;
varlen2=
parseInt(len/2);
for(;
i<
stepArrLength;
i++){
if(stepArr[i]>
len2){
continue;
stepSort(stepArr[i]);
//排序一个步长
functionstepSort(step){
//console.log(step)使用的步长统计
vari=0,j=0,f,tem,key;
varstepLen=len%step>
0?
parseInt(len/step)+1:
len/step;
step;
i++){//依次循环列
for(j=1;
/*j<
stepLen&
*/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;
returnarray;
/*快速排序*/
其实说到底快速排序算法就系对冒泡排序的一种改进,采用的就是算法理论中的分治递归的思想,说得明白点,它的做法就是:
通过一趟排序将待排序的纪录分割成两部分,其中一部分的纪录值比另外一部分的纪录值要小,就可以继续分别对这两部分纪录进行排序;
不段的递归实施上面两个操作,从而实现纪录值的排序。
这么说可能不是很清晰,直接上代码:
functionsort(arr){
returnquickSort(arr,0,arr.length-1);
functionquickSort(arr,l,r){
if(l<
r){
varmid=arr[parseInt((l+r)/2)],i=l-1,j=r+1;
while(true){
//大的放到右边,小的放到左边,i与j均为游标
while(arr[++i]<
mid);
while(arr[--j]>
if(i>
=j)break;
//判断条件
vartemp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
quickSort(arr,l,i-1);
quickSort(arr,j+1,r);
functionmain(){
varlist=newArray(49,38,65,97,76,13,27);
document.write(sort(list).valueOf());
main();
原理图:
/*冒泡法*/
functionbullSort(array){
vartemp;
array.length;
for(varj=array.length-1;
j>
i;
j--){
if(array[j]<
array[j-1]){
temp=array[j];
array[j]=array[j-1];
array[j-1]=temp;
returnarray;
/*js递归实现方案*/
递归函数是在一个函数通过调用自身的情况下去解决的:
方式如下:
functionfactorial(num){
if(num<
=1){
return1;
returnnum*factorial(num-1);
但是这在js里面可能会出现错误:
varanotherFactorial=factorial;
factorial=null;
alert(anoterFactorial(4));
因为在调用anoterFactorial时内部的factorial已经不存在了。
解决方法是通过arguments.callee来解决。
如下:
return1;
returnnum*arguments.callee(num-1);
factorial=null;
alert(anotherFactorial(4));
成功!
!
/**js模拟多线程**/
html>
head>
title>
emu--用command模式模拟多线程<
/title>
/head>
body>
SCRIPTLANGUAGE="
JavaScript"
!
--
if(Array.prototype.shift==null)
Array.prototype.shift=function(){
varrs=this[0];
for(vari=1;
this.length;
i++)this[i-1]=this[i]
this.length=this.length-1
returnrs;
if(Array.prototype.push==null)
Array.prototype.push=function(){
for(vari=0;
arguments.length;
i++)this[this.length]=arguments[i];
returnthis.length;
varcommandList=[];
varnAction=0;
//控制每次运行多少个动作
varfunctionConstructor=function(){}.constructor;
functionexecuteCommands(){
nAction;
i++)
if(commandList.length>
0){
varcommand=commandList.shift();
if(command.constructor==functionConstructor)
if(command.scheduleTime==null||newDate()-command.scheduleTime>
0)
command();
else
commandList.push(command);
functionstartNewTask(){
varresultTemp=document.getElementById("
sampleResult"
).cloneNode(true);
with(resultTemp){
id="
"
;
style.display="
block"
style.color=(Math.floor(Math.random()*(1<
23)).toString(16)+"
00000"
).substring(0,6);
document.body.insertBefore(resultTemp,document.body.lastChild);
commandList.push(function(){simThread(resultTemp,1);
});
nAction++;
function
simThread(temp,n){
if(temp.stop)n--;
elsetemp.innerHTML=temp.innerHTML-(-n);
if(n<
1000)
commandList.push(function(){simThread(temp,++n)});
else{
varcommand=function(){document.body.removeChild(temp);
nAction--;
};
command.scheduleTime=newDate()-(-2000);
window.onload=function(){setInterval("
executeCommands()"
1);
//-->
/SCRIPT>
buttononClick="
startNewTask()"
开始新线程<
/button>
BR>
divid=sampleResultonMouseOver="
this.stop=true"
onMouseOut="
this.stop=false"
>
0<
/div>
/body>
/html>
/*选择法排序*/
选择法主要有三种:
《1》简单的选择排序:
简单的前后交互。
/*简单选择法排序*/
其实基本的思想就是从待排序的数组中选择最小或者最大的,放在起始位置,然后从剩下的数组中选择最小或者最大的排在这公司数的后面。
//zh.wikipedia.org/wiki/%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F
functionselectionSort(data)
{
vari,j,min,temp,count=data.length;
for(i=0;
i<
count-1;
i++){
/*findtheminimum*/
min=i;
for(j=i+1;
count;
j++)
{
if(data[j]<
data[min])
{min=j;
/*swapdata[i]anddata[min]*/
temp=data[i];
data[i]=data[min];
data[min]=temp;
returndata;
《2》树型排序:
又称锦标赛排序,首先对n个元素进行两两比较,然后在其中[n/2]个较小者再进行两两比较如此重复直至选出最小的关键字的纪录为止。
(可用完全二差树表示)。
缺点:
辅助空间需求过大,和“最大值”进行多余比较
《3》堆排序:
(不适用于纪录数较少的文件)
堆排序算法的过程如下:
1)得到当前序列的最小(大)的元素
2)把这个元素和最后一个元素进行交换,这样当前的最小(大)的元素就放在了序列的最后,而原先的最后一个元素放到了序列的最前面
3)的交换可能会破坏堆序列的性质(注意此时的序列是除去已经放在最后面的元素),因此需要对序列进行调整,使之满足于上面堆的性质.
重复上面的过程,直到序列调整完毕为止.
js实现:
/**
*堆排序
*@paramitems数组
*@return排序后的数组
*/
functionheapSort(items)
items=array2heap(items);
//将数组转化为堆
for(vari=items.length-1;
i>
=0;
i--)
items=swap(items,0,i);
//将根和位置i的数据交换(用于将最大值放在最后面)
items=moveDown(items,0,i-1);
//数据交换后恢复堆的属性
returnitems;
*将数组转换为堆
*@return堆
functionarray2heap(items)
for(vari=Math.ceil(items.length/2)-1;
items=moveDown(items,i,items.length-1);
//转换为堆属性
*转换为堆
*@paramfirst第一个元素
*@paramlast最后一个元素
functionmoveDown(items,first,last)
varlargest=2*first+1;
while(largest<
=last)
if(largest<
last&
items[largest]<
items[largest+1])
largest++;
if(items[first]<
items[largest])
items=swap(items,first,largest);
//交换数据
first=largest;
//往下移
largest=2*first+1;
else
largest=last+1;
//跳出循环
*交换数据
*@paramindex1索引1
*@paramindex2索引2
*@return数据交换后的数组
functionswap(items,index1,index2)
vartmp=items[index1];
items[index1]=items[index2];
items[index2]=tmp;
vara=[345,44,6,454,10,154,3,12,11,4,78,9,0,47,88,9453,4,65,1,5];
document.write(heapSort(a));
所谓归并就是将两个或者两个以上的有序表合成一个新的有序表。
递归形式的算法在形式上较为简洁但实用性较差,与快速排序和堆排序相比,归并排序的最大特点是,它是一种稳定的排序方法。
js实现归并:
functionMemeryArray(Arr,n,Brr,m)
{
vari,j,k;
varCrr=newArray();
i=j=k=0;
while(i<
n&
m)
if(Arr[i]<
Brr[j])
Crr[k++]=Arr[i++];
Crr[k++]=Brr[j++];
n)
while(j<