直接插入排序

算法思想： 初始时，认为第一个元素是已经排好序的有序序列,从数组的第二个元素开始，向前进行比较，依次递增，每次只要前一个元素大于当前比较元素，就让该元素向后唯一一位，最终导致，一位空位，直接将元素插入即可；

时间复杂度分析： 因为每次从1开始(默认数组下标从0开始)，所以每次比较趟数位n-1次，易得比较次数与数组本身的顺序有关。
最好情况：如果数组递增有序，则每次只需比较1次就会结束循环，故比较次数为n-1；即O(n)。
最坏情况：如果本身数组逆序，每次比较都需要将前面所有元素比较一次，故比较次数为 1+2+3+…+n-1=(n(n-1))/2次; 即O(n^2)。
平均情况：在平均情况下，第i个元素需要与前面有序序列中的大约i/2个元素进行比较，才能找到合适的插入位置，1/2(2+3+4+…+n) 故O(n^2)

空间复杂度：没有借助辅助数组，故为O(1);

稳定性： 稳定 ，依次向前比较，只 > 才会执行向后位移，故相同元素的相对位置不会改变。

样例

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10010;
int q[N], n;

void insert_sort() 
{
    for(int i=1;i<n;i++) //从1开始，依次递增
    {
        int x=q[i];  //记录当前要插入的数据
        int j=i;  //利用下标 j 从当前元素向前进行比较
        while(j && q[j-1]>x) //当 j > 0 (即 向前遍历的的边界) 并且 当前比较的元素大于我们要插入的元素时，循环执行
        {
            q[j]=q[j-1];  //使比 插入数据 小的 被比较元素向后移动一位 
            j--; // 使得指针向前递增
        }
        q[j]=x; //最后会导致 该插入的位置空出，直接插入赋值即可
    }
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++) cin >> q[i];

    insert_sort();

    for(int i=0;i<n;i++) cout << q[i] << ' ';
    return 0;
}