折半插入排序代码实现

package sort;

/**
 * @author linjia
 * 折半插入排序
 */
public class BinaryInsertSort {

	public int[] binSort(int r[], int n) {
		
		for(int i=1;i<n;i++)
		{
			int temp=r[i];
			int low=0;
			int high=i-1;
			
			while(low<=high)
			{
				int mid=(low+high)/2;               //折半
				if(temp<r[mid])high=mid-1;      //插入点在低半区
				else low=mid+1;                      //插入点在高半区
			}
			
			System.out.println("low:"+low+" high:"+high);
			
			for(int j=i-1;j>=high+1;j--)
			{
				r[j+1]=r[j];
			}
			
			r[high+1]=temp;
		}
		
		return r;
	}

	public static void main(String[] args) {
		int[] test = { 3, 9, 8, 55, 97, 33, 6, 1 };

		test = new BinaryInsertSort().binSort(test, test.length);

		for (int i : test) {
			System.out.print(i+" ");
		}
	}
}

 结果：

low:1 high:0
low:1 high:0
low:3 high:2
low:4 high:3
low:3 high:2
low:1 high:0
low:0 high:-1
1 3 6 8 9 33 55 97 

 

    与直接插入排序相比，折半插入排序明显地减少了关键字的“比较”次数，但记录“移动”次数不变，故时间复杂度为n(o^2)