【从 0 到 1 学算法】7. 直接插入排序
什么是直接插入排序
直接插入排序是基础排序的一种,它的思路是:有一个有序部分,一个无序部分,我们每一次拿无序部分的第一个元素对有序部分 从后往前进行比较(默认升序情况),如果小于则把比较的元素向后移一位 直到大于某个元素 此时把无序元素插入到这个位置。
算法原理
对于数列{9,3,7,2,5,8,1,4}元素进行升序插入排序
初始有序部分 9 无序部分 3 7 2 5 8 1 4
第一趟:3 9 7 2 5 8 1 4,有序 3 9 无序 7 2 5 8 1 4
第二趟:3 7 9 2 5 8 1 4,有序 3 7 9 无序 2 5 8 1 4
第三趟:2 3 7 9 5 8 1 4,有序 2 3 7 9 无序 5 8 1 4
第四趟:2 3 5 7 9 8 1 4,有序 2 3 5 7 9 无序 8 1 4
第五趟:2 3 5 7 8 9 1 4,有序 2 3 5 7 8 9 无序 1 4
第六躺:1 2 3 5 7 8 9 4,有序 1 2 3 5 7 8 9 无序 4
第七趟:1 2 3 4 5 7 8 9,有序 1 2 3 4 5 7 8 9 无序空
可以看出几个问题
1.8 个元素排序 7 趟
2.每次都是让无序部分的第一个元素和有序部分进行从后往前的比较 且比较成功 则有序部分向后移 直到比较不成功则 插入无序元素
3.我们这里排序采用的是有序元素向后移 无序元素插入的方式,比无序元素和有序元素依次交换的时间要少得多这是一个优化点
4.我们在有序部分比较不成功时 直接退出 而不是再继续向前比较,这是个优化点
代码示例
int t 临时变量 记录无序部分的第一个元素,因为后续有序部分向后移会覆盖这个元素
if 判断中:如果无序元素小于有序元素 有序元素向后移 如果无序元素大于等于有序元素 则说明应该插入到此位置 所以这里直接退出 从后向前比较有序 元素 因为最后 j-- 所以需要++才能插入到空出的位置
结果:
第 1 趟
3 9 7 2 5 8 1 4
第 2 趟
3 7 9 2 5 8 1 4
第 3 趟
2 3 7 9 5 8 1 4
第 4 趟
2 3 5 7 9 8 1 4
第 5 趟
2 3 5 7 8 9 1 4
第 6 趟
1 2 3 5 7 8 9 4
第 7 趟
1 2 3 4 5 7 8 9
版权声明: 本文为 InfoQ 作者【Geek_65222d】的原创文章。
原文链接:【http://xie.infoq.cn/article/6189ca7813ec7abe4419bf251】。未经作者许可,禁止转载。
评论