插入排序

1. 基本思想

就像整理扑克牌时我们一般都是将后面的牌一张张地插入到前面有序的部分中适当的位置中一样，插入排序每次将无需部分的第一个元素每次向前面移动一个位置，直到它处于有序部分中的适当位置时为止。

2. 代码实现

void insertionSort(vector<int>& vec){
    for (int i = 1; i < vec.size(); i++){
        for (int j = i; j >= 1 && vec[j - 1] > vec[j]; j--)
            swap(vec[j - 1], vec[j]);
    }
}

3.效率分析

• 在数组有序的情况下时间复杂度为 O(n)，数组逆序情况下交换次数和比较次数都为 1 + ... + (n - 1), 此时时间复杂度为 O(n2)
• 插入排序是稳定的