欢迎访问响应式个人博客!
男生版
女生版
初遇时,她的微笑,她往日的深情、承诺和傻劲,两个人共度的美丽时刻,一一印在回忆里,今天的感情已经比不上从前,但是我爱着恋着往日的她,舍不得离开!
排行
详情
您当前的位置>首页 > 正文
常见算法是js实现汇总
2017-10-24 14:42:03   来源:总结   评论:0 点击:

Arr=new Array(45,36,89,75,65);

var Brr=new Array(48,76,59,49,25);

alert(MemeryArray(Arr , Arr.length , Brr , Brr.length));

</script>

归并排序待续,先睡了:

----------------------------------------------华丽丽的分割线-------------------------------------------------------------------------

归并排序:

<script>

//将有二个有序数列a[first...mid]和a[mid...last]合并。

function mergearray(Arr,first,mid,last,tempArr)

{

       var i = first, j = mid + 1;

       var m = mid,   n = last;

       var k = 0;

       while (i <= m && j <= n)

       {

              if (Arr[i] < Arr[j])

                     tempArr[k++] = Arr[i++];

              else

                     tempArr[k++] = Arr[j++];

       }

       while (i <= m)

              tempArr[k++] = Arr[i++];

       while (j <= n)

              tempArr[k++] = Arr[j++];

       for (i = 0; i < k; i++)

              Arr[first + i] = tempArr[i];

}

function mergesort(Arr,first,last)

       var tempArr=new Array();

       if (first < last)

       {

         var mid = (first + last)>>>1;

         mergesort(Arr, first, mid, tempArr);    //左边有序

         mergesort(Arr, mid + 1, last, tempArr);  //右边有序

         mergearray(Arr, first, mid, last, tempArr);  //再将二个有序数列合并

       }

  return  Arr;

}

var Arr=new Array(1,65,45,98,56,78);

alert(mergesort(Arr,0,Arr.length-1));

</script>

 

 

/*比较两个字符串的相似性-Levenshtein算法简介*/

问题与描述:

近似字符串匹配问题

说明:设给定样本,对于任意文本串,样本P在文本T中的K-近似匹配(K-approximate match)是指P在T中包含最多K个差异的匹配,这里的差别指:

(1)修改:P与T中对应的字符不同
(2)删除:T中含有一个未出现在P中的字符
(3)插入:T中不包含出现在P中的一个字符

(也就是编辑距离问题)

例如: 
T: a p r o x i o m a l l y   
P: a p p r o x i m a t l y
经过 1:插入  2:删除 3:修改
那么 就是一个3-近似问题

事实上,两个字符串可能有不得出不同的差别数量,所以K-近似匹配要求:
(1)差别数最多为K个
(2)差别数为所有匹配方式下最少的称为编辑距离
(字符串T到P最少的差别数称为T和P的编辑距离)

试验要求:
(1)利用动态规划方法给出两个字符串编辑距离的算法
(2)分析复杂度
(3)考虑其它方法


Levenshtein Distance 来文史特距离

goodzzp

 LD也叫edit distance,它用来表示2个字符串的相似度,不同于Hamming Distance,它可以用来比较2个长度不同的字符串。LD定义为需要最少多少步基本操作才能让2个字符串相等,基本操作包含3个:
 1,插入;
 2,删除;
 3,替换;
 比如,kiteen和sitting之间的距离可以这么计算:
 1,kitten – > sitten, 替换k为s;
 2,sitten – > sittin, 替换e为i;
 3,sittin – > sitting, 增加g;
 所以,其LD为3;
 计算LD的算法表示为:
 int LevenshteinDistance(char str1[1..lenStr1], char str2[1..lenStr2])
 // d is a table with lenStr1+1 rows and lenStr2+1 columns
 declare int d[0..lenStr1, 0..lenStr2]
 // i and j are used to iterate over str1 and str2
 declare int i, j, cost

相关热词搜索:算法 常见

上一篇:JS地址栏动态传参查询的方法
下一篇:JavaScript里的循环方法

收藏