总体思路是：先记录每一次要插入的值，插入的值依次与前面插入的值比较大小，直到找到那个值，然后后面的值全部后移空出的位置，就是他的正确位置。循环n次实现排序。

---

#include
     
      void insertvalue(int a[],int n);void main(){    int a[5]= {
    5,9,47,3,4};    printf("排序之前：\n");    for(int i=0; i<5; i++)    {        printf("%d\t",a[i]);    }    insertvalue(a,5);    printf("\n");    printf("排序之后：\n");    for(int i=0; i<5; i++)    {        printf("%d\t",a[i]);    }}void insertvalue(int a[],int n){    int key;    for(int i=1; i
      
       key&&j>=0) //寻找插入位置        {            a[j+1]=a[j];            j--;//与前面的数比较                 }        a[j+1]=key;//最终位置    }}
      
     

最好情况下，正序，总的比较次数为n-1次，记录移动的次数2(n-1)，时间复杂度为O(n)。

最坏情况下，逆序，总的比较次数为(n+2)*(n-1)/2，移动(n+4)(n-1)/2次，时间复杂度O(n^2)。

平均情况下，各种概率相同，总的比较次数为(n+2)*(n-1)/4，移动(n+4)(n-1)/4次，时间复杂度O(n^2)。

当记录基本有序或者待排序记录中较少时，它是最佳排序方法。