详解直接插入排序算法
前言
在玩扑克牌的时候，我们抽到一张牌的时候，都是将它插入到当前手中牌的合适位置的。 如下图：
（上图来自算法导论） 直接插入排序也是这样的思想。
基本思想
插入排序的思想是： 将待排序序列分成两个序列，前面的序列保持有序，依次选取后面的序列的元素，在前面的序列中进行插入。 初始时，有序序列的长度为1。
例子
给定序列 [9 , 20 , 13 , 20 , 12 ] 。 初始状态如下：
初始状态
分成两个序列如下：
初始的两个序列
定义两个变量 val 和 index。其中val表示后面序列中待插入的元素，index表示前面序列中插入的索引。
第一次插入 将 val初始化为 arr[1],即20; 将Index初始化为当前val值的前一个元素的索引，即0;
此时 arr[index] < val 不用移动，index-- 后将变为负数，退出循环。 第一次插入结束。 变成如下状态：
第一趟插入状态1
第二次插入 将 val初始化为 arr[2],即10; 将Index初始化为当前val值的前一个元素的索引，即1;
第二趟插入初始状态
此时 arr[index] > val 并不是合适的插入位置，将index代表的元素向后移动；
第二趟插入状态1
index--;
此时 arr[index] < val 找到了插入位置，即 index + 1; 退出当前循环； 将 arr[index+1] 赋值为val； 得到如下状态图：
第二趟插入状态3
第三次插入 将 val初始化为 arr[3],即13; 将Index初始化为当前val值的前一个元素的索引，即2;
此时 arr[index] > val 并不是合适的插入位置，将index代表的元素向后移动；
得到如下状态图：
index--;
第三趟插入状态2
此时 arr[index] < val 找到了插入位置，即 index + 1; 退出当前循环； 将 arr[index+1] 赋值为val； 得到如下状态图：
第三趟插入状态3
第四趟插入
第四趟插入1
第四趟插入2
代码
先定义变量；
int value;//待插入元素
int index;//初始值为待插入元素前一个元素的索引
由算法思想和例子解释，写成最终代码如下：
import java.lang.reflect.Array;
import java.util.Arrays;
public class Solution {
public static void main(String[] args) {
InsertSort(new int[] { 9 ,20 , 10, 13 , 12});
}
public static void InsertSort(int [] arr){
int value;//待插入元素
int index;//初始值为待插入元素前一个元素的索引
for(int i= 1 ; i< arr.length;i++){
//i从第二个元素开始，默认第一个元素是有序的
//循环条件是小于数组长度，因为也要将最后一个元素插入到前面的序列
value = arr[i];
index = i - 1;//初始为前一个元素
while(index >=0 && value < arr[index]){
//需要保证index合法
//每当前面的元素比待插入元素大，就向后移动
arr[index + 1] = arr[index];
//不用怕覆盖，因为value保存着待插入的值
index--;
}
//当退出循环，表明已经找到了待插入位置，即index + 1
arr[index + 1] = value;
}
System.out.println(Arrays.toString(arr));
}
}
时间复杂度
在排序前元素已经是按需求有序了，每趟只需与前面的有序元素序列的最后一个元素进行比较，总的排序码比较次数为n-1，元素移动次数为0。时间复杂度为; 而在最差的情况下，及第i趟时第i个元素必须与前面i个元素都做排序码的比较，并且每做一次就叫就要做一次数据移动，此时的时间复杂度为 ； 所以直接插入排序的时间复杂度为。
稳定性
插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。如果碰见一个和插入元素相等的，那么将会把待插入元素放在相等元素的后面。所以，相等元素的相对的前后顺序没有改变，所以插入排序是稳定的。
欢迎关注
欢迎大家的关注
扫描下方的二维码或者微信搜一搜即可关注我的微信公众号：code随笔