插入排序示意图
插入排序原理:通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应的位置并插入。
插入排序很类似排纸牌,从牌桌上抓牌排在手里,手里的牌始终是有序的,每次都把牌放在相应的位置,这就是插入排序。
举例说明:{1,9,7,2,3,6,4,5}
假设第一位的数字为有序(只有它自己一个,当然有序),
第1次遍历:把9拿来插入到有序的序列中,不过9比1大,都无需交换,我们就得到了新的有序序列{1,9}
第一次遍历
第2次遍历:我们把7拿来插入到{1,9}有序数列中,得到新的有序序列{1,7,9}
第2次遍历
第3次遍历:我们把2拿来插入到{1,7,9}有序序列中,得到新的有序序列{1,2,7,9}
第三次遍历
由于原理很简单,中间过程就不更多赘述了,我们总共遍历了n-1次也就是7次,
得到有序数列{1, 2, 3, 4, 5, 6, 7, 9}
JAVA实现代码:
插入排序代码
程序运行结果:
插入排序运行结果
下面为错过前几期排序算法的同学附上文章链接,有什么不懂的欢迎评论区留言哦~
经典排序算法三 选择排序(JAVA实现)
经典排序算法二 快速排序(JAVA实现)
经典排序算法一 冒泡排序(JAVA实现)
如果觉得《经典排序算法四 插入排序(JAVA实现)》对你有帮助,请点赞、收藏,并留下你的观点哦!