二分插入排序算法

本文主要是介绍二分插入排序算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

	public static void main(String args[]){int a[] ={0,9,5,6,10,2,7,8};
//		directInsertSort(a);binaryInsertSort(a);}//打印当前数组的内容public static void printArray(String text,int []a){System.out.print(text);int n = a.length;//遍历数组当中的内容for(int i=0;i<n-1;i++){System.out.print(a[i]+",");	}System.out.println(a[n-1]);}<pre class="java" name="code">//二分插入排序//与直接插入排序算法类似，不同之处在于确定好插入的位置之后，一次性地将数据往后移动。public static void binaryInsertSort(int []a){//数组的长度int n = a.length;for(int i=2;i<n;i++){printArray("当前的数据为：", a);//如果有序的最后一位大于要排序的一位，将其加入标记位a[0]if(a[i-1]>a[i]){a[0] = a[i];printArray("将第"+i+"位放入标记位：",a);//用二分方式查找要插入的位置(将有序的队列的中间值与要插入的数据比较。如果大，则继续从中间值的右边继续二分查找；如果小，则从中间值的左边开始(相等的情况应该默认为大)，以此类推)int low = 1;int high = i-1;while(high>=low){int mid = (low + high)/2;//如果插入数据比中间值大if(a[0]>=a[mid]){low = mid+1;}elsehigh = mid-1;}printArray("用二分法查找到插入数据的位置为"+(high+1)+":",a);//跳出循环之后，要插入的位置为high+1(如果不明白的话自己可以尝试一下，假如最后a[0]判断为在a[3]和a[4]之间，这时low=3,mid=3,high=4)//假如a[0]<a[3],则进入else,low=3,mid=3,high=2,跳出循环，要插入数据位置为3//假如a[3]<a[0]<a[4],则进入if,low=4,mid=3,high=4,进入else,low=4,mid=4,high=3,跳出循环，要插入数据位置为4//假如a[4]<a[0],则进入if,low=4,mid=3,high=4,进入if,low=5,mid=4,high=4,跳出循环，要插入的位置为5int j;for( j = i-1; j>=high+1;j--){//向后移动数据a[j+1] = a[j];}a[j+1] = a[0];printArray("插入数据后的结果为：",a);	}}}

输出结果为：