开发面试题之二分法插入排序

二分插入排序算法是直接插入排序算法的一种优化，比起直接插入排序算法，在排序数据量比较大的时候，二分插入排序的速度就要远远高于直接插入排序。

二分插入排序算法的思想是什么呢？

二分插入排序通过从第二个数开始将需要排序的数分为两个部分，左边部分有序，右边部分无序，然后从右边部分第一个数开始，一个一个插入前面有序部分，与直接插入排序唯一不同的是：二分插入排序会先找出左边有序部分的中间值，然后与需要插入的值比较，所以在插入之前，就只需要与左边有序部分的一半值进行比较。因此，在数据量比较大的时候，二分插入排序算法就更加高效，速度更快。

算法时间复杂度：O(n^2)

所以，二分查找排序比较次数为：x= log2n

二分查找插入排序耗时的操作有：比较 + 后移赋值。时间复杂度如下：

1. 最好情况：查找的位置是有序区的最后一位后面一位，则无须进行后移赋值操作，其比较次数为： log2n 。即O( log2n)

2. 最坏情况：查找的位置是有序区的第一个位置，则需要的比较次数为： log2n，需要的赋值操作次数为n(n-1)/2加上 (n-1) 次。即O(n^2)

3. 渐进时间复杂度（平均时间复杂度）：O(n^2)

空间复杂度：O(1)

稳定性：稳定

//二分法插入排序

public static void BinInsertSort(int[] a){

int key, left, right, middle;

for(int i=1; i<a.length; i++){

key = a[i]; // key 为需要插入的目标值，其前面为已经排好的数组

left = 0; // 最左边的数，从a[0] 开始

right = i-1; // 最右边的数，所要插入的那个数的前一位

while(left<=right) {

middle = (left + right) / 2; // middle 中间位

if (a[middle] > key) // 比较中值与要插入的值大小，更新数组下标 left 与right的值。

right = middle – 1;

else

left = middle + 1;

}

for(int j=i-1; j>=left; j–){ //将a[left]->a[i-1]的数都往后移一位

a[j+1] = a[j];

}

a[left] = key; // 最后将a[i] 插入a[left] 位置

}

}

main方法：

public static void main(String[] args) {

int[] a = {7,5,3,2,1,6,4,8,10,9};

System.out.println(Arrays.toString(a));

BinInsertSort(a);

System.out.println(Arrays.toString(a));

}