插入排序

1. 插入排序
   • 插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
2. 算法描述

   • 把待排序的数组分成已排序和未排序两部分，初始的时候把第一个元素认为是已排好序的。

   • 从第二个元素开始，在已排好序的子数组中寻找到该元素合适的位置并插入该位置。

   • 重复上述过程直到最后一个元素被插入有序子数组中。

3. 动图演示

    

4. 代码实现

   public static void insertsort(int arr[]){                
           for(int i = 1;i < arr.length; i ++){
               if(arr[i] < arr[i-1]){//注意[0,i-1]都是有序的。如果待插入元素比arr[i-1]还大则无需再与[i-1]前面的元素进行比较了，反之则进入if语句
                   int temp = arr[i];
                   int j;
                   for(j = i-1; j >= 0 && arr[j] > temp; j --){                
                           arr[j+1] = arr[j];//把比temp大或相等的元素全部往后移动一个位置            
                   }
                   arr[j+1] = temp;//把待排序的元素temp插入腾出位置的(j+1)
               }            
           }
           
       }

5. 算法分析
   • 时间复杂度

     • 最佳情况：T(n) = O(n)

     • 最坏情况：T(n) = O(n2)

     • 平均情况：T(n) = O(n2)

   • 空间复杂度：O(1)
6. 适用场景
   • 插入排序由于O( n2 )的复杂度，在数组较大的时候不适用。但是，在数据比较少的时候，是一个不错的选择，一般做为快速排序的扩充。例如，在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充，用于少量元素的排序。又如，在JDK 7 java.util.Arrays所用的sort方法的实现中，当待排数组长度小于47时，会使用插入排序。