作者简介:

       姜海强:闷骚码农,互联网行业摸爬滚打数余载,先后担任中国体育直播TV主程、网信集团先锋支付架构师、奇虎360服务器端资深开发。热爱技术,喜欢分享,热衷领域:PHP/Golang语言、面向对象设计模式、Redis、Yaf、Yii2、微服务等。

视频课程

yaf+yar微服务-腾讯课堂
yaf+yar微服务-51CTO学院
CSDN学院

Github

个人主页
swoole-boot
roach
roach-orm

QQ群:

姜海强的QQ群

公众号:

360tryst公众号

插入排序

插入排序的工作原理是通过构建有序序列,依次对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入,直到遍历完未排序数据为止。

代码实现

  1. func InsertSort(arr []int) {
  2. len := len(arr)
  3. if len < 2 {
  4. return
  5. }
  6. for n := 1; n < len; n++ {
  7. current := arr[n]
  8. m := n
  9. for m > 0 && arr[ m - 1] > current {
  10. if arr[ m - 1] > current {
  11. arr[m] = arr[m - 1]
  12. }
  13. m--
  14. }
  15. arr[m] = current
  16. }
  17. }

调用案例

  1. func main() {
  2. data := []int{12, 45, 2, 6, 678, 1, 2, 5, 8, 1, 30}
  3. InsertSort(data)
  4. fmt.Println(data)
  5. }

以上例程输出

  1. [1 1 2 2 5 6 8 12 30 45 678]

时间复杂度

最好 最坏 平均 稳定性
O(n) O(n平方) O(n平方) 稳定

适用场景

插入排序适用于已经有部分数据已经排好,并且排好的部分越大越好。一般在输入规模大于1000的场合下不建议使用插入排序

QQ群:

姜海强的QQ群

公众号:

360tryst公众号