插入排序算法 及其优化与性能 C++代码实现

• • 复习梗概
  • 插入排序算法思想
  • 插入排序时间复杂度与特性（多少，与什么有关？）
  • 插入排序基础版
  • 插入排序2nd优化版（优化了哪里？）
  • 插入排序3rd优化版（优化了哪里？）

想象插入排序就是两只手，一只手里的牌是有序的，一只是无序的，每次把无序的手里的牌的第一张，与有序的牌逐个比较，插入有序牌堆的合适位置

1. 插入排序的时间复杂度： 与数组中的逆序对有关
2. 逆序对：比如想要递增的数组【0，8，9，1】这里【8，1】【9，1】都是逆序对
3. 最坏时间复杂度：O（n2）（输入数组完全逆序），最好时间复杂度O（n）（输入数组已经有序），平均时间复杂度O（n2），空间复杂度O（1）
4. 属于原地稳定排序算法
5. 排序算法在逆序对特别少的数组中效率很高，甚至可能比O（nlogn）级别的堆排序和快速排序还快
   

void insertionSort1th(vector &array) //这里以数组左侧作为有序的那一边
{
    // chaosBeginIndex：未排序序列的起始元素下标
    // insertEIndex：拿去插入有序序列的那个元素的下标，就是未排序序列的起始元素，但随着交换位置，下标会改变
    for (int chaosBeginIndex = 1; chaosBeginIndex < array.size(); chaosBeginIndex++) 
    //外循环控制从第二个元素开始插入到有序序列里，直到最后一个元素
    {
        for (int insertEIndex = chaosBeginIndex; insertEIndex > 0; insertEIndex--)
        //内循环控制从未排序序列的首元素开始，逐渐与有序序列元素比较和交换位置，找到有序序列中的合适位置
        {
            if (array[insertEIndex] < array[insertEIndex - 1])
            {
                int temp = array[insertEIndex];
                array[insertEIndex] = array[insertEIndex - 1];
                array[insertEIndex - 1] = temp;
            }
            else
            {
                break;
            }
        }
        vectorPrint(array);
    }
}

void insertionSort1thRe(vector &array) //这里以数组右侧作为有序的那一边
{
    for (int chaosBeginIndex = array.size() - 1 - 1; chaosBeginIndex >= 0; chaosBeginIndex--)
    {
        for (int insertEIndex = chaosBeginIndex; insertEIndex < array.size() - 1; insertEIndex++)
        {
            if (array[insertEIndex] > array[insertEIndex + 1])
            {
                int temp = array[insertEIndex];
                array[insertEIndex] = array[insertEIndex + 1];
                array[insertEIndex + 1] = temp;
            }
            else
            {
                break;
            }
        }
        vectorPrint(array);
    }
}

输入数组：
6 9 3 1 2 0 8 29 15 11 10
插入排序基础版
6 9 3 1 2 0 8 29 15 11 10
3 6 9 1 2 0 8 29 15 11 10
1 3 6 9 2 0 8 29 15 11 10
1 2 3 6 9 0 8 29 15 11 10
0 1 2 3 6 9 8 29 15 11 10
0 1 2 3 6 8 9 29 15 11 10
0 1 2 3 6 8 9 29 15 11 10
0 1 2 3 6 8 9 15 29 11 10
0 1 2 3 6 8 9 11 15 29 10
0 1 2 3 6 8 9 10 11 15 29
算法用时：（微秒）
[AlgoTime: 10002 us]
输入数组：
6 9 3 1 2 0 8 29 15 11 10
插入排序基础版（换一个方向）
6 9 3 1 2 0 8 29 15 10 11
6 9 3 1 2 0 8 29 10 11 15
6 9 3 1 2 0 8 10 11 15 29
6 9 3 1 2 0 8 10 11 15 29
6 9 3 1 2 0 8 10 11 15 29
6 9 3 1 0 2 8 10 11 15 29 
6 9 3 0 1 2 8 10 11 15 29
6 9 0 1 2 3 8 10 11 15 29
6 0 1 2 3 8 9 10 11 15 29
0 1 2 3 6 8 9 10 11 15 29
算法用时：（微秒）
[AlgoTime: 10003 us]

1. 思路是将交换改为了挪动
2. 就是把左边比我大的元素都要跟我交换，换成了左边比我大的元素都要往右移
3. 流程图来自腾讯课堂-恋上数据结构与算法第二季-李明杰老师
   

//插入排序的第一次优化，就是把不断的交换位置，改成了找到位置后插入数组，数组元素后移覆盖
//就是把左边比我大的元素都要跟我交换，换成了左边比我大的元素都要往右移
void insertionSort2nd(vector &array) //这里以数组左侧作为有序的那一边
{
    for (int chaosBeginIndex = 1; chaosBeginIndex < array.size(); chaosBeginIndex++)
    {
        int insertENum = array[chaosBeginIndex]; //记录插入元素的元素内容，因为后面原本位置会被覆盖
        int rightEIndex = chaosBeginIndex;       //记录正确的插入位置，初始值就是被插入元素的原本位置（未排序序列的第一个元素位置）

        while (rightEIndex > 0)   //不断比较插入元素与有序队列元素，找到合适插入位置，用rightEIndex记录
        {
            if (insertENum< array[rightEIndex-1])
            {
                array[rightEIndex] = array[rightEIndex - 1];//妙啊，找合适位置的同时就顺便把元素后移了
                rightEIndex = rightEIndex - 1;
            }
            else
            {
                break;
            }
        }

        array[rightEIndex] = insertENum; //插入到空出来的合适位置中

        vectorPrint(array);
    }
}

输入数组：
6 9 3 1 2 0 8 29 15 11 10
插入排序第一次优化版
6 9 3 1 2 0 8 29 15 11 10
3 6 9 1 2 0 8 29 15 11 10
1 3 6 9 2 0 8 29 15 11 10
1 2 3 6 9 0 8 29 15 11 10
0 1 2 3 6 9 8 29 15 11 10
0 1 2 3 6 8 9 29 15 11 10
0 1 2 3 6 8 9 29 15 11 10
0 1 2 3 6 8 9 15 29 11 10
0 1 2 3 6 8 9 11 15 29 10 
0 1 2 3 6 8 9 10 11 15 29
算法用时：（微秒）
[AlgoTime: 11002 us]