[数据结构与算法]排序算法之直接插入排序

定义思路

分为有序区间和无序区间
刚开始时，把第一个元素当成有序区间，后面的为无序区间。
每次选择无序区间的第一个元素，在有序区间内选择合适的位置插入（当前元素与有序区间比较）。
外层循环代表每次从无序区间找第一个元素和有序区间比较的次数。比如有5个数，刚开始有序区间为1个数，还要执行4次，有序区间达到5个数。
内层循环代表从有序区间拿到的最后一个元素与无序区间第一个元素进行比较

代码实现

public class Main4 {
    public static void main(String[] args) {
        int[] array = {3,6,7,7,5};
        insertSort(array);
        for (int i: array) {
            System.out.print(i + " ");
        }
    }

    public static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
        	//无序区间第一个元素
            int v = array[i];
            //有序区间最后一个元素
            int j = i-1;
            //没有判断array[j] == v，是因为保证了数据的稳定性，如果相等也挪动
            for (; j >= 0 && array[j] > v; j--) {
                array[j+1] = array[j];
            }
            array[j+1] = v;
        }
    }

稳定性：稳定