数据结构与算法之插入排序

插入排序（Insertion Sort）

核心思想：将数组中的数据分为两个区间，已排序区间和未排序区间。
初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，
并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。
总结思路：每次从未排序数据中取一个数，在已排序区间中逐个比较找到其应该在的位置。

代码：

/**
     * 数据分为两个区间，已排序区间和未排序区间
     * @param arrs
     */
    public static void sort(int[] arrs) {
        System.out.println("排序前的数组:");
        Arrays.stream(arrs).forEach(x->System.out.print(x + " "));
        for(int i=1; i<arrs.length; i++) {
            int value = arrs[i];
            int j = i-1;
            for(; j>=0; j--) {
                if(arrs[j]>value) {
                    arrs[j+1] = arrs[j];
                } else {
                    break;
                }
            }
            arrs[j+1] = value;
        }
        System.out.println();
        System.out.println("排序后的数组:");
        Arrays.stream(arrs).forEach(x->System.out.print(x + " "));
    }

输出：

排序前的数组:
6 2 7 1 2 10 3 
第1次冒泡:
2 6 7 1 2 10 3 
第2次冒泡:
2 6 7 1 2 10 3 
第3次冒泡:
1 2 6 7 2 10 3 
第4次冒泡:
1 2 2 6 7 10 3 
第5次冒泡:
1 2 2 6 7 10 3 
第6次冒泡:
1 2 2 3 6 7 10 
排序后的数组:
1 2 2 3 6 7 10 

代码分析：外层循环

for(int i=1; i<arrs.length; i++)

i从1开始，默认0的位置是已排序区间（循环开始，默认第一个数据是已排序区间）

内层循环

int value = arrs[i];
int j=i-1;
for(; j>=0; --j)
当前外层循环的一个数，依次和内层循环的已排序数据进行对比
发现外层循环的数小于已排序区间的数，则将已排序数据后移一位
当外层循环的数找到第一个不小于已排序区间的数，则是外层循环的数的对应位置，将数据插入该位置