1. 简介

插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法。
在插入排序中，当待排序数组是有序时，是最优的情况，只需当前数跟前一个数比较一下就可以了，这时一共需要比较N- 1次，时间复杂度为O(N)。
在插入排序中，最坏的情况是待排序数组是逆序的，此时需要比较次数最多，总次数记为：1+2+3+…+N-1，所以，插入排序最坏情况下的时间复杂度为O(N^2)。
在插入排序中，插入排序的平均时间复杂度也是 O(n^2)。

2. 原理

实际上是将要排序的数字列表分为有序表和无序表。有序表的数字都是有序的，而且规模逐个变大，从一个数字到列表长度的数字数目；无序表就是列表除去有序表剩下的数字，每次取第一个数字去与有序表中的数字做比较，并插入到有序表中正确的位置，无序表的规模逐个变小，最终全部取出，得到一个完整的有序表。
如下图：
黄色的是有序表，浅蓝色的是无序表。
在这里插入图片描述

3. 代码实现

#include<iostream>
#include<string>
using namespace std;

int main()
{
    int arraysize = 15;
    int array[15] = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};

    for(int i=1;i<arraysize;i++){  
            int value = array[i];  // 取出来的那个数，拿去有序表中比较。
        for(int j=i-1;j>=0;j--){  // 有序表
            if(array[j]>value){
                int index = j+1; 
                array[index] = array[j];  // 如果符合条件，相邻两个数交换位置。
                array[j] = value;
            }
            else{
                break;  
            }

        }

        cout << "第"  << i  << "轮";

        for(int i=0;i<arraysize;i++){
            cout << array[i] << " ";

    }
    cout << '\n';
    }

    cout << "end" << endl;
    return 0;
}