插入排序（上）     

  基本思想：每次将一个待排序的的元素，按其关键字大小插入到已经排好序的子表的适当位置，直到全部元素插完为止。
直接插入排序 
  简写排序思路：

     假设待排序的元素存放在R[0.....n-1]中，在排序过程中，将R划分为两个区间，分别为R[0.....i-1]和R[i....n-1](刚开始时i=1，有序区只有R[0]一个元素),

   其中，前一个子区间即是一个已经排好序的子区间，即有序区，后一个子区间则是一个待排序的无序区。

   直接插入排序的操作即是：将当前无序区的开头元素R[i](1<=i<=n-1)插入到有序区R[0....i-1]中的适当位置上，使插入元素后的R[0....i]变为新的有序区。

   每趟操作仅使有序曲增加一个元素。(仅考虑在正序排列下的情况，反序类似（正序及从小到大排列））。

   算法代码：

 1 void InsertSort(ResType R[],int n)
 2    {     
 3         int i,j;
 4         RecType tmp;
 5         for(i=1;i<n;i++)
 6          {
 7                 tmp =R[i];
 8               j=i-1;//从左向右在有序区R[0....i-1]中找到R[i]的插入位置
 9                while (j>=0 && tmp.key<R[j].key)
10                  {
11                       R[j+1]=R[j];//将关键字大于R[i].key的元素后移
12                       j--;
13                       }
14                   R(j+1)=tmp;//在j+1处插入R[i]
15             }
16          }

      算法分析： 

    从示例代码中可知，直接插入排序由两重循环组成，对于具有N个元素的的表，外循环要进行N-1次排序，在每趟排序中，仅当待插入的元素R[i].key>=R[i-1].key

  （即大于等于R[0.....i-1]中的所有关键字时，才无需进入内循环。在正序排序中，每一趟排序的元素仅需进行一趟关键字比较，所以不会执行R[j+1]=R[j], 此时， 

    元素移动次数为2（tmp=R[i]与R[j+1]=tmp各算一次)。类似的，反序排列情况则依此推导。