1. 插入排序

什么是插入排序？
插入排序（Insertion-Sort）：是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

1.1 算法描述

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤2~5。

1.2 时空复杂度

时间复杂度：O(n²) 最好O(n²) 最坏O(n)
空间复杂度：O(1)
稳定性：稳定（相同元素排序后相对位置不发生交换）

1.3 动图演示

1.4 算法实现

移动法

public class insertSort {
    public static void main(String[] args) {
        int[] num = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48} ;
        int j;
        //i=1；从1开始，没必要和自己比
        for (int i = 1; i < num.length ; i++) {
            //记录要插入的值，这时就有了一个长度为i+1的数组可以进行移动
            int temp = num[i];
            System.out.print("第"+i+"次移动的位置：");
            //在已排序的数组中找到比记录值（temp）要小的值，位置往后移动（记住此时的数组长度（i+1））
            //要明白为什么往后移动。
            //j >= 0&&num[j] > temp要满足这两个条件，j才会j--；
            for (j = i - 1;j >= 0&&num[j] > temp ;j--)
            {
                System.out.print(j+" ");
                //符合条件的往后移动一位
                num[j + 1] = num[j];
            }
            System.out.println("\n第"+i+"次移动后的数组："+Arrays.toString(num)+"，此时j+1的位置为："+(j+1));
            //归位，此时符合条件的都全部移动了一位，此时的j+1就是记录值要插入的位置
            num[j + 1] = temp;
            System.out.println("第"+i+"次交换后的结果："+Arrays.toString(num));
        }
        System.out.println("最终的排序结果："+Arrays.toString(num));
    }

}

交换法

public static void insertSort(int[] arr){
    for(int i = 0; i < arr.length; i++){
        for(int j = i; j>=0&&arr[j]<arr[j-1];j--){
            swap(arr,j,j-1);
        }
    }
}
private static void swap(int[] arr,int i,int j){
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

2. 直接插入排序和折半插入排序

直接插入排序

思想：每次将一个待排序的元素按照其大小插入到前面已经排好序的子序列中，直到剩余元素全部插入完毕。

算法和上面一样：

void InsertSort(int A[],int n)
{
   int i,j,m;
  for(int i=1;i<n;i++)     //把A[0]看成一个有序序列，将A[1]~A[n-1]往前插
  {
    if(A[i]<A[i-1])   //如果待排元素小于前一个元素，则往前插
    {
      m=A[i];    //用一个变量记录待插元素的值
      for(j=i-1;A[j]>m;--j) //从i-1处往前寻找，对每个元素比较一次都将这个元素后移。当找到A[j]<m,说明j+1就是要插入的位置，直接跳出循环
     {
        A[j+1]=A[j];  //不满足大小关系的元素后移
     }
      A[j+1]=m;  //将待插入元素的值复制到该插入的位置
    }
  }
}

折半插入排序

思想：与直接插入排序相似。区别是直接插入排序是边比较边移动元素，折半插入排序则是将比较和插入的操作分离出来。先通过折半查找找到元素该插入的位置，再统一将该位置及后面的元素后移。
算法：

void InsertSort(int A[],int n)
{
  int i,j,low,high,mid,m;
  for(i=1;i<n;i++)
  {
    m=A[i];
    low=0;high=i-1;
    while(low<=high)  //先比较，寻找位置
    {
      mid=(low+high)/2;
      if(A[mid]>m) high=mid-1;  //查找左半段
      else low=mid+1;          //查找右半段
    }                      //跳出循环时，说明插入的位置在mid，也就是high+1。
    for(j=i-1;j>=high+1;--j)   //后统一移动，腾出位置
    {
       A[j+1]=A[j];
    }                   
      A[high+1]=m;    //拷贝待插入的元素
  }
}