插入排序

类似生活中的整理扑克牌。来一张牌整理一下，如果前一张牌大于后面的牌，则把后面的牌移到前面。由于前面的牌都是依次排好序的，所以后面来的牌只需要大于它的前一张牌，而不用继续往前比较。这样插入排序相比选择排序就有了截断的操作，效率会高于选择排序。尤其在几乎是顺序结构的集合排序时，插入排序效率很高！
上代码：

public static void insertSort(int[] arr) {
        //第一个数自身就已经排序，所以索引从1开始
        for (int i = 1; i < arr.length; i++) {
            //跟着索引往前遍历，如果后面的大于前面的，则交换位置即可，否则此次排序完成，进入下一次
            for (int j = i; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    //交换操作，很费效率，可以采用赋值的方式改善。（此处用的是交换操作）
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                } else {
                    break;
                }
            }
        }
    }


public class insertSort {
    public static void main(String[] args) {
        int[] arr = {2, 4, 6, 3};
        int[] result = insertSort(arr);
        for (int i = 0; i < result.length; i++) {
            System.out.println(result[i]);
        }

    }

    public static int[] insertSort(int[] arr) {
        //从第二个元素开始
        for (int i = 1; i < arr.length; i++) {
            //如果i位置的元素大于它前面的元素，则代表需要排序
            if (arr[i] < arr[i - 1]) {
                //寻找i位置元素应该插在的位置,从【0，i）范围找，也就是从i的前面元素找应该插入的位置
                for (int j = 0; j < i; j++) {
                    //如果j位置的元素大于i位置的元素，则代表则j则是应该是i元素排序后所在的位置
                    if (arr[j] > arr[i]) {
                        //找到了位置，将[j,i)的元素往后面移动一位，注意此时需要反向遍历,避免覆盖
                        int temp = arr[i];
                        for (int k = i - 1; k >= j; k--) {
                            //后面的元素用前面的元素覆盖掉，由于已经把i位置的元素保存到temp中，所以覆盖掉i也没事
                            arr[k + 1] = arr[k];
                        }
                        arr[j] = temp;
                        break;
                    }
                }
            }
        }


        return arr;
    }
}
//结果：
2
3
4
6