JS常见算法详解
算法是程序的灵魂，一个优秀前端工程师对算法也是要有所了解的，本文总结了我们在开发、面试中经常会遇到的基础算法，使用原生JS实现，未必是最优解，可以互相探讨。
为了便于查看，简单分下类，本文也会持续更新。
排序算法
1.冒泡排序
functionbubbleSort(arr){
vari=j=0;
for(i=1;i<arr.length;i++){
for(j=0;j<=arr.length-i;j++){
vartemp=0;
if(arr[j]>arr[j+1]){
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
}
2.快速排序
functionquickSort(arr,l,r){
if(l<r){
vari=l,j=r,x=arr[i];
while(i<j){
while(i<j&&arr[j]>x)
j--;
if(i<j)
//这里用i++，被换过来的必然比x小，赋值后直接让i自加，不用再比较，可以提高效率
arr[i++]=arr[j];
while(i<j&&arr[i]<x)
i++;
if(i<j)
//这里用j--，被换过来的必然比x大，赋值后直接让j自减，不用再比较，可以提高效率
arr[j--]=arr[i];
}
arr[i]=x;
quickSort(arr,l,i-1);
quickSort(arr,i+1,r);
}
}
3.二路归并
PS：将两个按值有序序列合并成一个按值有序序列，则称之为二路归并排序。
functionmerge(left,right){
varresult=[],
il=0,
ir=0;
while(il<left.length&&ir<right.length){
if(left[il]<right[ir]){
result.push(left[il++]);
}else{
result.push(right[ir++]);
}
}
while(left[il]){
result.push(left[il++]);
}
while(right[ir]){
result.push(right[ir++]);
}
returnresult;
}
字符串操作
1.判断回文字符串
functionpalindrome(str){
//\W匹配任何非单词字符。等价于“[^A-Za-z0-9_]”。
varre=/[\W_]/g;
//将字符串变成小写字符,并干掉除字母数字外的字符
varlowRegStr=str.toLowerCase().replace(re,'');
//如果字符串lowRegStr的length长度为0时，字符串即是palindrome
if(lowRegStr.length===0)
returntrue;
//如果字符串的第一个和最后一个字符不相同，那么字符串就不是palindrome
if(lowRegStr[0]!=lowRegStr[lowRegStr.length-1])
returnfalse;
//递归
returnpalindrome(lowRegStr.slice(1,lowRegStr.length-1));
}
2.翻转字符串
2.1思路1：反向遍历字符串
functionreverseString(str){
vartmp='';
for(vari=str.length-1;i>=0;i--)
tmp+=str[i];
returntmp
}
2.2思路2：转化成array操作。
functionreverseString2(str){
vararr=str.split("");
vari=0,j=arr.length-1;
while(i<j){
tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
i++;
j--;
}
returnarr.join("");
}
PS：什么？你要问为啥不直接操作str？因为str[i]是只读的，不能str[0]=str[1]这样操作。
再PS：如果允许用reverse()，也可以用'str'.split('').reverse().join('')实现。
3.生成指定长度随机字符串
PS：配合模糊等效果可以生成个验证码--
functionrandomString(n){
varstr='abcdefghijklmnopqrstuvwxyz0123456789';
vartmp='';
for(vari=0;i<n;i++)
tmp+=str.charAt(Math.round(Math.random()*str.length));
returntmp;
}
4.统计字符串中次数最多字母
PS：利用Object中key的唯一性，利用key来进行筛选，然后计数。
functionfindMaxDuplicateChar(str){
if(str.length==1){
returnstr;
}
varcharObj={};
for(vari=0;i<str.length;i++){
if(!charObj[str.charAt(i)]){
charObj[str.charAt(i)]=1;
}else{
charObj[str.charAt(i)]+=1;
}
}
varmaxChar='',
maxValue=1;
for(varkincharObj){
if(charObj[k]>=maxValue){
maxChar=k;
maxValue=charObj[k];
}
}
returnmaxChar+'：'+maxValue;
}
数组操作
1.数组去重
PS:还是利用Object中key的唯一性，利用key来进行筛选。
functionunique(arr){
varobj={}
vardata=[]
for(variinarr){
if(!obj[arr[i]]){
obj[arr[i]]=true;
data.push(arr[i]);
}
}
returndata;
}
2.Number数组中最大差值
functiongetMaxProfit(arr){
varmin=arr[0],max=arr[0];
for(vari=0;i<arr.length;i++){
if(arr[i]<min)
min=arr[i];
if(arr[i]>max)
max=arr[i];
}
returnmax-min;
}
其他常见算法
1.阶乘
1.1非递归实现
functionfactorialize(num){
varresult=1;
if(num<0)return-1;
if(num==0||num==1)return1;
while(num>1)
result*=num--;
returnresult;
}
1.2递归实现
functionfactorialize(num){
varresult=1;
if(num<0)return-1;
if(num==0||num==1)return1;
if(num>1){
returnnum*factorialize(num-1);
}
}
2.生成菲波那切数列
PS：斐波那契数列，又称黄金分割数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列主要考察递归的调用。通过定义fibo[i]=fibo[i-1]+fibo[i-2];来生成斐波那契数组。
2.1强行递归实现
functiongetfib(n){
if(n==0)
return0;
if(n==1)
return1;
if(n>1){
returngetfib(n-1)+getfib(n-2);
}
}
functionfibo(len){
varfibo=[];
for(vari=0;i<len;i++)
fibo.push(getfib(i));
returnfibo;
}
2.2简约非递归版
functiongetFibonacci(n){
varfibarr=[];
vari=0;
while(i<n){
if(i<=1){
fibarr.push(i);
}else{
fibarr.push(fibarr[i-1]+fibarr[i-2])
}
i++;
}
returnfibarr;
}
3.二分查找
PS：二分查找又称折半查找，是在有序数组查找中用到的较为频繁的一种算法，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。
3.1非递归实现
functionbinary_search(arr,key){
varlow=0,
high=arr.length-1;
while(low<=high){
varmid=parseInt((high+low)/2);
if(key==arr[mid]){
returnmid;
}elseif(key>arr[mid]){
low=mid+1;
}elseif(key<arr[mid]){
high=mid-1;
}
}
return-1;
};
3.2递归实现
functionbinary_search2(arr,low,high,key){
if(low>high)
return-1;
varmid=parseInt((low+high)/2);
if(key==arr[mid])
returnmid;
elseif(key>arr[mid])
returnbinary_search2(arr,mid+1,high,key);
elseif(key<arr[mid])
returnbinary_search2(arr,low,mid-1,key);
}
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，同时也希望多多支持毛票票！