插入排序
插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。
时间复杂度：O(n^2)
实现代码
/**
* 插入排序
*/
public static void insertSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int target = array[i];
int j = i; // 目标元素要插入的位置
while (j >= 1 && target < array[j - 1]) {
array[j] = array[j - 1];
j--;
}
array[j] = target;
}
}
/**
* 插入排序for循环写法
*/
public void insertSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int target = array[i]; // 要插入的元素
int position = i; // 要插入的位置
for (int j = i - 1; j >= 0; j--) { // 循环查找要插入的位置
if (array[j] > target) {
array[j + 1] = array[j]; // 比目标元素大的向后移
position = j;
} else {
break;
}
}
array[position] = target;
}
}
