算法与数据结构-算法篇-插入排序
程序员文章站
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)