常用排序算法的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])。二分插入排序是稳定的排序算法。



转载自  开发者的天空