直接插入排序

直接插入排序：基于有序数组元素内容的插入得来；

核心思想:将待排序的数据分为两个区间，已排序区间和待排序区间。

算法刚开始时，已排序空间有一个，在待排序空间中选择第一个元素与已排序空间最后一个元素比较，

若比已排序的最大元素大，直接放入已排序空间最后一个位置，否则需要找到合适位置后进行插入。

public static void insertaSort(int[] array){
        int n=array.length;
        if(n<=1){
            return ;
        }else{
            //外侧循环表示待排序区间
            for(int i=1;i<n;i++){
                int j=i-1,temp=array[i];
                //已排序区间，目的是将待排序区间的第一个数temp插入进去
                for(;j>=0;j--){
                    //如果temp小于已排序空间最后一个数，将该数向后移动一位
                    if(temp<array[j]){
                        array[j+1]=array[j];
                    }else{
                        //否则退出循环，说明已经找到位置
                        break;
                    }
                }
                //j+1就是找到的位置，因为在退出循环之前，一定是和插入位置的前一个位置进行比较，此时j是前一个位置的下标，所以插入位置是j+1
                array[j+1]=temp;
            }
        }
    }

算法的执行效率：最好 O（n）

​ 最坏 O（n^2）

算法的内存消耗：O（1）原地排序

算法的稳定性：插入排序是一个稳定性算法；