排序算法--折半插入排序（二分查找排序）
?
折半插入排序其实就是直接插入排序的一种改进，引入了二分查找算法，这样关键字的比较次数就会减少，
数量级为O(nlog^2n)，但是元素移动次数还是O(n^2)，所以折半插入排序的时间复杂度是O(n^2)。
另外，折半插入排序是稳定的排序算法；
下面是用JAVA写的算法的两种实现方式。不过原理都是一样的
第一种：
??package sort;
import java.util.Arrays;public class BinarySearch1 {public static void main(String args[]){int array[]={49,38,65,97,76,13,27};binarySort(array,array.length);System.out.println("---------排序后的结果----------");System.out.println(Arrays.toString(array));}//二分查找public static int binarySearch(int array[],int low,int high,int temp){int mid=0;while(low<=high){mid=(low+high)/2;if(array[mid]<temp&&temp<=array[mid+1])return (mid+1);else if(array[mid]<temp)low = mid + 1;elsehigh = mid -1;}return high;}//二分排序public static void binarySort(int array[],int size){int i,j,k,temp;for(i=1;i<size;i++){temp=array[i];if(array[i]<array[0])k=0;elsek = binarySearch(array,0,i,temp);for(j=i;j>k;j--){array[j]=array[j-1];}array[k]=temp;System.out.println(Arrays.toString(array));}}}?运行结果如下：
??[38, 49, 65, 97, 76, 13, 27]
[38, 49, 65, 97, 76, 13, 27][38, 49, 65, 97, 76, 13, 27][38, 49, 65, 76, 97, 13, 27][13, 38, 49, 65, 76, 97, 27][13, 27, 38, 49, 65, 76, 97]---------排序后的结果----------[13, 27, 38, 49, 65, 76, 97]?
第二种：
?
package sort;import java.util.Arrays;public class BinarySearch2 {public static void main(String args[]){int array[]={49,38,65,97,76,13,27};binaryInsertSort(array,array.length);System.out.println("------------排序后的结果-------------");System.out.println(Arrays.toString(array));}/** * * @param array 要排序的数组 * @param size 数组的大小 */public static void binaryInsertSort(int []array,int size){int i,j,temp;int low,high,mid;for(i=1;i<size;i++){//将待插入的元素赋给temp，这个元素前面是有序数组，用于插入到有序数组中temp=array[i];low=0;high=i-1;while(low<=high){//有序数组的中间坐标，此时用于二分查找，减少查找次数mid = (low+high)/2;//如果有序序列中的中间元素大于待排序的元素，则有序序列的中间坐标向前搜索，否则向后搜索if(array[mid]>array[i])high=mid-1;elselow = mid + 1;}/** * j首先赋值为要插入值的前一个元素的最后的坐标，也就是有序数组中最后一个元素的坐标 * 然后依次向前扫描有序数组，然后如果满足条件则向后移动数据 */for(j=i-1;j>=low;j--){array[j+1]=array[j];}//将待排序的元素插入到array数组中array[low]=temp;System.out.println(Arrays.toString(array));}}}?运行结果：
?
[38, 49, 65, 97, 76, 13, 27][38, 49, 65, 97, 76, 13, 27][38, 49, 65, 97, 76, 13, 27][38, 49, 65, 76, 97, 13, 27][13, 38, 49, 65, 76, 97, 27][13, 27, 38, 49, 65, 76, 97]------------排序后的结果-------------[13, 27, 38, 49, 65, 76, 97]?
?
?