1、定义

插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法。插入排序是一种简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动

2、时间复杂度、空间复杂度和稳定性

时间复杂度：平均复杂度O(n2)、最好复杂度O(n)、最坏复杂度O(n2)
空间复杂度：O(1)
稳定性：稳定

3、代码

public class InsertionSort {
    public static void main(String[] args) {
        int[] a = {9,3,1,4,8,7,5,2,6};
        sort(a);
        print(a);
    }
    static void sort(int[] a){
        /*for(int i=1;i<a.length;i++){   //1.0版
            for (int j=i;j>0;j--){
                if(a[j]<a[j-1]){
                    swap(a,j,j-1);
                }
            }
        }*/
        int  j=0, temp=0;
        for (int i = 1; i < a.length; i++) {
            temp = a[i];
            j = i - 1;
            while (j >= 0 && temp < a[j]) {
                a[j + 1] = a[j];
                j--;
            }
            a[j + 1] = temp;
        }
    }
    static void swap(int[] a,int i,int j){//简单的交换函数
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    static void print(int[] arr){
        for(int i=0;i<arr.length;i++){
            System.out.print(arr[i]+ " ");
        }
    }
}