(有个猜测，方便记忆：一般来说，若存在不相邻元素间交换，则很可能是不稳定的排序。)


思想：如下图所示，每次选择一个元素K插入到之前已排好序的部分A[1…i]中，插入过程中K依次由后向前与A[1…i]中的元素进行比较。若发现发现A[x]>=K,则将K插入到A[x]的后面，插入前需要移动元素。
插入排序是稳定的。

#include <iostream>
using namespace std;
void insertsort(int a[],int n)
{
    int i,j;
    for (i=1; i<n; i++)   //对0...n-1按递增有序进行直接插入排序
    {
        int t=a[i];
        j=i-1;   //从右往左在有序区a[0..i-1]找a[i]的插入位置
        while(j>=0&&t<a[j])
        {
            a[j+1]=a[j];  //将值大的后移
            j--;
        }
        a[j+1]=t;  //在j+1处插入a[i]
    }
}
int main()
{
    int a[10],n,i;
    cin>>n;
    for (i=0; i<n; i++)
        cin>>a[i];
    insertsort(a,n);
    for (i=0; i<n; i++)
    {
        cout<<a[i];
    }
}

插入排序