共计 1013 个字符,预计需要花费 3 分钟才能阅读完成。
导读 | 这篇文章主要为大家介绍了 Go 语言数据结构之插入排序示例详解,有需要的朋友可以借鉴参考下,希望能够有所帮助,祝大家多多进步,早日升职加薪 |
插入排序
插入排序,英文名(insertion sort)是一种简单且有效的比较排序算法。
思想:在每次迭代过程中算法随机地从输入序列中移除一个元素,并将改元素插入待排序序列的正确位置。重复该过程,直到所有输入元素都被选择一次,排序结束。
插入排序有点像小时候我们抓扑克牌的方式,如果抓起一张牌,我们放在手里;抓起第二张的时候,会跟手里的第一张牌进行比较,比手里的第一张牌小放在左边,否则,放在右边。
因此,对所有的牌重复这样的操作,所以每一次都是插入最正确的排序顺序,直到牌抓完为止。
动画演示
假设我们需要从小到大进行排序,动画演示如下:
Go 代码实现
package main
import "fmt"
func main() {arrays := []int{6, 2, 5, 8, 9, 3, 1}
length := len(arrays)
insertionSort(arrays, length)
for i := 0; i < length; i++ {fmt.Printf("%d", arrays[i])
}
}
func insertionSort(unsorted []int, length int) {
for i := 0; i < length; i++ {var insertElement = unsorted[i]
var insertPosition = i
for j := insertPosition - 1; j >= 0; j-- {if insertElement < unsorted[j] {unsorted[j+1] = unsorted[j]
insertPosition--
}
}
unsorted[insertPosition] = insertElement
}
}
运行结果:
[Running] go run "e:\Coding Workspaces\LearningGoTheEasiestWay\Go 数据结构 \main.go"
1 2 3 5 6 8 9
总结
插入排序实现简单,理解也较容易,数据量较少时效率高,算法的实际运行效率优于选择排序和冒泡排序。
空间复杂度:空间复杂度为 O(1),即不输入借助其他的辅助空间。
稳定性:插入排序是稳定的排序算法,在键值相同时它能够保持输入数据的原有次序。
正文完
星哥说事-微信公众号
![post-qrcode](https://www.xgss.net/wp-content/uploads/2023/07/二维码-微信公众号256x256.jpg)