入门算法：插入排序

上手难度：★☆

算法复杂度：O(n^2)，但在数组近乎有序的情况下，插入排序的性能相对比较高，甚至比O(nlogn)还要高

insertionSort.gif

排序思想：
两层循环
第一层循环从1到arr.length，前闭后开
最开始记录arr[i]的值为temp，也就是红色标记块
然后再以i为最大值进行倒序遍历
将temp与arr[j-1]进行比较不断往前挪动，挪动条件是小于前面的值，直到挪到挪不动的位置，就将temp放到这个位置

代码实现：

public class InsertSort {

    public static void insertSort(int[] arr) {
        for(int i = 1; i < arr.length; i++){
            int temp = arr[i];//使用temp记录i对应位置的值
            int j;

            for(j = i; j > 0 && temp < arr[j - 1]; j--){
            //每次与j前面的数进行比较，如果小于前面的值，就让arr[j]等于前一位的值，
            //由于temp记录了arr[i]，最开始的j等于i，因此起初的值不会丢失
                arr[j] = arr[j - 1];//接收前一个元素的值
            }//从逻辑上来说，这里是将temp的值在小于arr[j-1]时，往前挪动
            
            arr[j] = temp;//到这一步，j自减到了temp>arr[j-1]的位置，
            //由于j的值在循环过程中已经被j+1接收了，因此让arr[j] = temp就完成了交换
        }
    }

    public static void main(String[] args) {
        int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};

        insertSort(arr);

        for( int i = 0 ; i < arr.length ; i ++ ){
            System.out.print(arr[i]);
            System.out.print(' ');
        }
    }

}

运行结果

排序结果

优点：
第二层循环由于是从i开始进行倒序循环，循环不用每次都完整循环，提高了效率，在面对一个近乎有序数组时，内层循环甚至只需要循环一次就能完成，例如 1 2 3 4这种，内层循环只需要循环一次即可，算法复杂度最高效的时候接近O(n)。