当前位置：首页 > news >正文

折半插入排序

news 来源：原创 2024/5/19 14:47:22

2019独角兽企业重金招聘Python工程师标准>>>

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

http://bbs.itheima.com/thread-23776-1-1.html?fstgj

以前的学习网站，-全套java视频教程，需要的自己看下，可以去这个网站下载，下载视频免费，不需要注册和做什么任务

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

如果在最复杂的情况下，所要排序的整个数列是逆序的，当第 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);
    }
}