算法基础——插入排序

插入排序的原理类似于打扑克牌，通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到响应位置并插入。

将待排序序列的第一个元素做为有序序列，吧第二个元素到最后一个元素当成未排序序列

从头到尾一次扫描未排序序列，将扫面的每个元素插入有序序列的适当位置

void insertion_sort(vector &arr) {
    for (int i = 1; i <= arr.size(); i++) {
        int temp = arr[i];
        int j = i - 1;
        while ((j >= 1) && (temp < arr[j])) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
}