天河商城型网站建设,如何查询某个网站的设计公司,物流企业的网站模板,网站代码管理原理
保证区间内排好顺序#xff0c;逐渐将区间外数据插入到该区间中。
从局部扩散到整体。
第一次#xff1a;保证0-1范围内有序 arr[0]和arr[1]对比#xff0c;若arr[0] 大于 arr[1] #xff0c;交换两个值#xff0c; 0-1范围内有序。
第二次#xff1a;保证 0-2 …原理
保证区间内排好顺序逐渐将区间外数据插入到该区间中。
从局部扩散到整体。
第一次保证0-1范围内有序 arr[0]和arr[1]对比若arr[0] 大于 arr[1] 交换两个值 0-1范围内有序。
第二次保证 0-2 范围内有序。 arr[2]和arr[1]比若 arr[1] 大于arr[2]交换两个值。 arr[1]和arr[0]再比arr[0] 大于 arr[1] 交换两个值。 至此0-2范围内有序。
第三次保证0-3范围内有序 arr[3]和arr[2]比若 arr[2] 大于arr[3]交换两个值。 arr[2]和arr[1]比若 arr[1] 大于arr[2]交换两个值。 arr[1]和arr[0]再比arr[0] 大于 arr[1] 交换两个值。 至此0-2范围内有序。
第i次保证0-i范围内有序 arr[i]和arr[i-1]比若 arr[i-1] 大于arr[i]交换两个值。
图解 复杂度
时间复杂度 O(n²)
最好情况 O(n)最差情况 O(n²) 额外空间复杂度 O(1)
代码实现
java
public static void insertSort(int[] array) { if (array null || array.length 2) { return; } for (int i 1; i array.length; i) { // 控制第几次循环 for (int j i; j 0; j--) { if (array[j] array[j - 1]) { swap(array, j, j -1); } } }
}kotlin
fun insertionSort(array: IntArray) { if (array.size 2) { return } for (i in 1 until array.size) { // 0 ~ i 做到有序 抓扑克牌 for (j in i - 1 downTo 0) { if (array[j] array[j 1]) { swap(array, j, j 1) } } }
}
