排序算法1--（直接插入排序）

已知待排序列r[1...n],先将序列中的第一个记录看成是一个有序的子序列，然后从第二个记录起逐个进行插入，直至整个序列变成关键字非递减有序序列为止。 
具体操作如下：
    （1）查找出r[i]在有序序列r[1...i-1]中的插入位置k;
    （2）将r[k...i-1]中所有元素全部后移一个位置；
    （3）将r[i]复制到r[k],则原r[1...r-1]的有序序列变成了一个r[1...i]的有序序列。

动图演示：直接插入排序动图

//insertion sort
1 for i ← 2 to length[A]
2   do key ← A[i]
3         //insert A[j] into the sorted sequence A[1 ... j - 1]
4         j ← i - 1
5         while j > 0 and A[j] > key
6            do A[j + 1] ← A[j]
7                  j ← j - 1
8         A[j + 1] ← key

void InsertSort(ElemType A[],int n){
    int i,j;
    for(i = 2;i <= n;i++){                   //依次将A[2]~A[n]插入到前面已排序序列
        if(A[i].key < A[i-1].key){           //若A[i]的关键码小于其前驱，需将A[i]插入有序表
            A[0] = A[i];                     //复制为哨兵，A[0]不存放元素
            for(j=i-1;A[0].key 
三、复杂度分析 
3.1 空间复杂度 
仅使用了常数个辅助单元，因而空间复杂度为O(1)
 
3.2 时间复杂度 
①最好情况下，表中元素已经有序，此时每插入一个元素，都只需比较一次而不用移动元素，因而时间复杂度为O(n);
 ②最坏情况下，表中元素顺序刚好与排序结果中元素顺序相反时，总的比较次数达到最大，为 
     
      
       
        
         
          ∑
         
         
          
           i
          
          
           =
          
          
           2
          
         
         
          n
         
        
        
         i
        
       
       
        sum_{i=2}^ni
       
      
     i=2∑n​i 总的移动次数也达到最大，为
     
      
       
        
         
          ∑
         
         
          
           i
          
          
           =
          
          
           2
          
         
         
          n
         
        
        
         (
        
        
         i
        
        
         +
        
        
         1
        
        
         )
        
       
       
         sum_{i=2}^n(i+1)
       
      
     i=2∑n​(i+1);
 ③平均情况下，考虑待排序表中元素是随机的，此时可以取上述最好与最坏情况的平均值作为平均情况下的时间复杂度，总的比较次数与总的移动次数均约为n²/4。由此，直接插入排序算法的时间复杂度为O(n²)
 
3.3 稳定性 
由于每次插入元素时总是从后向前先比较再移动，所以不会出现相对位置发生变化的情况，即直接插入排序是一个稳定的排序方法。
 
3.4 适用性 
直接插入排序适用于顺序存储和链式存储的线性表。为链式存储时，可以从前往后查找指定元素的位置。
 大部分排序算法都仅适用于顺序存储的线性表。