二分插入法

二分插入法每次看都无法一次理解清楚，在这里做一次笔记加深下印象。

一、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步循环。