手写源码—javascript常见数据结构/深浅拷贝

[ymcdhr]

目录

1、快速排序 2、散列表 3、顺序查找 4、二分查找 5、数组去重 6、js事件节流 7、冒泡排序 8、js深拷贝

1.快速排序

（1）算法概要：

• 方法一，小于标记的存到一个数组，大于标记的存到一个数组，然后拼接数组。
• 方法二，j从右向左搜索，小于标记则和标记交换；i从左向右搜索，大于标记则和标记交换。
• 方法三，j从右向左搜索，小于标记则停止搜索；i从左向右搜索，大于标记则停止搜索；交换i和j；最后i==j时，交换当前元素和标记；效率比方法二稍高，因为if判断在for循环外面。

（2）算法代码实现：

    var arr=[44,75,23,43,55,12,64,77,33];

    function swap(arr,a,b){
        var tmp=arr[a];

        arr[a]=arr[b];
        arr[b]=tmp;

        return b;
    }

    // 快速排序方法一
    function qSort1(arr){
        var lArr = [],
            rArr = [],
            newArr = arr;
        var flag = arr[0];

        if(arr.length){
            for(var i=1;i<arr.length;i++){
                if(arr[i]<flag){
                    lArr.push(arr[i]);
                }
                else{
                    rArr.push(arr[i]);
                }
            }

            var newLeft = qSort1(lArr),
                newRight = qSort1(rArr);

            var newArr = newLeft.concat(flag).concat(newRight);
        }

        return newArr;

    }
    // 快速排序方法二
    // 交叉搜索，i从左到右标记，j从右到左标记
    // 先从右向左查询，如果比flag小的数，和标记位交换，暂停搜索
    // 再从右向左查询，如果比flag大的数，和标记位交换，暂停搜索
    // i=j的时候停止搜索，结束第一轮
    // 递归排序flag左右两侧子串，子串长度为1的时候停止递归
    function qSort2(arr,left,right){
        var flag = left,
            i = left,
            j = right;

        // 递归结束条件：子串长度等于0
        if(right-left>0){
            // 查询条件：
            // 先从右向左查询，再从左到右查询
            // 查询到中间的i=j时，停止查询
            while(i<j){
                // 从右向左查询比flag值更小的值
                for(;i<j;j--){
                    if(arr[j]<arr[flag]){
                        flag = swap(arr,flag,j);
                        // 重要：交换了就要停止查询
                        break;
                    }
                }
                // 从左向右查询比flag值更大的值
                for(;i<j;i++){
                    if(arr[i]>arr[flag]){
                        flag = swap(arr,flag,i);
                        break;
                    }
                }
            }
            // 递归排序左侧子串，右侧子串
            // flag为分割标记位，注意右侧子串起始位要+1，否则无法停止递归
            qSort2(arr,left,flag);
            qSort2(arr,flag+1,right);
        }

    }
    var newArr = qSort1(arr,0,arr.length-1);
    console.log("qSort1:",newArr);

2.散列表

（1）算法概要： （2）算法代码实现：

3.顺序查找

（1）普通查找最小值：

    // 顺序查找，查找最小值
    var arr=[44,75,23,43,55,12,64,77,33];

    function findMin(arr){
        var min = arr[0];

        for(var i=1;i<arr.length;i++){
            if(arr[i]<min){
                min = arr[i];
            }
        }

        return min;
    }

    console.log("findMin:",findMin(arr));

（2）自组织程序，提升查找性能：

    // 自组织程序
    // 普通的顺序查找
    // 根据频繁查找的记录，将频繁查找的元素每次向前挪一位

    var arr=[44,75,23,43,55,12,64,77,33];

    function findNum(arr,num){
        for(var i=0;i<arr.length;i++){
            if(arr[i]==num){
                i>0 && swap(arr,i,i-1);
                return num;
            }
        }
    }

    function swap(arr,a,b){
        var tmp=arr[a];

        arr[a]=arr[b];
        arr[b]=tmp;

        return b;
    }

    console.log(findNum(arr,43),arr);
    console.log(findNum(arr,43),arr);
    console.log(findNum(arr,43),arr);

