javascript常用算法

常用算法

算法是计算机编程非常重要的组成部分，算法可以让你很好的提高效率…

冒泡排序

1、
  var arr = [5,39,8,1,2,13,55];
  arr = arr.sort(function(a,b){return a-b});
  console.log(arr);//1,2,5,8,13,39,55
2、
  function bubbleSort(items){
     var len=items.length;
     for(var i=0;i<len;i++ ){
       for(var j=0;j<len-i-1;j++){
         if(items[j]>items[j+1]){
            var temp=items[j];
            items[j]=items[j+1];
            items[j+1]=temp;
        }
      }
    }
    return items;
  }

快速排序

var arr = [5,39,8,1,2,13,55];
function quickSort(arr){
  if(arr.length<=1) return arr;
    var valIndex=Math.floor(arr.length/2),//基准值
           val=arr.splice(valIndex,1)[0],
            left=[],
            right=[];
    for(var i=0;i<arr.length;i++){
      if(arr[i]<val){
        left.push(arr[i]);
      }else{
       right.push(arr[i]);
      }
    }
  return quickSort(left).concat([val],quickSort(right));
}
quickSort(arr);

二分查找 有序数组

function binarySearch(val,arr,startIndex,endIndex){
  if(!value||!(arr instanceof Array)) return;
  var len = arr.length,
      startIndex = typeof startIndex === 'number'?startIndex:0,
      endIndex = typeof endIndex === 'number'?endIndex:len-1,
      midIndex = Math.floor((startIndex + endIndex)/2),
      midVal = arr[midIndex];
  if(startIndex>endIndex) return;
  if(midval === val){
    return midval;
  }else if(midval>val){  
    return  binarySearch(val,arr,startIndex,midIndex-1);
  }else{
    return binnarySearch(val,arr,midIndex+1,endIndex);
 }
}

数组去重

//ie8 Array无indexOf属性
function unique(arr){
   var n=[];
   for (var i = 0; i<=arr.length; i++) {
     n.indexOf(arr[i])==-1&&n.push(arr[i]);
   }
   return n;
}
//hash
function unique2(arr){
  var n=[],obj={};
  for(var i=0;i<arr.length;i++){
     if(obj[arr[i]]==undefined){
        obj[arr[i]]=1;
        n.push(arr[i]);
     }else if(obj[arr[i]]===1){
      continue;
     }
  }
  return n;
}

函数柯里化

var fn=function(a,b,c){
  return a+b+c
}
function curry(fn){
    var arr=[],
        fnlen=fn.length,
        myslice=arr.slice;
    function currying(){
       arr=arr.concat(myslice.call(arguments));
       if(arr.length<fnlen){
         return currying;
       }
       return fn.apply(this,arr);
    }
    return currying;
}
curry(fn)(1)(2)(3)//6

函数节流

function thottle(fn,delay,duration){ 
   var timer=null,begin=new Date();
   return function(){
     var context=this,arg=arguments,curr=new Date();
     clearTimeout(timer);
     if(curr-begin>duration){
         fn.apply(context,arg);
         begin=curr;
     }else{
       timer=setTimeout(function(){
        fn.apply(context,arg);
      },delay);
     }
   }
}

拷贝

function clone(obj) {
  var buf;
  if(obj instanceof Array) {
    buf = [];
    var len = buf.lenght;
    while(len--){
     buf[len]=clone(obj[len]);
    }
    return buf;
  }else if(obj instanceof Object) {
    buf = {};
    for(var s in obj){
      buf[s] = clone(obj[s]);
    }
    return buf;
  }else {
    return obj;
  }
}

两个很大的数字相加

function sumStrings(a,b) {
    a = '0' + a;    //加0是因为两个最大的位数相加后可能需要进位
    b = '0' + b;

    var arrA = a.split(''),//将数字转成字符串
    arrB = b.split(''),
    res = [],
    temp = '',
    carry = 0,
    distance = a.length - b.length,  //计算两个数值字符串的长度差
    len = distance > 0 ? a.length : b.length;

    //在长度小的那个数值字符串前面添加distance个0，这样两个数值的位数就保持一致，
    //如：9797979797、34646，需要将这两个数值转成['0','9','7','9','7','9','7','9','7','9','7']、['0','0','0','0','0','3','4','6','4','6']
    if(distance > 0){
      for(let i = 0; i < distance; i++){
        arrB.unshift('0');
      }

    }else{
      for(let i = 0; i < Math.abs(distance); i++){
        arrA.unshift('0');
      }
    }

    //从数组的最后一位开始向前遍历，把两个数组对应位置的数值字符串转成整形后相加，
    //carry表示相加后的进位，比如最后一位相加是7+6=13，这里进位carry是1
    //在遍历的时候每次都加上上次相加后的carry进位
    for(let i = len - 1; i >= 0; i--){
      temp = +arrA[i] + (+arrB[i]) + carry;
      if(temp > 10){  
        carry = 1;
        res.push((temp + '')[1]);

      }else{
        carry = 0;
        res.push(temp);
      }
    }
    res = res.reverse().join('').replace(/^0/,'');
    console.log(res)
}
 sumStrings('30000000000000000000000000','91111111111111111111111111');

产生一个3-8的随机数字

var randomInt = (min, max) => Math.floor(Math.random() * (max - min) + min);
console.log(randomInt(3, 8))