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));
}
}
相关文章
