利用js来实现一些常用的算法

示例代码中的arr指的是给出的数组，s指的是数组的起始坐标0，end指的是数组的最后一个坐标arr.length-1,n指的是要查找的数字

查找某个值：

1.线性法

function findInArr(arr,item){
    for(var i=0;i<arr.length;i++){
        if(arr[i]==item){
            return true;
        }
    }
    return false;
}

2.二分法

function findInArr(n,s,e){
            //n为查找数字，s为起始位置下标0，e为结束为止下标arr.length-1

            if(s>e){
                return fasle;
            }else if(s==e){
                if(arr[s]==n){
                    return true;
                }else{
                    return false;
                }
            }
//这里的数组arr是已经从小到大排过序的数组
            var c=Math.floor((s+e)/2);
            if(arr[c]==n){
                return true;
            }else{
                if(n<arr[c]){
                    return findInArr(n,s,c);
                }else{
                    return findInArr(n,c+1,e);
                }
            }
        }

查找最小值：

    var arr=[1,28,47,53,68,108,200];
        function findMin(s,e){
            //s，e为数组下标start,end
            if(s>e){
                return null;
            }else if(s==e){
                return arr[s];
            }else if(s==e-1){
                if(arr[s]<arr[e]){
                    return arr[s];
                }else{
                    return arr[e];
                }
            }
            var c=Math.floor((s+e)/2);
            var l=findMin(s,c);
            var r=findMin(c+1,e);
            if(l<r){
                return l;
            }else{
                return r;
            }
        }

 去重：

function findInArr(arr,n){
            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 l=removeDup(arr,s,c);
            var r=removeDup(arr,c+1,e);
            while(r.length){
                if(findInArr(l,r[0])){
                    r.shift();
                }else{
                    l.push(r.shift());
                }
            }
            return l;
        }

 排序：

1.二分法

function mySort(arr,s,e){
            if(s>e){
                return [];
            }else if(s==e){
                return [arr[s]];
            }else if(s=e-1){
                if(arr[s]<arr[e]){
                    return [arr[s],arr[e]];
                }else{
                    return [arr[e],arr[s]];
                }
            }
            var c=Math.floor((s+e)/2);
            var l=mySort(arr,s,c);
            var r=mySort(arr,c+1,e);
            var aResult=[];
            while(l.length||r.length){
                if(l[0]<right[0]){
                    aResult.push(l.shift());
                }else{
                    aResult.push(r.shift());
                }
                if(l.length==0){
                    aResult=aResult.concat(r);
                    break;
                }else if(r.length==0){
                    aResult=aResult.concat(l);
                    break;
                }
            }
            return aResult;
        }

 2.冒泡排序

function bubbleSort(arr){
    for(var i=0;i<arr.length;i++){
        for(var j=0;j<arr.length;j++){
            if(arr[j+1]<arr[j]){
                var c = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = c;
            }
        }
    }
    return arr;
}

3.选择排序

function findArr(arr,start){
    var iMin = arr[start];
    var iMinIndex = start;
    for(var i=start;i<arr.lengthli++){
        if(arr[i]<iMin){
            iMin=arr[i];
            iMinIndex=i;
        }
    }
    return iMinIndex;
}
function selectionSort(arr){
    for(var i=0;i<arr.length;i++){
        var index=findMin(arr,i);
        var c;
        c=arr[index];
        arr[index]=arr[i];
        arr[i]=c;
    }
    return arr;
}

4.归并排序

function mergeSort(arr,s,e){
    if(s>e){
        return [];
    }else if(s==e){
        return [arr[s]];
    }else if(s==e-1){
        if(arr[s]<arr[e]){
            return [arr[s],arr[e]];
        }else{
            return [arr[e],arr[s]];
        }
    }
    var c = Math.floor((s+e)/2);
    var left = mergeSort(arr,s,c);
    var right = mergeSort(arr,c+1,e);
    var aResult = [];
    while(left.length||right.length){
        if(left[0]<right[0]){
            aResult.push(left.shift());
        }else{
            aResult.push(right.shift());
        }
        if(left.length==0){
            aResult = aResult.concat(right);
            break;
        }else if(right.length==0){
            aResult = aResult.concat(left);
            break;
        }
    }
    return aResult;
}

5.快速排序

function quickSort(arr,s,e){
    if(arr.length==0){
        return [];
    }
    var n = Math.floor((s+e)/2);
    var c = arr.splice(n,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,0,left.length-1).concat(c,quickSort(right,0,right.length-1))
}