插入排序之二分法插入排序

　

二分法排序

简介

二分法插入排序没有排序，只有查找。所以当找到要插入的位置时。移动必须从最后一个记录开始，向后移动一位，再移动倒数第2位，直到要插入的位置的记录移后一位。

• 二分法插入排序的思想
  • 对于每次循环，都有left，mid，right3个局部变量做支持。
  • 将要插入的元素同mid位置元素比较，选择left - mid-1还是mid+1 - right。
  • 最后记录left的位置，这个位置就是要插入的位置。
  • 然后将left - （要插入的位置-1）的所有元素的位置整体后移一位。空出left位置进行插入。

核心代码

/**
 * 二分法插入排序
 * 
 * @param a
 */
private static void binaryInsertSort(int[] a) {
    for (int i = 0; i < a.length; i++) {
        int temp = a[i]; // 待插入的元素
        int left = 0;
        int right = i - 1;
        int mid = 0;
        // 确定要插入的位置，最终要插入的位置是a[left]
        while (left <= right) {
            // 先获取中间位置
            mid = (left + right) / 2;
            if (temp < a[mid]) {
                // 如果值比中间值小，让right左移到中间下标-1
                right = mid - 1;
            } else {
                // 如果值比中间值大,让left右移到中间下标+1
                left = mid + 1;
            }
        }

        for (int j = i - 1; j >= left; j--) {
            // 以左下标为标准，在左位置前插入该数据，左及左后边全部后移一位
            a[j + 1] = a[j];
        }

        // left肯定不能等于i，因为temp本来就是a[i]
        if (left != i) {
            // 左位置插入该数据
            a[left] = temp;
        }
    }
}

• 每次循环left都从0开始，right从i-1开始。没什么问题。
• 只有当left <= right时，才计算mid。while循环为了确定插入位置。
• 第2个for循环为了后移元素，留出空位。
• 最后直接插入数据。

优缺点

• 优点

  • 稳定
  • 快

• 缺点

  • 元素移动次数较多

复杂度

• 时间复杂度

  • O(n^2)

• 空间复杂度

  • O(1)

• 稳定度

  • 稳定

应用场景

• 数据量小时使用。并且大部分已经被排序。

相关阅读

python二分法查找

常见的搜索方法：顺序查找、二分法查找、二叉树查找、哈希查找。 二分法查找 二分查找又称折半查找，优点是比较次数少，查找速度快，平均

二分法查找

二分查找： 即每次用比较区域中间的数值和要查找的数值作比较。用函数调用，程序更加简洁，可移植性增强。令查找这个函数模块返回一个

二分法查找详解

二分法查找从概念上很好理解，困难的地方在于有几个细节需要注意:1.循环执行条件。2.递进方式。3返回值的问题，返回左右边界值还是返

73-插入排序——直接插入排序

1. 插入排序   插入排序的基本思想：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子表中的适当位置，直到全部记

二分法查找

在用二分法查找前必须满足一个条件：必须是排序好的一组数字 思路：按照升序排序，从中间分，分成两半，如果所要查找的数字比中间的数字小，