数据结构

内排序1:插入排序

2020-05-04  本文已影响0人  玲儿珑

插入排序有几种,这里讨论的是简单插入排序法,也称为直接插入排序法

基本思想:第i趟排序是将第i+1个元素ki+1(i=1,2,...,n-1)插入到一个已经按值有序的子序列(k1,k2,...,k`i)的合适位置,得到一个长度为i+1且仍然按值有序的子序列(k1,k2,...,ki,ki+1)。插入方法的核心动作是插入,而寻找被插入元素的合适位置是主要工作。
算法如下:

function insertSort(arr) {
    let n = arr.length
    let i, j, temp
    for ( i=1; i<n; i++) {
        temp = arr[i]
        j = i-1
        while ( j>=0 && temp<arr[j] ) {
            arr[j+1] = arr[j--]
        }
        arr[j+1] = temp
    }
    return arr
}

let arr = [5,3,8,1,9,2,7,4,6,10]
insertSort(arr)

性能:
时间复杂度:最坏时O(n2),最好时O(n)。是稳定性排序方法。

基本思想:由于每一趟被插入的子序列为一个按值有序的序列,因而可以采用 折半查找方法 来确定被插入元素在该有序排序中的合适位置。
算法如下:

function bin_insertSort(arr) {
    let n = arr.length
    let low, high, mid, i, j, temp
    for( i=1; i<n; i++ ) {
        temp = arr[i]
        low = 0
        high = i-1
        while ( low<=high ) {
            mid = Math.floor((low+high)/2)
            if ( temp<arr[mid] ) {
                high = mid-1
            } else {
                low = mid+1
            }
        }
        for( j=i-1; j>=low; j-- ) {
            arr[j+1] = arr[j]
        }
        arr[low] = temp
    }
    return arr
}

let arr = [5,3,8,1,9,2,7,4,6,10]
bin_insertSort(arr) 

性能:
时间复杂度:最坏时O(n2),最耗时O(nlog2n)。

上一篇下一篇

猜你喜欢

热点阅读