将arr[i]复制为一个名为target的临时元素。 向下扫描列表，比较这个目标值target与arr[i-1]、arr[i-2]的大小，依次类推。 这个比较过程在小于或等于目标值的第一个元素(arr[j])处停止，或者在列表开始处停止（j=0）。 在arr[i]小于前面任何已排序元素时，后一个条件（j=0）为真， 因此，这个元素会占用新排序子列表的第一个位置。 在扫描期间，大于目标值target的每个元素都会向右滑动一个位置（arr[j]=arr[j-1]）。 一旦确定了正确位置j，目标值target（即原始的arr[i]）就会被复制到这个位置。 与选择排序不同的是，插入排序将数据向右滑动，并且不会执行交换。

package com.lifeibigdata.fight;/** * Created by lifei on 16/10/24. */public class InsertSort {    static int[] insertSort(int[] a){        int j;        for (int i = 1; i < a.length; i++) {            int target = a[i];            j = i;            while (j > 0 && target < a[j - 1]){                a[j] = a[j - 1];                j--;            }            a[j] = target;            for (int x:a) {                System.out.printf(x +" ");            }            System.out.println();        }        return a;    }        public static void main(String[] args) {//TODO 插入排序,只能在大于前一个值并且小于后一个值的地方交换,只大或者只小不能解决问题        int[] a = new int[]{2,3,5,1,4};        int[] r = insertSort(a);        for (int x:r) {            System.out.println(x);        }    }}//=======================================================/** *  *特点是简单，不需要额外的存储空间，在元素少的时候工作得好 */public class InsertSort {    public static void main(String[] args) {        int[] array = { 3, -1, 0, -8, 2, 1 };        printArray(array);        insertSort(array);        printArray(array);    }    public static void insertSort(int[] array) {        if (array == null || array.length < 2) {            return;        }        for (int i = 1; i < array.length; i++) {            int currentValue = array[i];            int position = i;            for (int j = i - 1; j >= 0; j--) {  //j表示已经插入元素的索引值                if (array[j] > currentValue) {                    array[j + 1] = array[j];                    position -= 1;                } else {                    break;                }            }            array[position] = currentValue;        }    }    public static void printArray(int[] array) {        System.out.print("{");        for (int i = 0; i < array.length; i++) {            System.out.print(array[i]);            if (i < array.length - 1) {                System.out.print(", ");            }        }        System.out.println("}");    }}