直接插入排序

基本思想：假设待排序的记录存放在数组R[1..n]中。初始时，R[1]自成1个有序区，无序区为R[2..n]。从i=2起直至i=n为止，依次将R[i]插入当前的有序区R[1..i-1]中，生成含n个记录的有序区。

代码实现：

#include<stdio.h>
#include<iostream>
using namespace std;
int n;
void InsertSort(int a[])
{
    int i,j;
    for(i=2;i<=n;i++)
    {
        if(a[i]<a[i-1])
        {
            a[0]=a[i];    //哨兵
            a[i]=a[i-1];
            for(j=i-2;a[0]<a[j];j--)
                a[j+1]=a[j];        //后移
            a[j+1]=a[0];
        }
    }
}

int main ()
{
    int a[100],i;
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>a[i];
    InsertSort(a);
    for(i=1;i<=n;i++)
        cout<<a[i]<<" ";
    return 0;
}

直接插入排序