前言： 折半插入排序（ Binary Insertion Sort ）是对直接插入排序算法的一种改进。

插入排序思想介绍

折半插入排序与直接插入排序算法原理相同。只是，在向已排序的数据中插入数据时，采用来折半查找（二分查找）。先取已经排序的序列的中间元素，与待插入的数据进行比较，如果中间元素的值大于待插入的数据，那么待插入的数据属于数组的前半部分，否则属于后半部分。依次类推，不断缩小范围，确定要插入的位置。

算法说明：

待排序数据： 2 ， 1 ， 6 ， 7 ， 4

取第一个元素作为有序表，剩余的元素作为无序表

 其中有序表： 2 ；无序表： 1 ， 6 ， 7 ， 4

第一次比较，从无序表中取出第一个数 1 ，与中间值 2 比较， 1<2 ， 1 插到 2 的前面，得到

 有序表： 1 ， 2 ；无序表： 6 ， 7 ， 4

第二次比较，从无序表中取出第一个数 6 ，与中间值 1 比较， 6>1 ，要放在 1 的后面，再与后半区（有序表： 2 ）的中间值 2 比较， 6>2 ，6 插入到 2 的后面，得到

 有序表： 1 ， 2 ， 6 ；无序表： 7 ， 4

第三次比较，从无序表中取出第一个数 7 ，与中间值 2 比较， 7>2 ， 7 放在 2 后面，再与后半区（有序表： 6 ）的中间值 6 比较， 7>6 ， 7放在 6 后面，得到

 有序表： 1 ， 2 ， 6 ， 7 ；无序表： 4

第四次比较，从无序表中取出第一个数 4 ，与中间值 2 比较， 4>2 ， 4 放在 2 后面，再与后半区（有序表 :6,7 ）的中间值 6 比较， 4<6 ， 4放在 6 前面，最终得到：

1 ， 2 ， 4 ， 6 ， 7

折半插入排序的代码实现

private void binaryInsertSort(int arr[]){  

 int low = 0; 

 int high = 0; 

 int m = 0;// 中间位置 

 for(int i = 1; i < arr.length; i++){ 

 low = 0; 

 high = i-1; 

 while(low <= high){ 

 m = (low+high)/2; 

 if(arr[m] > arr[i]) 

 high = m - 1; 

 else 

 low = m + 1; 

 } 

 // 统一移动元素，将待排序元素插入到指定位置 

 temp = arr[i]; 

 for(int j=i; j > high+1; j--){ 

 arr[j] = arr[j-1]; 

 } 

 arr[high+1] = temp; 

} 

 }

总结

折半插入排序相对稳定，相对于直接插入排序，减少了比较次数；但是相对直接插入排序，移动次数不变。

插入排序思想介绍

折半插入排序与直接插入排序算法原理相同。只是，在向已排序的数据中插入数据时，采用来折半查找（二分查找）。先取已经排序的序列的中间元素，与待插入的数据进行比较，如果中间元素的值大于待插入的数据，那么待插入的数据属于数组的前半部分，否则属于后半部分。依次类推，不断缩小范围，确定要插入的位置 。

算法说明：

待排序数据： 2 ， 1 ， 6 ， 7 ， 4

取第一个元素作为有序表，剩余的元素作为无序表

 其中 有序表： 2 ；无序表： 1 ， 6 ， 7 ， 4

第一次 比较 ，从无序表中取出第一个数 1 ， 与中间值 2 比较， 1<2 ， 1 插到 2 的前面，得到

 有序表： 1 ， 2 ；无序表： 6 ， 7 ， 4

第二次 比较 ，从无序表中取出第一个数 6 ， 与中间值 1 比较， 6>1 ，要放在 1 的后面，再与后半区（有序表： 2 ）的中间值 2 比较， 6>2 ， 6 插入到 2 的后面，得到

 有序表： 1 ， 2 ， 6 ；无序表： 7 ， 4

第三次 比较 ，从无序表中取出第一个数 7 ， 与中间值 2 比较， 7>2 ， 7 放在 2 后面，再与后半区（有序表： 6 ）的中间值 6 比较，7>6 ， 7 放在 6 后面，得到

 有序表： 1 ， 2 ， 6 ， 7 ；无序表： 4

第四次 比较 ，从无序表中取出第一个数 4 ， 与中间值 2 比较， 4>2 ， 4 放在 2 后面，再与后半区（有序表 :6,7 ）的中间值 6 比较， 4<6 ， 4 放在 6 前面，最终得到：

  1 ， 2 ， 4 ， 6 ， 7

折半插入排序的代码实现

private  void binaryInsertSort( int  arr[]){  
2.   
int low = ;  
int high = ;  
int m = ; // 中间位置   
for ( int i = 1 ; i < arr.length; i++){  
low = ;  
high = i- 1 ;  
while (low <= high){  
m = (low+high)/ 2 ;  
if (arr[m] > arr[i])  
high = m - 1 ;  
else   
low = m + 1 ;  
}  
//统一移动元素，将待排序元素插入到指定位置   
temp = arr[i];  
for ( int j=i; j > high+ 1 ; j--){  
arr[j] = arr[j- 1 ];  
}  
arr[high+ 1 ] = temp;  
}          
}

总结

折半插入排序相对稳定，相对于直接插入排序，减少了比较次数；但是相对直接插入排序，移动次数不变。