直接插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。

第一种程序：

1. void InsertSort1(int arr[] , int n)   
2. {  
3.     for(int i=1;i<n;i++)//循环从第二个数组元素开始，因为arr[0]作为最初已排序部分   
4.     {  
5.         int temp=arr[i];//temp标记为未排序第一个元素   
6.         int j=i-1;  
7.         while (j>=0 && arr[j]>temp)//将temp与已排序元素从大到小比较，寻找temp应插入的位  
8.         {   
9.             arr[j+1]=arr[j];    //比temp大则向后移动
10.             j--;   
11.         }   
12.         arr[j+1]=temp;   
13.     }   
14. }   

1. void Insertsort2(int a[], int n)  
2. {  
3.     int i, j;  
4.     for (i = 1; i < n; i++)  
5.         if (a[i] < a[i - 1])  
6.         {  
7.             int temp = a[i];  
8.             for (j = i - 1; j >= 0 && a[j] > temp; j--)  
9.                 a[j + 1] = a[j];  
10.             a[j + 1] = temp;  
11.         }  
12. }  

详解直接插入排序