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

冒泡排序

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)
不稳定排序
以上这一种实现是非原地排序