第九天 《简易算法代码》

算法：就是解决问题的方法和步骤，算法和相关的计算机语言无关

1. 使用find:线型查找

   递归代码：
   <script type="text/javascript">
   function jiecheng(n){
   if( n == 1){
   return 1;
   }
   return n * jiecheng(n-1);
   }
   alert(jiecheng(4));
   </script>

数组：

      1：后面加一个数：arr.push()
      2：后面删除一个数：arr.pop()
      3：前面加一个数：arr.unshift() 
      4：前面删除一个数：arr.shift(); //删除后返回的值是：number    
      5：删除：arr.splice('位置'，删除几个)；//删除后返回值是：objert

2. find2:二分查找

   find2：也叫分治法可以解决大多数算法问题。
   1：数组必须是有序的数组  
   2：必须知道怎么找中间数（取中间数的时候是偏左取）取中间值：Math.floor((s+e)/2); 
   3：要知道起始位置和结束范围
   

二分查找代码：

    //在数组里找重复
        function findInArray(n,arr){
            for(var i = 0; i <arr.length; i++){
                if(arr[i] == n){
                    return true;
                }
            }
            return false;
        }
        function removeDup(arr,s,e){
            if(s>e){
                return [];
            }
            else if(s==e){
                return[arr[s]];
            }
            var c = Math.floor((s+e)/2);
            var left = removeDup(arr,s,c);
            var right = removeDup(arr,c+1,e);
            
            for(var i = 0; i < right.length; i++ ){
                if(!findInArray(right[i],left)){
                    left.push(right[i]);
                }
            }
            return left;
        }
        var arr = [28,18,35,64,18,35,64,80];
        //document.write(removeDup(arr,0,arr.length-1));
        document.write(removeDup(arr,0,arr.length-1));

（1）：找最小值:首先要一分为二，left值=递归后左边最小，right值=递归后右边最小 ，最后比较left和right的返回值

在数组里找最小值的代码：

        function findMin(arr,s,e){
            if(s>e){
                return false;
            }
            else if(s==e){
                return arr[s];
            }
            
            var c = Math.floor((s+e)/2);
            var left = findMin(arr,s,c);
            var right = findMin(arr,c+1,e);
            
            if(left < right){
                return left;
            }
            else{
                return right;
            }
        };
        var arr = [28,-90,-100,50,60,100,700];
        alert(findMin(arr,0,arr.length-1));

（2）：数组去重：首先要一分为二，left递归后去重复，right递归后去重，循环right。如果不在left里，就加到left，然后返回left。
去重复代码：

  function findInArray(n,arr){
    for(var i=0; i<arr.length; i++){
        if(arr[i] == n){
            return true;
        }
    }
    return false;
};
    function removeDup(arr,s,e){
        if(s>e){
            return [];
        }
        else if(s == e){
            return [arr[s]];
        }           
        var c= Math.floor((s+e)/2);
        var left = removeDup(arr,s,c); 
        var right = removeDup(arr,c+1,e);           
        for(var i =0; i<right.length;i++){  
            if(!findInArray(right[i],left)){
                left.push(right[i]);
            }
        }
        return left;
    };
    var arr = [28,19,48,29,-40,48,100];
    document.write(removeDup(arr,0,arr.length-1));

2：选择排序：（插入排序）：从剩余的数据中，找嘴角的放到前面，并交换当前位置

选择排序代码：

         function selectionSort(arr){
            for(var i=0; i<arr.length; i++){
                for(var j=i+1; j<arr.length; j++){
                    if(arr[i]>arr[j]){
                        var tmp = arr[j];
                        arr[j] = arr[i];
                        arr[i] =tmp;
                    }
                }
            }
            return arr;
        };
        var arr = [-105,67,78,95,28,46];
        document.write(selectionSort(arr));

3:归并排序：分治法或者二分法思路左面排序自己，右边排序自己，每一比较左右数组的第一个值，比较后的最小值放到新的数组里。

归并排序代码：

      function mergesSort(arr,s,e){
    //判断相等的时候
    if(s>e){
        return [];  
    }else if( s==e){
        return [arr[s]];
    }
    //从中间切开
    var c = Math.floor((s+e)/2);
    var left = mergesSort(arr,s,c);
    var right = mergesSort(arr,c+1,e);
    var result = [];
    while(left.length || right.length){
        if(left[0]>right[0]){
            result.push(right.shift());
        }else{
            result.push(left.shift());
        }
        if(left.length == 0){
        result = result.concat(right);
            break;
        }else if(right.length == 0){
        result = result.concat(left);
            break;
        }
    }
    return result;
}
    var arr = [-105,28,29,30,29,28,45,30];
    document.write(mergesSort(arr,0,arr.length-1));

4:快速排序：分治法思路，找到中间位置，准备两个空数组分别方左右的值，递归后调用，链接数组c=arr.splice(cIndex,1),c[0]是中间的数组。

快速排序代码：

       function quickSort(arr,s,e){
    //判断是否相等
    if(arr.length == 0 ){
        return [];
    }
    var cIndex = Math.floor((s+e)/2);
    var c = arr.splice(cIndex,1);
    var left = [];
    var right = [];
    for(var i=0; i<arr.length; i++){
        if(arr[i]<c[0]){
            left.push(arr[i]);
        }else{
            right.push(arr[i]);
        }
    }
    //递归返回
    return quickSort(left).concat(c,quickSort(right));
}
    var arr = [-105,29,30,45,16,57];
    document.write(quickSort(arr));

数据结构：算法离不开数据结构，算法没有最好的算法，只有最合适的算法（有序数组--是数据结构 无序数组--是数据结构）

衡量算法的好坏两个指标：

        1，时间（时间复杂度用O表示）
        2，空间（空间复杂度S表示）

1：二叉树：
2：散列：也叫（哈希--hash）是指数组 存数据时使用下标
分析不同的数据结构是指：1，增加 2修改 3删除 4查询
数据不重复：（测试以毫秒为单位的运算速度）

                        增加：            查询：           综合
 无序数组:                50                39             85
 有序数组：             5000                5             5100           
   二叉树：              25                 12             35
    散列：               10                10              20