Golang排序算法-插入排序

2018-05-04 14:10:31 george518 ...

什么是插入排序

顺序从序列中取一个数与左侧的元素们做比较,如果左侧的元素比取的数大,就向右移,直到把取的数插入到不小于左侧元素的位置处。

此种排序方法类似于你在打扑克牌的时候,整理纸牌顺序的做法。

时间复杂度

时间复杂度为O(n^2)

/************************************************************
** @Description: insertion
** @Author: haodaquan
** @Date:   2018-09-02 11:03
** @Last Modified by:   haodaquan
** @Last Modified time: 2018-09-02 11:03
*************************************************************/
package insertion

func Sort(arr []int) []int {
    len := len(arr)
    if len < 2 {
        return arr
    }
    for i := 1; i < len; i++ {
        for j := i; j > 0; j-- {
            if arr[j] < arr[j-1] {
                arr[j-1], arr[j] = arr[j], arr[j-1]
            }

        }
    }
    return arr
}

测试代码和性能测试代码已经放到了github上,地址:

https://github.com/george518/PPGo_algorithm/tree/master/sort/insertion

不妨一试.

相似文章


345708673

在路上

技术无止境,一直在路上。 年过而立,惴惴不安,愈加发奋,孜孜求学。