java实现插入排序

时间复杂度：O(n²)

1. 算法思想

数组第一个数arr[0]视为有序，将第二个数arr[1]插入。插入完成后再将前两个数视为有序，
将第三个数插入。如此循环直至插入所有数。

2. 插入的过程

一次插入中，将arr[n+1]插入前面排好序的arr[0]~arr[n]中。若arr[n+1]<arr[n],则二者交换位置（可视为arr[n+1]插入到arr[n]前面，如{1,3,4,2}变为{1,3,2,4}），然后再将交换后的a【n】(也就是例子中的2)与a[n-1]比较，如此循环直至该数不再有比它大的数在前面或者该数已经到a[0]位置时结束一次插入过程。

3. java算法实现

public static void charu(int[] arr) {
            if(arr == null || arr.length<2) {
                return;
            }
            else {
                //数组第一个数arr[0]视为有序，从第二个数arr[1]开始插入
                for(int i = 1 ; i < arr.length ; i++) {
                    for(int j = i - 1 ; j >= 0 && arr[j] > arr[j + 1] ; j--) {
                        int temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                    }
                }
            }
        }