插入排序-insertSort

1、基本思路

? ? ? ? 与冒泡排序和插入排序一样，也是两个元素比较；不过不同的是，在插入排序中，数组的左边会维护一个有序数组，这个数组刚开始时只有一个元素，即数组第一个元素，后续将拿有序数组后的第一个元素（也就是标记元素）去和有序数组进行比较，比较的顺序是有序数组的倒序。

? ? ? ? 具体过程是，先将标记元素的值存储起来，然后用标记元素的值和有序数组的最后一个元素比较，如果有序数组的值大于标记数组，则需要将有序数组的比较值赋值到标记元素的位置，随后继续比较有序数组的其他值，当有序数组的值没有了，或者遇到一个值标记值小，那么此时就需要停下来了，因为已经找到了标记值的位置，此时只需要将标记元素的值放到此处即可。

? ? ? ? 时间复杂度为O(N^2)，但是相比冒泡排序和选择排序，速度更快。

2、代码实现

public class InsertSort {
    public static void main(String[] args) {
        int[] arr = new int[]{33, 24, 4, 28, 95, 63, 86, 77};
        insertSort(arr);
        for (int i = 0; i < arr.length; i++){
            System.out.print(arr[i] + " ");
        }
    }

    private static void insertSort(int[] arr) {
        int length = arr.length;
        int mark;
        // 从第二个元素开始，是因为把第一个元素当成已经排好序的数组
        for (int i = 1; i < length; i++ ){
            //把标记的值存储下来，后续元素移动时可以直接覆盖标记元素
            int temp = arr[i];
            //从标记点的前一个元素开始对比
            mark = i;
            while(mark > 0 && arr[mark -1 ] > temp){
                //将标记点的元素和前一个元素交换
                arr[mark] = arr[mark - 1];
                //交换之后要更新标记元素的位置，虽然没有将标记元素放到该位置
                --mark;
            }
            //将标记元素的值放入左边的数组中，左边的数组依然是一个有序数组
            arr[mark] = temp;
        }
    }
}

3、动态过程?

查看算法的动态演示过程