直接插入排序简介
直接插入排序最适合的场景如下：对于一个有序的序列来说，当我们将另外一个数字添加到该有序序列中的时候，依次从该序列的右边开始比较，如果要插入的值小于序列中当前位置的值，那么序列中该位置的值后移一位，以此类推，直到找到第一个不大于要插入的数值为止，最后将要插入的这个数值插入到合适位置，这就完成了一次直接插入排序的过程。
对于无序数列来说，我们知道要插入的第i个数据之前的前i-1个数据都是有序，那么，我们就可以应用直接插入排序来对数字序列进行排序。
直接插入排序代码示例
private static void directInsertSort(int[] array) {
if (array == null || array.length == 0) {
return;
}
int length = array.length;
for (int i = 1; i < length; i++) {
int temp = array[i];
int j = i - 1;
//遍历前j个数字，判断是否需要右移
while (j >= 0 && array[j] > temp) {
array[j + 1] = array[j];
--j;
}
//找到了插入位置，进行插入，完成一遍直接插入过程
array[j + 1] = temp;
}
}直接插入排序性能分析
最好情况下,排序前对象已经按照要求的有序。比较次数(KCN):n−1 ; 移动次数(RMN):为0。则对应的时间复杂度为O(n)。
最坏情况下,排序前对象为要求的顺序的反序。第i趟时第i个对象必须与前面i个对象都做排序码比较,并且每做1次比较就要做1次数据移动。则对应的时间复杂度为O(n^2)。
如果排序记录是随机的，那么根据概率相同的原则，直接插入排序的平均时间复杂度为O(n^2)。
空间复杂度：O（1）；
直接插入排序属于稳定的排序算法。