二分插入法
二分插入法每次看都无法一次理解清楚，在这里做一次笔记加深下印象。
一、Java代码如下所示：
public static void main(String[] args) {
int [] values = new int[]{3,8,7,6,1,9,12,2,5,11};
for(int i = 0 ; i < values.length ; i++){
System.err.print(values[i] + ",");
}
System.err.println();
sort(values);
System.err.println();
for(int i = 0 ; i< values.length; i++){
System.err.print(values[i] + ",");
}
}
public static void sort(int [] values){
for(int i = 0 ;i < values.length ; i++) //步骤1
int now = values[i];
int left = 0;
int right = i -1;
int center = 0;
while(left <= right){ //步骤2
center = (left + right)/2;
if(now < values[center]){ //步骤2.1
right = center -1;
}else{ //步骤2.2
left = center + 1;
}
}
for(int j = i-1 ;j >= left ; j--){ //步骤4 4.1 4.2
values[j+1] = values[j];
}
if(left != i){ //步骤5 5.1 5.2
values[left] = now;
}
}
}
输出结果：
3,8,7,6,1,9,12,2,5,11, 1,2,3,5,6,7,8,9,11,12,
二、简单举例说一下当I=4时代码执行过程 ，详细过程如下图所示：
在i = 0、1、2、3执行完以后，values的顺序就变成如下列表：
3, 6, 7, 8, 1, 9, 12, 2, 5, 11
此时当i=4初进循环时：
now = 1 ; left = 0 ; right = 3 ; center = 0;
left (1) <= right (3) 进入while循环：
center(1) = (left(0) + right(3))/2;
now(1) < values[center] (6)进入if:
right(2) = right(3) - 1;
left (1) <= right (2)进入while循环：
center(1) = (left(0) + right(2))/2;
now(1) < values[center] (6)进入if:
right(1) = right(2) - 1;
left (1) <= right (1)进入while循环：
center(0) = (left(0) + right(1))/2;
now(1) < values[center] (3)进入if:
right(0) = right(1) - 1;
left (0) <= right (0)进入while循环：
center(0) = (left(0) + right(1))/2;
now(1) < values[center] (3)进入if:
right(-1) = right(0) - 1;
left (0) <= right (-1)跳出while循环：
center = 0 ; left = 0 ; right=-1; now = 1;
j(3)=i(4)-1 >= left(0) 进入For循环：
values[j(3)+1] = values[j(3)];
valus = 3, 6, 7, 8, 8, 9, 12, 2, 5, 11;
j(2)=i(4)-1-1 >= left(0) 进入For循环：
values[j(2)+1] = values[j(2)];
valus = 3, 6, 7, 7, 8, 9, 12, 2, 5, 11;
j(1)=i(4)-1-1-1 >= left(0) 进入For循环：
values[j(1)+1] = values[j(1)];
valus = 3, 6, 6, 7, 8, 9, 12, 2, 5, 11;
j(0)=i(4)-1-1-1-1 >= left(0) 进入For循环：
values[j(0)+1] = values[j(0)];
valus = 3, 3, 6, 7, 8, 9, 12, 2, 5, 11;
i(4) != left(0) 进入if:
now=1 一直没变;
values[left(0)] =now(1)
valus = 1, 3, 6, 7, 8, 9, 12, 2, 5, 11
接下来进入当I=5的循环，过程同上。
三、执行流程分析说明：
1、对排序数组values进行从索引0进行递增循环，初入循环始终将左索引(left)设置为0，右索引(right)设置为当前索引向左移一位(i-1)，并将当前索引(i)对应数组的值赋值给循环内局部变量now进行备份。
2、循环使用左索引(left)与右索引(right)进行比较，如果左索引(left)小于或等于右索引(right)时，取出左右索引之和的中间值索引(center)在values数组中的值(values[center])与当前索引(i)在values数组中的值(now<--values[i]-->)进行比较。
2.1、如果中间索引值(values[center])大于当前索引值(now<--values[i]-->)时，将得到的中间索引(center)向左移动一位重新计算出右索引(right=center-1)，继续第2步进行左右索引比较、中间索引值与当前索引值比较。
2.2、如果中间索引值(values[center])小于或等于当前索引值(now<--values[i]-->)时，将得到的中间索引(center)向右移动一位重新计算出左索引(left=center+1)，继续第2部进行左右索引比较、中间索引值与当前索引值比较。
3、直到左索引(left)已经向右移动超过了右索引(right)时就跳出循环，进入下一步。此时如果2.1或2.2步已经执行过，那么此时跳出循环后得到左索引(left)，就是当前索引对应数组值将要插入到数组中的索引位置。
4、当前索引向左一位(i-1)循环递减得到的索引与第2步骤得到的左索引(left)进行比较。
4.1、如果当前索引左一位(i-1)循环递减的索引结果(i-1-n)大于或等于以上第2步骤得到的左索引时，将前者索引(i-n-1)对应的数组值赋值给该索引的右一位索引(i-1-n+1)对应的数组值。此时在数组中的(i-1-n)索引值和(i-1-n+1)索引值是相同的。接下来进入下一次第4步循环操作。
4.2、如果当前索引左一位(i-1)循环递减的索引结果(i-1-n)小于第三步得到的左索引时，跳出循环进入到下一步。
5、判断第3步获得到的左索引与当前索引进行比较。
5.1、如果不相同时，将第1步获取的now覆值给第3步获得到的左索引对应数组中的值。
5.2、如果相同时，进行下一次第2步循环。