43  [44, 75, 43, 23, 55, 12, 64, 77, 33]
43  [44, 43, 75, 23, 55, 12, 64, 77, 33]
43  [43, 44, 75, 23, 55, 12, 64, 77, 33]

4.二分查找

（1）算法概要： （2）算法代码实现：

    // 二分查找
    // 前提：针对有序数据集
    // 比中间值小就在左边继续查找
    // 比中间值大就在右边继续查找
    // 等于中间值就返回索引
    var arr=[12,23,33,43,44,55,64,75,77];

    function findX(arr,num,left,right){

        var mid = parseInt((left + right)/2);

        if(num == arr[mid]){
            return mid;
        }

        if(num < arr[mid]){
            return findX(arr,num,left,mid);
        }
        else{
            return findX(arr,num,mid+1,right);
        }
    }
    var index = findX(arr,33,0,arr.length-1);

    // 2 33
    console.log(index,arr[index]);

5.数组去重

（1）算法概要： （2）算法代码实现：

// 这种方式数组元素如果是对象，是否可行需要调查？
var arrTmp = [12,23,33,43,44,55,64,75,75,77,12,75,43,55];
var index = arrTmp.indexOf(33);
arrTmp.splice(index,1);
console.log(arrTmp);

    // 数组去重
    var arr=[12,23,33,43,44,55,64,75,75,77,12,75,43,55];

    var arrayClean = function (arr){
        var newArr = [],
            flagArr = {};

        for(var i=0;i<arr.length;i++){
            var x = arr[i];
            if(!flagArr[x]){
                newArr.push(x);
                flagArr[x] = true;
            }
        }

        return newArr;
    }

    console.log(arrayClean(arr));

6.js事件节流

（1）算法概要： （2）算法代码实现：

  <script>
    // 利用闭包写一个事件节流
    function periodEvent(time,action){
        var preTime = 0;

        return function(){
            var nowTime = new Date().getTime();
            if(nowTime-preTime>time){
                action.apply(this,arguments);
                preTime=nowTime;
            }
        }
    }

    // 调用示例
    var action = periodEvent(5000,function(fiveSeconeds){
        fiveSeconeds?console.log("5s后可以执行"):console.log("5s内不重复执行");
    });

    // 5s内不重复执行
    action();
    action();

    // 5s后可以执行
    setTimeout(function(){
        action(true);
    },6000);
  </script>

7.冒泡排序

（1）算法概要： （2）算法代码实现：

    var arr=[44,75,23,43,55,12,64,77,33];

    function swap(arr,a,b){
        var tmp=arr[a];

        arr[a]=arr[b];
        arr[b]=tmp;

        return b;
    }

    function sort(arr){
      var j = 0;
      while(j<arr.length-2){
        for(i=1;i<arr.length;i++){
          if(arr[i-1]>arr[i]){
            swap(arr,i-1,i);
          }
        }
        j++;
      }
    }

    sort(arr);
    console.log(arr);

8.js深拷贝

（1）算法概要： （2）算法代码实现：

    // 此方法无法拷贝function
    function deepClone(obj){
        if(obj instanceof Object){
          var newObj = obj instanceof Array?[]:{};

          for(var i in obj){
            if(obj.hasOwnProperty(i)){
                newObj[i] = deepClone(obj[i]);
            }
          }
        }else{
          return obj;
        }
        return newObj
    }

    var x = {
      name :[
        1,
        2,
        {w:function(){}},
        {y:3},
        {z:true}
      ],
      age: 10
    };

    var y = deepClone(x);
    y.name[3].y=5;
    y.name[4].z=false;
    console.log(x);
    console.log(y);

    /**
     * 深拷贝，可以拷贝function
     * @param {*} obj 
     */
    deepCopy(obj){
        if(typeof obj === "object"){
            if(obj !== null && !obj instanceof RegExp){
                let newObj = obj instanceof Array?[]:{};
                for(var attr in obj){
                    if(obj.hasOwnProperty(attr)){
                        newObj[attr] = this.deepCopy(obj[attr]);//不拷贝原型
                    }
                }

                return newObj;
            }
            else{
                return obj;
            }

        }
        else{
            return obj;
        }
    }