前端算法之排序搜索算法

排序搜索算法建议工具

工具地址：visualgo.net/zh

一、冒泡排序

<script type="text/javascript">
function arrSort( arr ){
    for(let i=0;i<arr.length-1;i++){
        for(let j=0;j<arr.length-1-i;j++){
            if( arr[j] > arr[j+1]){
                let temp = arr[j];
                arr[j] =  arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}
let arr = [29,10,14,37,14];
console.log( arrSort( arr ) );
</script>

二、选择排序

<script type="text/javascript">
function sortMin( arr ){
    let indexMin = 0;
    for( let i=0;i<arr.length-1;i++){
        indexMin = i;
        for( let j=i+1;j<arr.length;j++){
            if( arr[j] < arr[indexMin] ){
                indexMin = j;
            }
        }
        let temp = arr[i];
        arr[i] = arr[indexMin];
        arr[indexMin] = temp;
    }
    return arr;
}
let arr = [29,10,14,37,14];
console.log( sortMin(arr) );
</script>

三、插入排序

<script type="text/javascript">
function insertSort( arr ){
    let len = arr.length;
    for(let i=1;i<len;i++){
        let temp = arr[i];
        let j = i-1;//默认已排序的元素
        //在已经排序好的队列进行从后到前的扫描
        while( j>=0 && arr[j] > temp ){
            //已排序的元素大于新元素，将该元素移动到下一个位置
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = temp;
    }   
    return arr;
}
let arr = [5,3,4,2,1];
console.log(  insertSort(arr)  );
</script>

四、归并排序

<script type="text/javascript">
let arr = [8,4,5,7,1,3,6,2];
function mergeSort( arr ){
//视频课程：https://www.xuexiluxian.cn/course/detail/8429c57c800544f6b49fe73f9aae21de
    if( arr.length < 2 ) return arr;
    let mid = Math.floor(  arr.length/2 );

    let merge = function(leftArr,rightArr){
        console.log( leftArr,rightArr );
        let resultArr = [];
        while( leftArr.length && rightArr.length ){
            resultArr.push(  leftArr[0] <= rightArr[0] ? leftArr.shift() : rightArr.shift()   )
        }
        return resultArr.concat(leftArr).concat(rightArr);
    }

    return merge( 
        mergeSort(arr.slice(0,mid)),
        mergeSort(arr.slice(mid))
    );
}
console.log( mergeSort(arr)  );
</script>

五、快速排序

<script type="text/javascript">
let arr = [29,10,14,37,4];
function quickSort( arr ){
    if( arr.length <=1 ) return arr;
    let mid = Math.floor(  arr.length/2  );
    let pivot = arr.splice(mid,1)[0];
    let left =[];
    let right = [];

    for( let i=0;i<arr.length;i++){
        if( arr[i] <pivot ){
            left.push( arr[i] );
        }else{
            right.push( arr[i] );
        }
    }

    return quickSort(left).concat([pivot],quickSort(right));
}
console.log( quickSort(arr)  );
</script>

六、二分搜索

<script type="text/javascript">
let arr = [1,2,3,4,5,6,7];
let target = 6;
//视频课程：https://www.xuexiluxian.cn/course/detail/8429c57c800544f6b49fe73f9aae21de
function search( arr , target ){

    let conut = 1;
    let start = 0;
    let end = arr.length-1;
    while(  start<=end  ){
        //取出中间值
        let middle = Math.floor( (start+end)/2 );
        let guess = arr[middle];
        //如果中间 == 目标值
        console.log( conut );
        if( guess== target ){
            return middle;//返回位置
        }
        if( guess > target ){
            end = middle;
        }
        if( guess < target ){
            start = middle + 1;
        }
        conut++;
    }
    return -1;

}
console.log( search( arr , target) );
</script>