什么是直接插入排序

直接插入排序是基础排序的一种，它的思路是：有一个有序部分，一个无序部分，我们每一次拿无序部分的第一个元素对有序部分 从后往前进行比较(默认升序情况)，如果小于则把比较的元素向后移一位 直到大于某个元素 此时把无序元素插入到这个位置。

算法原理

对于数列{9,3,7,2,5,8,1,4}元素进行升序插入排序

初始有序部分 9 无序部分 3 7 2 5 8 1 4

第一趟：3 9 7 2 5 8 1 4，有序 3 9 无序 7 2 5 8 1 4

第二趟：3 7 9 2 5 8 1 4，有序 3 7 9 无序 2 5 8 1 4

第三趟：2 3 7 9 5 8 1 4，有序 2 3 7 9 无序 5 8 1 4

第四趟：2 3 5 7 9 8 1 4，有序 2 3 5 7 9 无序 8 1 4

第五趟：2 3 5 7 8 9 1 4，有序 2 3 5 7 8 9 无序 1 4

第六躺：1 2 3 5 7 8 9 4，有序 1 2 3 5 7 8 9 无序 4

第七趟：1 2 3 4 5 7 8 9，有序 1 2 3 4 5 7 8 9 无序空

可以看出几个问题

1.8 个元素排序 7 趟

2.每次都是让无序部分的第一个元素和有序部分进行从后往前的比较 且比较成功 则有序部分向后移 直到比较不成功则 插入无序元素

3.我们这里排序采用的是有序元素向后移 无序元素插入的方式，比无序元素和有序元素依次交换的时间要少得多这是一个优化点

4.我们在有序部分比较不成功时 直接退出 而不是再继续向前比较，这是个优化点

代码示例

public static void main(String[] args) {    int[] a = {9,3,7,2,5,8,1,4};    int len = a.length;    for (int i=1;i<len;i++){        int j = i-1;        int t = a[i];        System.out.println("第"+(i)+"趟");        while (j>=0){            if (t<a[j]) {                a[j+1]=a[j];            }else {                break;            }            j--;        }        a[++j]=t        for (int k=0;k<len;k++){            System.out.printf("%d ",a[k]);        }        System.out.println();    }}

int t 临时变量 记录无序部分的第一个元素，因为后续有序部分向后移会覆盖这个元素

if 判断中：如果无序元素小于有序元素 有序元素向后移 如果无序元素大于等于有序元素 则说明应该插入到此位置 所以这里直接退出 从后向前比较有序 元素 因为最后 j-- 所以需要++才能插入到空出的位置

结果：

第 1 趟

3 9 7 2 5 8 1 4

第 2 趟

3 7 9 2 5 8 1 4

第 3 趟

2 3 7 9 5 8 1 4

第 4 趟

2 3 5 7 9 8 1 4

第 5 趟

2 3 5 7 8 9 1 4

第 6 趟

1 2 3 5 7 8 9 4

第 7 趟

1 2 3 4 5 7 8 9