排序算法总结之折半插入排序
栏目：互联网时间：2014-09-15 03:44:10
基本思想
折半插入排序是对直接插入排序的简单改进，对于直接插入排序而言，当第i-1趟需要将第i个元素插入前面的0~i-1个元素序列中时，总是需要从i-1个元素开始，逐个比较每个元素，直到找到它的位置。这显然没有利用前面0~i-1个元素已经有序这个特点，而折半插入排序则改进了这一点。
对于折半插入排序而言，当需要插入第i个元素时，它不会逐个进行比较每个元素，而是：
（1）计算0~i-1索引的中间点，也就是用i索引处的元素和(0+i-1)/2索引处的元素进行比较，如果i索引处的元素值大，就直接在(0+i-1)/2~i-1半个范围内进行搜索；反之在0~(0+i-1)/2半个范围内搜索，这就是所谓的折半；
（2）在半个范围内搜索时，按照（1）的方法不断地进行折半搜索，这样就可以将搜索范围缩小到1/2、1/4、1/8…，从而快速的确定插入位置；
Java实现代码
package com.liuhao.sort;
import java.util.Arrays;
public class BinaryInsertSort {
public static void binaryInsertSort(DataWrap[] data){
int arrayLength = data.length;
for(int i=1; i<arrayLength; i++){
DataWrap tmp = data[i];
int low = 0;
int high = i-1;
// 不断折半，寻找合适的插入位置
while(low <= high){
int mid = (low + high) / 2;
if(tmp.compareTo(data[mid]) > 0){
low = mid + 1;
}
else{
high = mid - 1;
}
}
// 依次后移
for(int j=i; j>low ; j--){
data[j] = data[j-1];
}
data[low] = tmp;
System.out.println(Arrays.toString(data));
}
}
public static void main(String[] args) {
DataWrap[] data = {
new DataWrap(21, "")
,new DataWrap(30, "")
,new DataWrap(49, "")
,new DataWrap(30, "*")
,new DataWrap(16, "")
,new DataWrap(9, "") };
System.out.println("排序之前：" + Arrays.toString(data));
binaryInsertSort(data);
System.out.println("排序之后：" + Arrays.toString(data));
}
}
算法分析
折半插入排序减少了关键字的比较次数，但是记录的移动次数不变，其时间复杂度与直接插入排序相同。
------分隔线----------------------------
------分隔线----------------------------