20170718-各種排序方法

PAMPANG 發(fā)布于2019-08-21 16:02 / 1058人閱讀

摘要：插入排序插入排序是穩(wěn)定的排序方法時間復(fù)雜度冒泡排序插入排序是穩(wěn)定的排序方法時間復(fù)雜度快速排序插入排序是不穩(wěn)定的排序方法時間復(fù)雜度選擇排序簡單選擇排序這種簡單選擇排序是穩(wěn)定的排序方法時間復(fù)雜度堆排序堆排序是

1.插入排序

function insertSort(array){
    var i = 0,
        j = 0,
        len = array.length,
        flag = 0
    for(i=1; i=0 && flag < array[j]; j--){
                array[j+1] = array[j]
            }
            array[j+1] = flag
        }
    }
}

插入排序是穩(wěn)定的排序方法

時間復(fù)雜度 O(n2)

2.冒泡排序

function bubbleSort(array){
    var i = 0,
        j = 0,
        len = array.length
    for(i=0; i

插入排序是穩(wěn)定的排序方法

時間復(fù)雜度 O(n2)


3.快速排序
function partition(array, low, high){
    var flag = array[low]
    while(low=flag && low

插入排序是不穩(wěn)定的排序方法

時間復(fù)雜度 O(nlogn)


4.選擇排序
簡單選擇排序
function selectSort(array){
    var i = 0,
        j = 0,
        temp = 0,
        len = array.length
    for(i=0; i< len; i++){
        j = array.indexOf(Math.min.apply(null, array.slice(i)))
        if(i!==j){
            temp = array[i]
            array[i] = array[j]
            array[j] = temp
        }
    }
}

這種簡單選擇排序是穩(wěn)定的排序方法

時間復(fù)雜度 O(n2)


堆排序
function HeapAdjust(array, s, m){
    var key = array[s]
    for(var j = 2*s; j<=m; j*=2){
        if(j= array[j]){
            break
        }
        array[s] = array[j]
        s = j
    }
    array[s] = key
}
function heapSort(array){
    array.unshift(0)
    var i = 0,
        length = array.length - 1
    for(i=Math.floor(length/2); i>0; i--){
        HeapAdjust(array, i, length)
    }
    for(i=length; i>0; --i){
        var temp = array[i]
        array[i] = array[1]
        array[1] = temp
        HeapAdjust(array, 1, i-1)
    }
    
}

堆排序是不穩(wěn)定的排序方法

時間復(fù)雜度 O(nlogn)


5.歸并排序
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())
        }
    }
    if(left.length){
        return result.concat(left)
    }
    if(right.length){
        return result.concat(right)
    }
}
function mergeSort(array){
    if(array.length <= 1){
        return array
    }
    let mid = Math.ceil(array.length / 2),
        left = array.slice(0, mid),
        right = array.slice(mid)
    
    return merge(mergeSort(left), mergeSort(right))
}

歸并排序是不穩(wěn)定的排序方法

時間復(fù)雜度 O(nlogn)