插入排序

1、思路：假定前面的序列已经有序，当前元素插入前面有序的序列。从后往前遍历，比当前元素大的，往后移，为当前元素腾出位置。

2、代码：

 1 template <typename T>
 2 void InsertSort(vector<T>& vec)
 3 {
 4     for(int i=1; i< vec.size();i++)
 5     {
 6         int j =i;
 7         T target = vec[i];        
 8         while(j>0 && target<vec[j-1])
 9         {
10             vec[j] = vec[j-1];
11             j--;
12         }
13         if(j!=i)
14         {
15             vec[j] = target;
16         }        
17     }
18 }

3、上面代码有个问题，当前元素找自己位置的时候，从后往前遍历，既然前面的序列已经有序，可以采用二分查找。代码：

 1 template <typename T>
 2 int FindPosition(const vector<T>& vec,int lhs,int rhs,T target)
 3 {
 4     if(rhs-lhs ==1)
 5     {
 6         if(target>vec[lhs])
 7         {
 8             return rhs;
 9         }
10         else
11         {
12             return lhs;
13         }
14     }
15     else
16     {
17         int mid = (lhs+rhs)/2;
18         if(target>vec[mid])
19         {
20             return FindPosition(vec,mid,rhs,target);
21         }
22         else
23         {
24             return FindPosition(vec,lhs,mid,target);
25         }
26     }    
27 }
28 
29 
30 template <typename T>
31 void InsertSort(vector<T>& vec)
32 {
33     for(int i=1; i< vec.size();i++)
34     {
35         int j =i;
36         T target = vec[j];
37         int position = FindPosition(vec,0,j,target);
38 
39         while(j>position)
40         {
41             vec[j] = vec[j-1];
42             j--;
43         }
44         vec[position] = target;
45     }
46 }