插入排序属于内部排序算法，把待排序数组分为已排序区间和未排序区间两部分：
1. 初始状态下，已排序区间只有数组的第一个元素，剩余元素为未排序区间；
2. 依次取出未排序区间的第一个元素，将其与已排序区间的元素从后往前逐一比较；
3. 如果已排序区间的当前元素大于待插入元素，就将该元素向后移动一位；
4. 找到待插入元素的合适位置后，将其放入，完成一次插入操作；
5. 重复上述步骤，直到未排序区间为空，数组整体有序。
public class InsertionSort {
public static void insertionSort(int[] arr) {
if (arr == null<= 1) {
return;
}
for (int i = 1; i < arr.length; i++) {
int current = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > current) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = current;
}
}
public static void main(String[] args) {
int[] arr = {5, 2, 9, 1, 5, 6};
System.out.println("排序前数组：");
for (int num : arr) {
System.out.print(num + " ");
}
insertionSort(arr);System.out.println("\n排序后数组：");for (int num : arr) {System.out.print(num + " ");}
}
}