02.插入排序

目录介绍

1.基本思想
2.排序过程
3.代码实现
4.如何优化
5.复杂度
6.使用场景

1.基本思想

在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
插入排序非常类似于整扑克牌顺序。

2.排序过程

从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素(已排序)大于新元素，将该元素移到下一位置；
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置中，重复步骤2。
image

3.代码实现

代码如下

public static void InsertSort(int[] arr) {
    //直接插入排序
    for (int i = 1; i < arr.length; i++) {
        //待插入元素
        int temp = arr[i];
        int j;
        for (j = i - 1; j >= 0; j--) {
            //将大于temp的往后移动一位
            if (arr[j] > temp) {
                arr[j + 1] = arr[j];
            } else {
                break;
            }
        }
        //插入进来
        arr[j + 1] = temp;
    }
    for(int i=0;i<arr.length;i++){
        System.out.println("yc1-----" +arr[i]);
    }
}