插入排序是稳定的排序，平均情况和最坏情况的算法复杂度为O(n^2)，最好情况为O(n)；空间复杂度为：O(1)。
[cpp]
#include
void InsertSort(int a[],int n)
{
int i,j,rc;
for(i=1;i
if(a[i-1]>a[i])
{
rc=a[i];
j=i;
while(j-1>=0 && rc
a[j]=a[j-1];
j--;
} www.2cto.com
a[j]=rc;
}
}
}
void main()
{
int a[]={49,38,65,97,76,13,27,49};
int n=sizeof(a)/sizeof(a[0]);
InsertSort(a,n);
for(int i=0;i
printf("%d\n",a[i]);
}
}