java 减半插入排序

java 折半插入排序
pdf文档上看到的。
直接插入排序算法简便、容易实现。当待排序元素的数量n 很小时，
这是一种较好的排序方法，但是通常待排序元素数量n 很大，则不宜采用直接插入排序方法，
此时需要对直接插入排序进行改进。
直接插入排序的基本操作是向有序序列中插入一个元素，插入位置的确定是通过对有序
序列中元素按关键字逐个比较得到的。既然是在有序序列中确定插入位置，则可以不断二分
有序序列来确定插入位置，即搜索插入位置的方法可以使用折半查找实现。
折半插入排序所需的辅助空间与直接插入排序相同，从时间上比
较，折半插入排序仅减少了元素的比较次数，但是并没有减少元素的移动次数，因此折半插
入排序的时间复杂度仍为O(n2)。

package test.sort;

import java.util.Arrays;

public class BinInsertSort {
	
	
	
	public int[] binInsertSort(int[] a){
		
		
		for(int i=1;i<a.length;i++){
			/**
			 *  保存当前操作值，记录高位hi用来做高低位的计算，低位永远是0
			 *  hi 是用来记录要插入的位置的上一个位置。
			 *  这样看来着个就是直接插入排序的一个改版，
			 *  只要记住：待操作元素前面的永远是有序的，对有序的集合做插入操作，找到插入点移动数据，插入就可以了。
			 */
			int tmp = a[i],hi = i-1,low = 0;
			
			while(low<=hi){//折半确定位置 
				int mid = (low+hi)/2;
				if(tmp<a[mid]){
					hi = mid -1;
				}else{
					low = mid+1;
				}
			}
			for(int j =i-1;j>hi;j--){
				a[j+1] =a[j];//在待插入位置后面的元素全部向后移动
			}
			a[hi+1] = tmp;//将元素插入指定空间
			
		}
		
		return a;
		
	}
  public static void main(String[] args) {
	  BinInsertSort b = new BinInsertSort();
		int[] as = { 1, 34, 56, 23, 67, 82, 4, 3, 2, 0, 13, 76, 90, 21, 24, 44,
				4 };
		int[] a = b.binInsertSort(as);
		System.out.println(Arrays.toString(a));
}
	

}

java 减半插入排序

相关推荐