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));}}