插入排序-直接插入排序

1、原理：先假定数组只有一个数，然后后面进来的数与这个数比较，如果小于他，则换位置。以此类推，不断插入新的数，与前面数相比，比到前一个数小于他，而后一个数大于他时插入
2、图解

图片来自网络

3、java代码展示：

package Sort专题.InsertSort;


import java.util.Arrays;

public class DirectInsert {
    public static int[] sort(int arr[]){

        for(int i=1;i<arr.length;i++){
            //后一个数比前一个数小，因此要把它放到前面
            if(arr[i]<arr[i-1]){
                //将后一个数记录在temp里，方便和它前面的很多数比较
                int temp=arr[i];
                //j相当于在找当前需要插入的数的位置,不断用j-1的位置与要插入的值比较
                for(int j=i;j>=0;j--){
                    //如果j不在第一位，且该位置前面的值要大于要插入值，则证明要插入值还要往前比，那么把这个数向后移
                    if (j>0&&arr[j-1]>temp){
                        //这时arr[j-1]的位置虽然有数字，但是已经没有用，是要插入的预位置
                        arr[j]=arr[j-1];
                    }else{
                        arr[j]=temp;
                        break;
                    }
                }
            }
        }
        return arr;
    }
    public static void main(String[] args) {
        int arr[]={5,4,3,1,2};
        System.out.println(Arrays.toString(sort(arr)));
    }
}

4、时间复杂度
最优时间复杂度：当输入就为正序，那么只需插入n-1次，所以为O(n)
最坏时间复杂度：倒序输入，第一层：n-1次，第二层分别为：2，3，...n 次，所以O(1/2n²+1/2n-1)=O(n²)
平均时间复杂度：O(1/2(n-1+1/2n²+1/2n-1))=O(n²)
5、空间复杂度
O(1)
6、稳定性
稳定
算法稳定性什么意思？如果排序前两个相等的数据其在序列中的先后位置顺序与排序后它们两个先后位置顺序相同，我们说算法具有稳定性，有什么意义呢？如果排序的算法是稳定的，第一个次排序的结果和关键字段可以为第二个次排序所用。