<--个人成长笔记系列-->解析排序算法之插入排序

JAVA知识点：

    （掌握）插入排序：

        1、是稳定排序；

        2.1、最坏时间复杂度是O(n^2)；需要进行n-1轮，每一轮最坏情况下，需要比较1次、2次、3次...一直到n-1次

        2.2、最好时间复杂度是O(n)；本身有序的情况下，轮数不变，但每一轮只比较一次就跳出循环，所以最好情况下时间复杂度是On

        3、空间复杂度是O(1)，因为插入排序是在原地排序，没有引入额外的数据结构；

        4、和冒泡排序的区别：插入排序的优势在于元素交换方式。冒泡排序每次交换需要三步，插入排序平均每次交换只要一步

---

public static void sort(int[] array){

    for(int i=1;i<array.length;i++){

        int insertValue =array[i];

        int j=i-1;

        //从右向左比较元素的同时，进行元素复制

        for(; j>=0&&insertValue<array[j]; j--){

            array[j+1]=array[j];

        }

        //insertValue的值插入适当位置

        array[j+1]=insertValue;

    }

}

public static void main(String[] args) {

    int array[]={12,1,3,46,5,0,-3,12,35,16};

    sort(array);

    System.out.println(Arrays.toString(array));

}

---

    （掌握）源码断点：比较Arrays.sort()和Collections.sort()方法

        记录链接：https://juejin.im/post/5d513925e51d4561cf15df99