theory

原理讲解来源于文章 https://www.runoob.com/data-structures/insertion-sort.html

1、概念及其介绍

插入排序(InsertionSort)，一般也被称为直接插入排序。

对于少量元素的排序，它是一个有效的算法。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增 1 的有序表

。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。

2、适用说明

插入排序的平均时间复杂度也是 O(n^2)，空间复杂度为常数阶 O(1)，具体时间复杂度和数组的有序性也是有关联的。

插入排序中，当待排序数组是有序时，是最优的情况，只需当前数跟前一个数比较一下就可以了，这时一共需要比较 N-1 次，时间复杂度为 O(N)。最坏的情况是待排序数组是逆序的，此时需要比较次数最多，最坏的情况是 O(n^2)。

3、过程图示

假设前面 n-1(其中 n>=2)个数已经是排好顺序的，现将第 n 个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。

按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序。

从小到大的插入排序整个过程如图示：

第一轮：从第二位置的 6 开始比较，比前面 7 小，交换位置。

第二轮：第三位置的 9 比前一位置的 7 大，无需交换位置。

第三轮：第四位置的 3 比前一位置的 9 小交换位置，依次往前比较。

第四轮：第五位置的 1 比前一位置的 9 小，交换位置，再依次往前比较。

......

就这样依次比较到最后一个元素。

code

/******************************************
 * @Author       : 鱼香肉丝没有鱼
 * @Date         : 2021-10-28 11:06:13
 * @LastEditors  : 鱼香肉丝没有鱼
 * @LastEditTime : 2021-11-18 07:02:56
 ******************************************/

#include <iostream>
using namespace std;

int main()
{
    int num[12] = {23, 45, 17, 11, 13, 89, 72, 26, 3, 17, 11, 13};
    int n = 12;
    int tmp = 0;
    int i, j;
    for(i = 1; i < n; i++) {  //从第2个元素开始每次都要和他前面的进行比较
        j = i;
        tmp = num[i];
        while(j && num[j - 1] > tmp) {  //只要num[j-1]<tmp就终止循环，因为前面的是有序的，也一定是<，不用再比较了
            num[j] = num[j - 1];  //往后挪位置，腾出位置让tmp插入
            j--;
        }
        num[j] = tmp;
    }
    cout << "排序后的数组为：" << endl;
    for(int i = 0; i < n; i++)
        cout << num[i] << ' ';
    cout << endl;

    return 0;
}

output

排序后的数组为：
3 11 11 13 13 17 17 23 26 45 72 89

这是运行过程，中间有几帧按快了，没显示变量，不过不影响

小小的改进

• 每一次while循环中我们都需要判断j是否大于0，防止越界操作，那么我们现在不使用0这个位置，把0这个位置设置为哨兵位。
• 代码：

/******************************************
 * @Author       : 鱼香肉丝没有鱼
 * @Date         : 2021-10-28 11:06:13
 * @LastEditors  : 鱼香肉丝没有鱼
 * @LastEditTime : 2021-11-18 07:02:56
 ******************************************/

#include <iostream>
using namespace std;

int main()
{
    int num[13] = {-999,23, 45, 17, 11, 13, 89, 72, 26, 3, 17, 11, 13};
    int n = 13;
    int tmp = 0;
    int i, j;
    for(i = 1; i < n; i++) {  //从第2个元素开始每次都要和他前面的进行比较
        j = i;
        tmp = num[i];
        num[0] = tmp;//设置哨兵位，运行到这个一定会停止，避免每一次都判断j的值
        while(num[j - 1] > tmp) {  //只要num[j-1]<tmp就终止循环，因为前面的是有序的，也一定是<，不用再比较了
            num[j] = num[j - 1];  //往后挪位置，腾出位置让tmp插入
            j--;
        }
        num[j] = tmp;
    }
    cout << "排序后的数组为：" << endl;
    for(int i = 1; i < n; i++)
        cout << num[i] << ' ';
    cout << endl;

    return 0;
}

输出：

排序后的数组为：
3 11 11 13 13 17 17 23 26 
45 72 89 

<2> 递归版本

/*
 * @Author: 鱼香肉丝没有鱼
 * @Date: 2021-11-13 16:17:51
 * @Last Modified by: 鱼香肉丝没有鱼
 * @Last Modified time: 2021-11-13 16:40:30
 */

#include <iostream>
using namespace std;

int num[] = {23, 45, 17, 11, 13, 89, 72, 26, 3, 17, 11, 13};

void rec_insertion_sort(int n)
{
    if(n <= 1)  //到达第2个元素的时候停止，因为还要和前面的一个比较
        return;
    rec_insertion_sort(n - 1);

    int current_end = num[n - 1];
    int i = n - 2;  //从前面一个开始

    // 注意这里是&&，用current_end保存好最后一个位置的值，然后往前和每一个元素两两比较，
    // 只要num[i]>current_end,直接让num[i+1]=num[i],覆盖在上面;不用担心数据丢失
    // 一旦遇到num[i]<current_end;就可以退出循环，因为递归是从最前面开始处理的，前面都是有序的
    // 如果大于当前这个数，那么再往前肯定也是大于前面的数的
    while(i >= 0 && num[i] > current_end) {
        //直接把num[i]的值放到i+1(他的后面)的位置上，不需要交换（减少基础操作)
        num[i + 1] = num[i];
        i--;
        // num[i+1] = num[i--];
    }
    num[++i] = current_end;  //退出循环的时候i有减了1，所以要自增，
}

int main()
{
    int n = sizeof(num) / sizeof(num[0]);
    rec_insertion_sort(n);

    cout << "排序后的数组为：" << endl;
    for(int i = 0; i < n; i++)
        cout << num[i] << ' ';
    cout << endl;

    return 0;
}
//注意一下第30行喔注释的代码，如果那样写的话是错误的

output

排序后的数组为：
3 11 11 13 13 17 17 23 26 45 72 89

summary

1. 插入排序是稳定的排序
2. 时间复杂度 O(n²)
3. 非递归其实就相当于直接进入了递归的最底层开始执行，所以大部分的递归都可以写成迭代版本嘛