美文网首页
冒泡/插入/归并/快速 排序

冒泡/插入/归并/快速 排序

作者: 隐号骑士 | 来源:发表于2020-10-28 14:10 被阅读0次

    冒泡排序

    var sort = function(input){
        for(let i=0; i<input.length; i++){
            let flag = false
            for(let j= 0; j<input.length; j++){
                if(input[j]>input[j+1]){
                    temp = input[j]
                    input[j] = input[j+1]
                    input[j+1] = temp
                    flag = true
                }
            }
            if(!flag){
                break;
            }
        }
        return input
    }
    

    平均时间复杂度 O(n2)
    稳定排序
    原地排序

    插入排序

    var sort = function(input){
        for(let i=1; i<input.length; i++){
            let value = input[i]
            let j = i-1
            for(; j>=0; --j){
                if(value<input[j]){
                    input[j+1] = input[j]
                }else{
                    break
                }
            }
            input[j+1] = value
            
        }
        return input
    }
    

    平均时间复杂度 O(n2)
    稳定排序
    原地排序

    冒泡排序 VS 插入排序

    两者时间复杂度和空间复杂度相同
    逆序度相同的情况下,需要做相同次数的比较和交换操作,但对于交换操作本身,冒泡排序需要三次:

    temp = input[j]
    input[j] = input[j+1]
    input[j+1] = temp
    

    插入排序只需要一次

    input[j+1] = input[j]
    

    归并排序

    先分解再合并,合并的过程实际就是合并有序数组的过程

    var sort = function(array){
        if(array.length <=1 ){
            return array
        }
        const m = Math.floor((array.length-1)/2)
        const leftArray = array.slice(0,m+1)
        const rightArray = array.slice(m+1,array.length+1)
        const left = sort(leftArray)
        const right = sort(rightArray)
        return merge(left,right)
    }
    function merge (left,right){
        let result = []
        while(left.length && right.length){
            if(left[0]<=right[0]){
                result.push(left.shift())
            }else{
                result.push(right.shift())
            }
        }
        while(left && left.length){
            result.push(left.shift())
        }
        while(right && right.length){
            result.push(right.shift())
        }
        return result
    }
    

    平均时间复杂度 O(nlogn)
    稳定排序
    非原地排序

    快速排序

    数组中选择一个元素为pivot,然后比较其余元素和pivot,小于放左边,大于放右边,再对左右两边的数组分别执行以上逻辑。

    var sort = function(array){
        if(array.length <=1 ){
            return array
        }
        let pivot = array[0]
        let left =[] , right = []
        for(let i=1; i<array.length; i++){
            if(array[i]<= pivot){
                left.push(array[i])
            }else{
                right.push(array[i])
            }
        }
        const leftArray = sort(left)
        const rightArray = sort(right)
        return [...leftArray,pivot,...rightArray]
    }
    

    平均时间复杂度 O(nlogn)
    不稳定排序
    以上这一种实现是非原地排序

    相关文章

      网友评论

          本文标题:冒泡/插入/归并/快速 排序

          本文链接:https://www.haomeiwen.com/subject/jkdqvktx.html