插入排序：把一个数插入到一个有序的序列中，并要求插入后此数据序列仍然有序。这种排序思想就是插入排序。

    那么对于一个原始无序的序列，哪里找有序的部分呢？这个很简单，可以把序列分为两个部分，第一个元素是第一部分，其余元素是第二部分。第一个部分只有一个元素，当然是有序的！对于如何把其余元素插入到第一部分中去，按插入策略，可分为如下几种插入方法：

直接插入：每次a[i]先和前面一个数据a[i-1]比较，如果a[i] > a[i-1]说明a[0…i]也是有序的，无须调整。否则就令j=i-1,temp=a[i]。然后一边将数据a[j]向后移动一边向前搜索，当有数据a[j]<a[i]时停止并将temp放到a[j + 1]处。

看代码：

1. void InsertSortArray(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];    
10.             j--;   
11.         }   
12.         arr[j+1]=temp;   
13.     }   
14. }   

交换插入：也可以在比较的过程中，直接交换前后位置的元素，一步一步地把插入的元素交换到合适的位置，如下：

折半插入：在直接插入中，我们每次都是把一个元素插入到一个有序的序列中。为了使找到位置更高效，我们可以借鉴二分查找的方法，减少比较次数，快速找到合适的插入位置。这就是折半插入的来历。

根据二分查找时，区间选取的不同，可细分为如下两种：注意比较两者的细微差别哦

代码一：左闭右闭 [low,high]