【面试：基础题04：插入排序】

01.简介

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

02.算法步骤

对于数列{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.我们在有序部分比较不成功时 直接退出 而不是再继续向前比较，这是个优化点

03.代码

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;// 因为最后j-- 所以需要++才能插入到空出的位置
        for (int k=0;k<len;k++){
            System.out.printf("%d ",a[k]);
        }
        System.out.println();
    }
}

结果

第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

04.插入排序与选择排序与冒泡排序比较

相同点:

1.插入排序与选择排序都是被分为有序部分和无序部分，只不过选择排序是记录最小值下标最后进行交换把无序元素放入有序元素。而插入排序则是把无序部分的一个元素依次从后往前对有序部分的元素进行比较直到比较不成功则插入。

2.和冒泡排序一样插入排序在顺序情况下时间复杂度很优秀，在完全顺序的情况下 插入排序与冒泡排序的时间复杂度都可以达到O(n)水平。

3.插入排序和冒泡排序都是稳定排序。

不同点:

1.插入排序的时间复杂度优于选择排序与冒泡排序，优于他们的原因在于插入排序是移动元素而不是交换元素，交换元素部分的代码 进行了三次移动 所以一次交换等于三次移动。

2.插入排序是稳定排序而选择排序不是稳定排序。