package sort;

/**

* 插入排序

* 对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入

* <p>

* 1、从第一个元素开始，该元素认为已经被排序

* 2、取出下一个元素，在已排序的元素序列中从后向前扫描

* 3、如果已排序元素大于新元素，新元素继续比较前一个元素，直到找到已排序的元素小于或者等于新元素的位置

* 4、将新元素插入到该位置后

* 5、重复步骤2~4

*/

public class InsertionSort {

public static void main(String[] args) {

int[] a = {5, 2, 9, 4, 7, 6, 1, 3, 8};

int insertIndex, insertElement;

for (int i = 1; i < a.length; i++) { //外层循环，默认第一个元素有序，从第二个元素开始，时间复杂度N

insertIndex = i - 1; //插入的位置，默认有序数列的最后一个元素的位置

insertElement = a[i]; //新插入的元素，默认外层循环的元素

while (insertIndex >= 0 && a[insertIndex] > insertElement) { //内层循环，只要新元素比待插入位置的元素小就继续，时间复杂度N

a[insertIndex + 1] = a[insertIndex]; //比待插入元素大的元素后移一位

insertIndex--; //插入位置前移一位

}

a[insertIndex + 1] = insertElement; //内层循环结束，把新元素放到插入位置后面

}

for (int i : a) {

System.out.print(i + " ");

}

}

}