欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

算法与数据结构-算法篇-插入排序

程序员文章站 2022-07-08 13:19:09
...

算法与数据结构-算法篇-插入排序

插入排序的思路是在数组内维护出一个有序数组,每次将取到的数按位置进行插入,得到一个排序好的数组
这种排序属于不稳定的排序,排序的性能可能会随意数组的结构而产生较大的差异
每一次排完序后,都要保证当前索引前面的所有数已经是一个有序数组即可
实现方式就是在数组的遍历过程中,索引每偏移一次,都将新的元素向前查找,找到对应的位置放进去,后面的元素后移

算法实现步骤

开始

开始时,索引指向0号位,然后向前看,越界了,比较停止

算法与数据结构-算法篇-插入排序

第二步

索引后移一步指向了2,2向前比较,发现7比2大,2移动到0号位,7向后移动一位

算法与数据结构-算法篇-插入排序

第三步

当前的索引位置为2,值为3,3开始和索引位1比较,发现3比7小,

算法与数据结构-算法篇-插入排序

第四步

拿到3号位的9,开始和2号位的7比较,发现9比较大,直接跳过

算法与数据结构-算法篇-插入排序

第五步

索引来到四号位置,得到值2,开始向3号位比较,小于9,再向2号位比较,小于7,再向1号位比较,小于3,再和0号位比较,不小于2,OK,放到1号位置,原本的1,2,3号位置集体右移一位

算法与数据结构-算法篇-插入排序

最后一步

基本和第五步一样,1找到0号位进行插入,其他数据右移

算法与数据结构-算法篇-插入排序

程序实现(java)

 		for (int i = 1; i < arr.length; i++) {
            for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
                swap(arr, i, j);
            }
        }

总结

  • 在上述的流程过程中,其实主要的时间都是消耗在寻找插入位与迁移数据中了,虽说可以通过二分的方式提升查找的性能 ,但是数据迁移的代价还是过高,因此,在数据已经排序好的情况下,不存在数据迁移与复制的场景下,时间复杂度为O(n),如果全倒序的情况下,复杂度O(n2)
相关标签: # 算法 算法