java 折半插入排序_JAVA_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > JAVA > java 折半插入排序

java 折半插入排序

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



class="java" name="code">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));
}
	

}
发表评论
用户名: 匿名