插入排序及其优化

今天来重温一遍插入排序，及其对应的优化，插入排序可以说是很重要的一个排序算法了，因为他在最某些情况下可以达到O(n)的复杂度。由此特性可以用来优化其他排序算法，以达到提高速度的效果。

原理：每次将目标元素与 它之前的元素作对比，若比其小，则交换位置，一直到第一个元素位置，如图：

上C++代码(原始版本，只要比目标元素小，则交换位置)：

template<typename T>
void insertionSortOrigin(T arr[], int n) {
    for (int i = 0; i < n; i++) {

        for (int j = i - 1; j >= 0 && arr[j + 1] < arr[j]; j--) {
            std::swap(arr[j + 1], arr[j]);
        }

    }
}

优化版本(不进行交换，只进行下标切换，最终达到只交换一次，除去交换带来的性能损耗)：

template<typename T>
void insertionSort(T arr[], int n) {
    // 首先从第二个元素开始，因为第一个元素本来就是已经确定了的没有可比较元素
    for (int i = 1; i < n; i++) {

        T data = arr[i];
        int j = i - 1;
        for (; j >= 0 && data < arr[j]; j--) {
            // 跟前一个元素比较，如果比他小则切换目标的位置
            arr[j + 1] = arr[j];
        }

        arr[j + 1] = data;

    }
}