/* 

 

二分插入法 */

void HalfInsertSort(int a[], int len)
{
     int i, j,temp;
     int low, high, mid;
     for (i=1; i<len; i++)
     {
          temp = a[i];/* 

 

保存但前元素 */

          low = 0;
          high = i-1;
          while (low <= high) /* 在 a[low...high]

 

中折半查找有序插入的位置 */

          {
               mid = (low + high) / 2; /* 

 

找到中间元素 */

               if (a[mid] > temp)  /* 如果中间元素比但前元素大，当前元素要插入到中间

 

元素的左侧 */
               {
                high = mid-1;
               }
               else    /* 

 

如果中间元素比当前元素小，但前元素要插入到中间元素的右侧 */

               {
                low = mid+1;
               }
          }       /* 找到当前元素的位置，在 low 和 high

 

之间 */

          for (j=i-1; j>high; j--)/* 

 

元素后移 */

          {
           a[j+1] = a[j];
          }
          a[high+1] = temp; /* 

 

插入 */

     }
}

 

三.直接插入法

/*直接插入法*/

void InsertionSort(int input[],int len) 
{
     int i,j,temp;
     for (i = 1; i < len; i++) 
     {
          temp = input[i];  /* 

 

操作当前元素，先保存在其它变量中 */

          for (j = i - 1;j>-1&&input[j] > temp ; j--) /* 从当前元素的上一个元素开始查找