插入排序

插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增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;
    }
}