二分实现的插入排序

package com.ncsi.straight_insertion_sort;
/**
 * 折半插入排序 Binary Insertion Sort   
 * 折半查找的时间复杂度为O(logN)，但定位后循环数据后移仍然要花费O(N)的代价。
 * 因此时间复杂度仍然是O(N^2)，空间复杂度为O(1)
 * @author baiwei
 *
 */
public class BISortion {
	
	/**
	 * 
	 * @param arrays 需要排序的数组
	 * @param size  需要排序的大小
	 */
	void sort(int[] arrays,int size){
		
		int key;//保存关键值
		int i = 1;//从第二位开始
		for(;i<size;i++){
			key = arrays[i];
			int low = 0,hight = i-1;
			//折半查找
			while(low <= hight){
				int middle = (low+hight)/2;
				if(key < arrays[middle]){
					hight = middle-1;
				}else{
					low = middle+1;
				}
			}
			//移动位置
			for(int j = i-1;j>=hight+1;j--){
				arrays[j+1] = arrays[j];
			}
			arrays[hight+1] = key;
			
			
		}
		//打印数组
		for(int data:arrays){
			System.out.print(" "+data);
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		int[] arrays = {49,38,65,97,76,13,27,49};
		new BISortion().sort(arrays, arrays.length);
	}

}