突破算法之-二分插入排序

 · 2018-8-19 · 次阅读


二分插入排序原理

二分法是对直接插入的改进,由直接插入排序的循环遍历找出插入点改为二分法找出插入点,时间复杂度O(nlogn)。

二分法插入排序是在插入第i个元素时,对前面的0~i-1元素进行折半,先跟他们中间的那个元素比,如果小,则对前半再进行折半,
否则对后半进行折半,直到left>right,然后再把第i个元素前1位与目标位置之间的所有元素后移,再把第i个元素放在目标位置上。

Golang实现

package main

import "fmt"

// 二分插入排序
// 算法思想简单描述:
//在插入第i个元素时,对前面的0~i-1元素进行折半,先跟他们
//中间的那个元素比,如果小,则对前半再进行折半,否则对后半
//进行折半,直到left>right,然后再把第i个元素前1位与目标位置之间
//的所有元素后移,再把第i个元素放在目标位置上。
func main() {

    array := []int{6, 7, 9, 3, 6, 8, 1, 9, 3}

    var start, end, temp, mid int

    for i := 1; i < len(array); i++ {

        start = 0
        end = i - 1
        temp = array[i]

        for start <= end {
            mid = (start + end) / 2
            if temp < array[mid] {
                end = mid - 1
            } else {
                start = mid + 1
            }
        }
        //循环完后,start=end+1,此时start为当前插入数字所待坑位
        //把坑位给当前插入的数据挪出来
        for j := i - 1; j >= start; j-- {
            array[j+1] = array[j]
        }
        //将当前插入数字挪入它该待的坑位
        array[start] = temp
    }

    fmt.Println(array)
}

github地址