原理

保证区间内排好顺序，逐渐将区间外数据插入到该区间中。

从局部扩散到整体。

第一次：保证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)  }  }  }  
}