70
[golang] 数据结构-直接插入排序
source link: https://studygolang.com/articles/13719?amp%3Butm_medium=referral
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
原理
直接插入排序，也是一种非常简单的排序算法。
第一轮先从第二个元素开始，和第一个比较，如果较小就交换位置，本轮结束。第二轮从第三个元素开始，先与第二个比较，如果较小就与第二个交换，交换后再于第一个比较。如此循环直至最后一个元素完成比较逻辑。
复杂度
最好的情况下，直接插入排序只需进行n-1次比较，0次的交换。平均下来时间复杂度为 O(n^2)。
由于是每个元素逐个与有序的队列进行比较，所以不会出现相同数值的元素在排序完成后交换位置。所以直接插入排序是种稳定的排序算法。
代码
package main
import (
"fmt"
"math/rand"
)
func main() {
var length = 10
var tree []int
for i := 0; i < length; i++ {
tree = append(tree, int(rand.Intn(1000)))
}
fmt.Println(tree)
for i := 1; i < length; i++ {
for j := i; j > 0 && tree[j] < tree[j-1]; j-- {
tree[j], tree[j-1] = tree[j-1], tree[j]
}
fmt.Println(tree)
}
}
运行结果
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK