常用排序算法的Java实现(2)-二分插入排序
前面讲了直接插入排序，下面来讲讲二分插入排序。
二分插入排序也是插入排序的一种，和直接插入排序不同的是比较的方法不同。直接插入排序是将第i个与前面i-1个逐个比较，找到要插入的位置。最好的情况是只比较一次，最坏的情况是比较i-1次。二分插入排序采用二分法来减少最坏情况下的比较次数。例如：
有6个记录，前5个已排序的基础上，对第6个记录排序。
[3,5,8,12,23], 19
前面有5个已经排序的，中间位置是第3个。将第6个与第3个进行比较，19 > 8，说明19应该排在8后面，但是具体的位置还没有确定，还需要继续进行比较。在后面的两个（第4个和第5个），我们取中间位置为第4个。 19>12，说明19应该排在12后面。再将19和最后面的一个进行比较，19<23,说明19应该排在23的前面，这样我们就确定了19最终的位置。
大家可以看到，在这种情况下，直接插入排序需要比较5次，而二分插入排序只需要比较3次。
下面就是二分插入排序的代码，同样的我们以对整数进行升序排列为例子：

public int[] binSort(int[] source){                for (int i=0; i<source.length; i++){                        int left = 0;                        int right = i-1;                        while (left <= right){                                int mid = left + (right - left)/2;                                if (source[i] > source[mid]){                                        left = mid + 1;                                } else {                                        right = mid - 1;                                }                        }                                               int temp = source[i];                        moveBackward(left, i-1, source);                        source[left] = temp;                                       }                               return source;        }        /*         * 将给定数组中指定范围内的所有元素在数组中向后移一个位置。         */        private void moveBackward(int from, int to, int[] values){                if (from < 0)                        return;                if (values == null || values.length<2)                        return;                if (from >= values.length)                        return;                if (to > values.length -2)                        to = values.length - 2;                for (int i=to + 1; i>from; i--){                        values[i] = values[i-1];                }        }

二分插入排序的比较次数是O(nlog[sub]2[/sub])。二分插入排序是稳定的排序算法。



转载自 开发者的天空