折半插入排序-阿里云开发者社区

折半插入排序

2017-11-22 1246

简介：

+关注继续查看

只有比别人更早、更勤奋地努力，才能尝到成功的滋味。 ------麦克马斯特大学训言

记得之前总结过插入排序，有兴趣的可以看看---插入排序。

如果在最复杂的情况下，所要排序的整个数列是逆序的，当第 i-1 趟需要将第 i 个元素插入前面的 0~ i -1 个元素的序列当中的时候，它总是会从第 i -1 个元素开始，逐个比较每个元素的大小，直到找到相应的位置。

这个算法中丝毫没有考虑当要插入第 i 个元素时前面的 0~~ i -1 序列是有序的这个特点。今天要总结的这个算法就充分的利用了这一点。

算法的基本过程：

1）计算 0 ~ i-1 的中间点，用 i 索引处的元素与中间值进行比较，如果 i 索引处的元素大，说明要插入的这个元素应该在中间值和刚加入i索引之间，反之，就是在刚开始的位置到中间值的位置，这样很简单的完成了折半；

2）在相应的半个范围里面找插入的位置时，不断的用（1）步骤缩小范围，不停的折半，范围依次缩小为 1/2 1/4 1/8 .......快速的确定出第 i 个元素要插在什么地方；

3）确定位置之后，将整个序列后移，并将元素插入到相应位置。

算法实现：

import java.util.*;

public class BinaryInsertSort {
    private static int[] Sort(int[] arr) {
        int i, j;
        //保存中间插入的值
        int insertNote = 0;
        //将待排序的数列保存起来
        int[] array = arr;
        System.out.println("开始排序：");
        for (i = 1; i < array.length; i++) {
            int low = 0;
            int high = i - 1;
            insertNote = array[i];
            //不断的折半
            while (low <= high) {
                //找出中间值
                int mid = (low + high) / 2;
                //如果大于中间值
                if (array[i] > array[mid]) {
                    //在大于中间值的那部分查找
                    low = mid+1;
                } else
                    //在小于中间值的那部分查找
                    high = mid-1;
            }
          //将整体数组向后移
            for ( j=i; j > low; j--) {
                array[j] = array[j - 1];
            }
         //插入到指定的位置
            array[low] = insertNote;
            System.out.println(Arrays.toString(array));
        }
        System.out.println("排序之后：");
        System.out.println(Arrays.toString(array));
        return array;
    }

    public static void main(String[] args) {
        Random random = new Random();
        int[] array = new int[10];
        for (int i = 0; i < 10; i++) {
            array[i] = Math.abs(random.nextInt() % 100);
        }
        System.out.println("排序之前：");
        System.out.println(Arrays.toString(array));            
        BinaryInsertSort.Sort(array);
    }
}