吃完午饭回来洗完这篇去睡觉，心累~~~_{(>_<)}~~~
其实插入排序的核心思想就是从第一个数依次排序，在0~i-1个有序数列中查找到第i个数的位置，然后将其插入即可。这样，在查找这个位置时有很多种方法，可以利用前面最暴力的直接插入排序，也可以用接下来要写的二分插入排序，或者快排，堆排等等，按照实际情况或者项目需求随意组合即可。用二分排序在代码实现上有以下一个关键点：
不管left和right指针如何变化，这两货最终会指向同一个数字，这样的话要是要排序的list[i]>thisDigit,则left+1的位置即是要插入的位置，反之，若list[i]<thisDigit,则left的位置即是要插入的位置，等于的情况两者均可，随便写。。。只要理解了这点，对于所有二分插入排序算法的编写都不会困惑，例如什么给定数组不是偶数【相除有余】等等情况均可忽略。。。下面贴出代码：

include<iostream>

include<vector>

using namespace std;

class BinaryInsertSort{

private:
    int len;
    vector<int> list;
public:
    BinaryInsertSort(vector<int> _list, int _len);      
    void binary_insert_sort();      
    void out();

}; //end class

BinaryInsertSort::BinaryInsertSort(vector<int> _list, int _len){

        for(int i=0; i<_len; i++) list.push_back(_list[i]);
        this->len = _len;   

}

void BinaryInsertSort::binary_insert_sort(){

        int middle;   //中间的那个数
        int left;    //左指针 
        int right;   //右指针 
        for(int i=0; i<len; i++){
            
            left   = 0;
            right  = i-1;
            middle = list[i];
             
            while(left <= right){
                
                if( list[(left+right)/2] > middle) right = (left+right)/2 - 1;
                
                else left = (left+right)/2 + 1; 
            }  //end while
            
            for(int j=i; j>left; j--)list[j] = list[j-1];
            
            list[left] = middle;
            
        } //end for 

}

void BinaryInsertSort::out(){

for(int i=0; i<len;i++) cout<<list[i];  

}

int main(){

int array[9] = {9,8,7,6,5,4,3,2,1};
vector<int> list;
for(int i=0; i<9; i++) list.push_back(array[i]);
BinaryInsertSort mazhe(list,9);
mazhe.binary_insert_sort();
mazhe.out();

}