[数据结构与算法]插入排序学习笔记

12.31

令i从2到n枚举，进行n-1趟操作。假设某一趟时，序列A的前i-1个元素已经有序，而i到n还未有序，那么将在1到i-1范围内寻找某个位置j此时原前i-1个序列向后移一个位置变为i。那么此时由原先的前i-1个元素有序变为前i个元素有序.

插入排序是将插入元素一个个插入初始有序部分的过程，而插入位置的选择遵循了使插入后仍保持有序的原则，具体做法一般是从后往前枚举已有序部分来确定插入位置。

代码如下：

int A[maxn],n;
void insertSort()
{
    for(int i=2;i<+n;i++)
    {
        int temp=A[i];
        j=i;
        while(j>1&&temp<A[j-1]
        {
            A[j]=A[j-1];
            j--;
        }
        A[j]=temp;
    }
}