折半插入排序代码实现
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:0low:1 high:0low:3 high:2low:4 high:3low:3 high:2low:1 high:0low:0 high:-11 3 6 8 9 33 55 97?
??? 与直接插入排序相比，折半插入排序明显地减少了关键字的“比较”次数，但记录“移动”次数不变，故时间复杂度为n(o^2)