吃完午饭回来洗完这篇去睡觉，心累~~~(>_<)~~~
其实插入排序的核心思想就是从第一个数依次排序，在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();
}
