【排序】详解插入排序

一、思想

插入排序是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。具体步骤如下，将数组下标为0的元素视为已经排序的部分，从1开始遍历数组，在遍历的过程中当前元素从当前位置开始在已经排序的部分中寻找到合适的位置并插入，直到遍历完整个数组。

二、图解

图解

初识时遍历指针指向下标为1的元素

此时在已排序部分[0 , i - 1]开始寻找合适的位置进行插入，先将i位置的值进行记录，然后开始定义指针在已排序区间寻找

在j从i-1遍历向0的过程中，拿arr[j]与存储的变量t进行比较，因为前部分都是已排序部分，所有在进行比较时会出现两种情况：1》arr[j] > t 说明此时j位置并不是t要插入的位置，这个时候我们可以让j+1的位置修改为arr[j]，然后j--继续去比较 2》arr[j] < =t， 此时说明j位置就是t要插入的位置，我们可以结束j的遍历然后让j + 1位置的值更改为t

此时i指针继续向后遍历，j依旧指向i-1向0遍历寻找arr[i]也就是t要插入的位置

i再往后遍历，重复上述过程

这个时候arr[j] > t，于是让arr[j+1]=arr[j]

依旧是arr[j] > t，于是让arr[j+1]=arr[j]

接着i++，继续重复这个过程

说明：上述寻找t的插入位置的过程我们也可以通过二分在已排序的区间中寻找到t该插入的位置，在寻找到t要插入的位置后，在插入t之前，我们要先将t要插入的位置到i-1的区间所有的值都后移一位

三、代码实现

C++

void insert_sort(vector<int>& arr) {
    for (int i = 1; i < arr.size(); i++) {
        int j = i - 1, t = arr[i];
        for (j = i - 1; j >= 0; j--) {
            if (arr[j] > t) {
                arr[j + 1] = arr[j];
            } else {
                break;
            }
        }
        arr[j + 1] = t;
    }
}

Java 

    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int j = i - 1, t = arr[i];
            for (j = i - 1; j >= 0; j--) {
                if (arr[j] > t) {
                    arr[j + 1] = arr[j];
                } else {
                    break;
                }
            }
            arr[j  + 1] = t;
        }
    }