常见算法是js实现汇总
/*去重*/
<script>
function delRepeat(arr){
var newArray=new Array();
var len=arr.length;
for(var i=0;i<len;i++){
for(var j=i+1;j<len;j++)
{
if(arr[i]==arr[j])
{
++i;
}
}
newArray.push(arr[i]);
}
return newArray;
}
var arr=new Array("red","red","1","5","2");
alert(delRepeat(arr));
</script>
/*二分法*/
又称为折半查找算法，但是有缺陷就是要求数字是预先排序好的
function binary(items,value){
var startIndex=0,
stopIndex=items.length-1,
midlleIndex=(startIndex+stopIndex)>>>1;
while(items[middleIndex]!=value && startIndex<stopIndex){
if(items[middleIndex]>value){
stopIndex=middleIndex-1;
}else{
startIndex=middleIndex+1;
}
middleIndex=(startIndex+stopIndex)>>>1;
}
return items[middleIndex]!=value ? false:true;
}
/*十六进制颜色值的随机生成*/
function randomColor(){
var arrHex=["0","2","3","4","5","6","7","8","9","a","b","c","d"],
strHex="#",
index;
for(var i=0;i<6;i++){
index=Math.round(Math.random()*15);
strHex+=arrHex[index];
}
return strHex;
}
/*一个求字符串长度的方法*/
function GetBytes(str){
var len=str.length,
bytes=len;
for(var i=0;i<len;i++){
if(str.CharCodeAt>255){
bytes++;
}
}
return bytes;
}
/*插入排序*/
所谓的插入排序，就是将序列中的第一个元素看成一个有序的子序列，然后不段向后比较交换比较交换。
---------------------------------华丽丽的分割线-------------------------------------
function insertSort(arr){
var key;
for(var j = 1; j < arr.length ; j++){
//排好序的
var i = j - 1;
key = arr[j];
while(i >= 0 && arr[i] > key){
arr[i + 1] = arr[i];
i --;
}
arr[i + 1] = key;
}
return arr;
}
/*希尔排序*/
希尔排序，也称递减增量排序算法具体描述：http://zh.wikipedia.org/zh/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F
其实说到底也是插入排序的变种
function shellSort(array){
var stepArr = [1750, 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;
var stepLen = len%step > 0 ? parseInt(len/step) + 1 : len/step;
for(;i < 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;
}
}
}
return array;
}
/*快速排序*/
其实说到底快速排序算法就系对冒泡排序的一种改进，采用的就是算法理论中的分治递归的思想，说得明白点，它的做法就是：通过一趟排序将待排序的纪录分割成两部分，其中一部分的纪录值比另外一部分的纪录值要小，就可以继续分别对这两部分纪录进行排序；不段的递归实施上面两个操作，从而实现纪录值的排序。
这么说可能不是很清晰，直接上代码：
<script>
function sort(arr){
return quickSort(arr,0,arr.length-1);
function quickSort(arr,l,r){
if(l<r){
var mid=arr[parseInt((l+r)/2)],i=l-1,j=r+1;
while(true){
//大的放到右边，小的放到左边, i与j均为游标
while(arr[++i]<mid);
while(arr[--j]>mid);
if(i>=j)break;//判断条件
var temp = arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
quickSort(arr,l,i-1);
quickSort(arr,j+1,r);
}
return arr;
}
}
function main(){
var list=new Array(49,38,65,97,76,13,27);
document.write(sort(list).valueOf());
}
main();
</script>
原理图：
/*冒泡法*/
function bullSort(array){
var temp;
for(var i=0;i<array.length;i++){
for(var j=array.length-1;j>i;j--){
if(array[j]<array[j-1]){
temp = array[j];
array[j]=array[j-1];
array[j-1]=temp;
}
}
}
return array;
}
/*js递归实现方案*/
递归函数是在一个函数通过调用自身的情况下去解决的：
方式如下：
function factorial(num){
if(num<=1){
return 1;
}else{
return num*factorial(num-1);
}
}
但是这在js里面可能会出现错误：
var anotherFactorial = factorial;
factorial=null;
alert(anoterFactorial(4));
因为在调用anoterFactorial时内部的factorial已经不存在了。
解决方法是通过arguments.callee来解决。
如下：
function factorial(num){
if(num<=1){
return 1;
}else{
return num*arguments.callee(num-1);
}
var anotherFactorial = factorial;
factorial = null;
alert(anotherFactorial(4));
成功！！！！
}
/**js模拟多线程**/
<html><head><title>emu -- 用command模式模拟多线程</title></head><body>
<SCRIPT LANGUAGE="JavaScript">
<!--
if (Array.prototype.shift==null)
Array.prototype.shift = function (){
var rs = this[0];
for (var i=1;i<this.length;i++) this[i-1]=this[i]
this.length=this.length-1
return rs;
}
if (Array.prototype.push==null)
Array.prototype.push = function (){
for (var i=0;i<arguments.length;i++) this[this.length]=arguments[i];
return this.length;
}
var commandList = [];
var nAction = 0;//控制每次运行多少个动作
var functionConstructor = function(){}.constructor;
function executeCommands(){
for (var i=0;i<nAction;i++)
if (commandList.length>0){
var command = commandList.shift();
if (command.constructor == functionConstructor)
if (command.scheduleTime == null || new Date()-command.scheduleTime>0)
command();
else
commandList.push(command);
}
}
function startNewTask(){
var resultTemp = 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--;
else temp.innerHTML = temp.innerHTML - (-n);
if (n<1000)
commandList.push(function(){simThread(temp,++n)});
else{
var command = function(){document.body.removeChild(temp);;nAction--;};
command.scheduleTime = new Date()-(-2000);
commandList.push(command);
}
}
window.onload = function(){setInterval("executeCommands()",1);}
//-->
</SCRIPT>
<button onClick="startNewTask()">开始新线程</button>
<BR><BR>
<div id=sampleResult onMouseOver="this.stop=true" onMouseOut="this.stop=false" >0</div>
</body>
</html>
/*选择法排序*/
选择法主要有三种：
《1》简单的选择排序：简单的前后交互。
/*简单选择法排序*/
其实基本的思想就是从待排序的数组中选择最小或者最大的，放在起始位置，然后从剩下的数组中选择最小或者最大的排在这公司数的后面。
http://zh.wikipedia.org/wiki/%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F
function selectionSort(data)
{
var i, j, min, temp , count=data.length;
for(i = 0; i < count - 1; i++) {
/* find the minimum */
min = i;
for (j = i+1; j < count; j++)
{ if (data[j] < data[min])
{ min = j;}
}
/* swap data[i] and data[min] */
temp = data[i];
data[i] = data[min];
data[min] = temp;
}
return data;
}
《2》树型排序：又称锦标赛排序，首先对n个元素进行两两比较，然后在其中[n/2]个较小者再进行两两比较如此重复直至选出最小的关键字的纪录为止。（可用完全二差树表示）。缺点：辅助空间需求过大，和“最大值”进行多余比较
《3》堆排序：（不适用于纪录数较少的文件）
堆排序算法的过程如下:
1)得到当前序列的最小(大)的元素
2)把这个元素和最后一个元素进行交换,这样当前的最小(大)的元素就放在了序列的最后,而原先的最后一个元素放到了序列的最前面
3)的交换可能会破坏堆序列的性质(注意此时的序列是除去已经放在最后面的元素),因此需要对序列进行调整,使之满足于上面堆的性质.
重复上面的过程,直到序列调整完毕为止.
js实现：
<script>
/**
* 堆排序
* @param items 数组
* @return 排序后的数组
*/
function heapSort(items)
{
items = array2heap(items); //将数组转化为堆
for(var i = items.length - 1; i >= 0; i--)
{
items = swap(items, 0, i); //将根和位置i的数据交换(用于将最大值放在最后面)
items = moveDown(items, 0, i - 1); //数据交换后恢复堆的属性
}
return items;
}
/**
* 将数组转换为堆
* @param items 数组
* @return 堆
*/
function array2heap(items)
{
for(var i = Math.ceil(items.length / 2) - 1; i >= 0; i--)
{
items = moveDown(items, i, items.length - 1); //转换为堆属性
}
return items;
}
/**
* 转换为堆
* @param items 数组
* @param first 第一个元素
* @param last 最后一个元素
* @return 堆
*/
function moveDown(items, first, last)
{
var largest = 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; //跳出循环
}
}
return items;
}
/**
* 交换数据
* @param items 数组
* @param index1 索引1
* @param index2 索引2
* @return 数据交换后的数组
*/
function swap(items, index1, index2)
{
var tmp = items[index1];
items[index1] = items[index2];
items[index2] = tmp;
return items;
}
var a = [345,44,6,454,10,154,3,12,11,4,78,9,0,47,88,9453,4,65,1,5];
document.write(heapSort(a));
</script>
所谓归并就是将两个或者两个以上的有序表合成一个新的有序表。
递归形式的算法在形式上较为简洁但实用性较差，与快速排序和堆排序相比，归并排序的最大特点是，它是一种稳定的排序方法。
js实现归并：
<script>
function MemeryArray(Arr,n, Brr, m)
{ var i, j, k;
var Crr=new Array();
i = j = k = 0;
while (i < n && j < m)
{
if (Arr[i] < Brr[j])
Crr[k++] = Arr[i++];
else
Crr[k++] = Brr[j++];
}
while (i < n)
Crr[k++] = Arr[i++];
while (j < m)
Crr[k++] = Brr[j++];
return Crr;
}
var 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
for i from 0 to lenStr1
d[i, 0] := i
for j from 0 to lenStr2
d[0, j] := j
for i from 1 to lenStr1
for j from 1 to lenStr2
if str1[i] = str2[j] then cost := 0
else cost := 1
d[i, j] := minimum(
d[i-1, j ] + 1, // deletion
d[i , j-1] + 1, // insertion
d[i-1, j-1] + cost // substitution
)
return d[lenStr1, lenStr2]；
这个算法其实就是一个矩阵的计算：
k i t t e n
0 1 2 3 4 5 6
s 1 1 2 3 4 5 6
i 2 2 1 2 3 4 5
t 3 3 2 1 2 3 4
t 4 4 3 2 1 2 3
i 5 5 4 3 2 2 3
n 6 6 5 4 3 3 2
g 7 7 6 5 4 4 3
首先给定第一行和第一列，然后，每个值d[i,j]这样计算：d[i,j] = min(d[i-1,j]+ 1,d[i,j-1] +1,d[i-1,j-1]+(str1[i] == str2[j]?0:1));
最后一行，最后一列的那个值就是LD的结果。
LD(str1,str2) <= max(str1.len,str2.len)；
有人提出了Levenshtein automaton（Levenshtein自动机）来计算和某个字符串距离小于某个值的集合。这样能够加快近似字符串的计算过程。见文献：Klaus U. Schulz, Stoyan Mihov, Fast String Correction with Levenshtein-Automata. International Journal of Document Analysis and Recognition, 5(1):67--85, 2002.
A Guided Tour to Approximate String Matching GONZALO NAVARRO
这篇文章里面对这个方面（字符串相似）进行了很多描述。其中，包含了动态规划法计算Edit distance的方法。
-------------------------------------------华丽丽的分割线-------------------------------------------------------------------------
js实现：
<script>
//求两个字符串的相似度,返回差别字符数,Levenshtein Distance算法实现
function Levenshtein_Distance(s,t){
var n=s.length;// length of s
var m=t.length;// length of t
var d=[];// matrix
var i;// iterates through s
var j;// iterates through t
var s_i;// ith character of s
var t_j;// jth character of t
var cost;// cost
// Step 1
if (n == 0) return m;
if (m == 0) return n;
// Step 2
for (i = 0; i <= n; i++) {
d[i]=[];
d[i][0] = i;
}
for (j = 0; j <= m; j++) {
d[0][j] = j;
}
// Step 3
for (i = 1; i <= n; i++) {
s_i = s.charAt (i - 1);
// Step 4
for (j = 1; j <= m; j++) {
t_j = t.charAt (j - 1);
// Step 5
if (s_i == t_j) {
cost = 0;
}else{
cost = 1;
}
// Step 6
d[i][j] = Minimum (d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1] + cost);
}
}
// Step 7
return d[n][m];
}
//求两个字符串的相似度,返回相似度百分比
function Levenshtein_Distance_Percent(s,t){
var l=s.length>t.length?s.length:t.length;
var d=Levenshtein_Distance(s,t);
return (1-d/l).toFixed(4);
}
//求三个数字中的最小值
function Minimum(a,b,c){
return a<b?(a<c?a:c):(b<c?b:c);
}
var str1="ddsddf",str2="xdsfsx";
alert(Levenshtein_Distance_Percent(str1,str2));
</script>
相关推荐
JS 数据结构与算法.pdf 本书主要介绍了 JavaScript 语言的基础知识，包括数据结构和算法。以下是该书的详细知识点： 一、JavaScript 基础知识 * 变量和数据类型 * 运算符和控制结构 * 函数和对象 * 数组和字符串 ...
JavaScript算法训练营是一个专注于提升JavaScript开发者算法能力的学习资源。在这个训练营中，参与者将深入学习和实践各种算法，从而提高编程技巧，理解数据结构，并掌握解决复杂问题的方法。JavaScript作为前端开发...
JavaScript（简称JS）是一种广泛应用于Web开发的轻量级编程语言，它在处理算法和数据结构方面具有强大的能力。...通过学习和实践这些JavaScript算法，开发者可以提升解决问题的能力，更好地理解和优化数据处理的效率。
前端学习 html css js 算法前端学习 html css js 算法前端学习 html css js 算法 前端学习 html css js 算法前端学习 html css js 算法前端学习 html css js 算法 前端学习 html css js 算法前端学习 html css js ...
JavaScript算法是编程领域中的核心部分，它涉及到一系列用于解决复杂问题的步骤和数据处理方法。在JavaScript中，算法的应用广泛，包括数据排序、搜索、优化等。本篇将深入探讨两个重要的JavaScript算法：二分查找和...
**JavaScript 算法与数据结构精华集** 在软件开发领域，掌握良好的算法和数据结构是提升编程能力的关键。尤其对于使用 JavaScript 这样的多用途语言的开发者来说，理解并能够应用这些概念不仅可以优化代码效率，还...
ES6的JavaScript算法思想实现之分而治之、动态规划、贪心算法和回溯算法 一、分而治之算法思想实现 分而治之算法是一种常用的算法思想，它将原问题分解为多个小问题，解决小问题，然后将小问题的解决方案组合起来...
在这个场景中，JavaScript算法可能包含一系列操作，如哈希计算、位操作、异或等，用于创建一个独特的加密密钥。这个密钥会被用来加密"0ar"开头的数据，确保其在传输过程中的安全性。 Python在数据处理和爬虫编写...
在“JavaScript_来自JS算法数据结构课程的挑战文档.zip”这个压缩包中，我们很可能会找到一系列针对JavaScript算法和数据结构的学习资源。这些挑战通常旨在帮助开发者提升对JavaScript核心概念的理解，以及在实际...
在这个"three.js算法寻路示例"中，我们将探讨如何结合three.js、Vue框架以及几种路径寻找算法来解决3D环境中的寻路问题。 首先，让我们了解`three.js`。Three.js是一个开源的JavaScript库，它为WebGL提供了一个高级...
JavaScript算法与数据结构是编程领域中的核心概念，尤其在Web开发中，JavaScript作为最常用的客户端脚本语言，理解和掌握其算法与数据结构至关重要。这个"JS算法 数据结构 精华集.zip"压缩包很可能包含了关于...
标题中的“一个很不错的js算法”指的是在JavaScript中实现的一种创新的、视觉效果良好的花朵渐变色算法。这种算法能够创建出美观的花朵图案，并且颜色会呈现出平滑的过渡，给用户带来舒适的视觉体验。JavaScript是一...
js所有的算法，自己总结的，如有遗漏，请留言。希望可以帮助到需要的人
《_ac_signature加密JS算法详解》 在网络安全领域，数据加密是确保信息隐私和安全的重要手段。本文将深入探讨一种名为"_ac_signature"的JavaScript加密算法，它在 ZIP 包内的"dy_ac_signature"文件中被实现。这个...
通过阅读这个文件，你可以快速了解如何在自己的项目中集成和使用Cardinal曲线JS算法。 `CHANGE.log`记录了项目的版本更新历史，包括新增功能、修复的bug和性能改进等，这对于跟踪库的演化和确定是否需要升级到新...
24点牌js算法，24点牌js算法，24点牌js算法
首先，"JS指数算法"是指使用JavaScript实现的指数运算算法。指数运算在数学上是基于幂次运算的，即a的b次方（a^b）。在JavaScript中，可以使用Math.pow()函数进行指数运算，例如`Math.pow(2, 3)`会返回8，表示2的3...
前端JavaScript算法集源码.zip前端JavaScript算法集源码.zip前端JavaScript算法集源码.zip前端JavaScript算法集源码.zip前端JavaScript算法集源码.zip前端JavaScript算法集源码.zip
这个项目主要针对的是如何在Python环境中，利用JavaScript算法来规避浏览器的自动化检测，从而提高爬虫的生存能力。以下是对这个主题的详细解释： 一、Python自动化 Python是一种广泛用于Web爬虫开发的语言，其丰富...