Java常见排序算法详解—— 二分插入排序

转载请注明出处:https://www.jianshu.com/p/18e3847816d9

二分插入排序Binary Insert Sort

概念:

二分(折半)插入排序是一种在直接插入排序算法上进行小改动的排序算法。其与直接排序算法最大的区别在于查找插入位置时使用的是二分查找的方式,在速度上有一定提升。

原理:

总共有N个元素,当插入第i个元素时,对前面的0~i-1个元素进行折半,先跟他们中间的那个元素比,如果小,那么再对前半折半,否则对后半进行折半,知道左<右,然后再把第i个元素前一位于目标位置之间的所有元素后移,再把第i个元素放在目标位置上。 关说原理可能大家不是很理解,下面我们就用一个列子来详细说明一下:

例如:我们当前数组为[4 5 7 10 29 11] 已知当前0到第N-1个都是按顺序排序,现在对第N个11找对应位置。 第一趟

[4 5 7 10 29] 11  
L    M     R

11比中间M大 那么接下来第二趟为:

[4 5 7 10 29] 11
     L  M  R

11比中间M大 那么11的位置就在M+1这个

注意,我们这里的第0到第N-1已经是按照要求排好序的

代码:

//从小到大
 public  void sort() {
        for (int i = 1; i < array.length; i++) {
            int temp = array[i];
            int low = 0, high = i - 1;
            int mid = -1;
            while (low <= high) {
                mid = low + (high - low) / 2;
                if (array[mid] > temp) {
                    high = mid - 1;
                } else { // 元素相同时,也插入在后面的位置
                    low = mid + 1;
                }
            }
            for(int j = i - 1; j >= low; j--) {
                array[j + 1] = array[j];
            }
            array[low] = temp;
        }
    }

算法系列:

冒泡排序 选择排序 直接插入排序

完整代码:

Java和Kotlin代码我均放在了GitHub上,欢迎Star!

GitHub地址:https://github.com/yang0range/MyAlgorithm

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券