本文共 1867 字，大约阅读时间需要 6 分钟。
算法思想简单描述：
在插入第i个元素时，对前面的0～i-1元素进行折半，先跟他们
中间的那个元素比，如果小，则对前半再进行折半，否则对后半
进行折半，直到left>right，然后再把第i个元素前1位与目标位置之间
的所有元素后移，再把第i个元素放在目标位置上。
折半插入排序其实就是直接插入排序的一种改进，引入了二分查找算法，这样关键字的比较次数就会减少，
数量级为O(nlog^2n)，但是元素移动次数还是O(n^2)，所以折半插入排序的时间复杂度是O(n^2)。
另外，折半插入排序是稳定的排序算法；
C++代码：
#include <stdio.h>
#include <iostream>using namespace std;
//二分排列
void binarySort(int *a,int len) { int start=0,mid=0,end=0; int tmp = 0;for(int i =1;i<len;i++)
{ start=0,mid=0,end=i-1; tmp = a[i];while(start<=end)
{ mid = (start+end)/2; if(a[mid]>a[i]) end = mid-1; else start = mid+1;}
for(int j=i-1;j>=end+1;j--) { a[j+1] = a[j]; } a[end+1] = tmp; }
}
int main() {int input[5] = {13, 97, 176, 13, 13};
binarySort(input,5); for(int i = 0;i<5;i++) printf("%d,",input[i]); printf("\n"); int t; cin >>t;}
Java代码
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; else low = 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)); } } }
转载地址：http://igmji.baihongyu.com/