二分插入排序

一、算法描述

1.1 核心思想

• 数据分为已排序区间和未排序区间
• 从未排序区间取出元素，通过二分法找到合适的位置，插入到已排序区间中
• 插入已排序区间时，同时要保证已排序区间的有序性

总体上和插入排序差不多，只是在插入的时候，使用二分查找来找到合适的插入位置。

1.2 细节解释

比如说，数组 [2, 7, 1, 4, 3, 6, 5]。

首先分成未排序和已排序区间，第 1 个值无需排序，默认属于已排序区间：

已排序                           未排序
 ___                              ___ ___ ___ ___ ___ ___
| 2 |                            | 7 | 1 | 4 | 3 | 6 | 5 |

此时从未排序区间中取一个值 7，插入到已排序区间：

通过二分法定位到 7 应该在的位置 [1]，所以 7 直接插入 [1] 的位置：

已排序                           未排序
 ___ ___                          ___ ___ ___ ___ ___
| 2 | 7 |                        | 1 | 4 | 3 | 6 | 5 |

继续从未排序区间取值 1，二分法定位到 [0]，所以 1 直接插入 [0] 的位置：

已排序                           未排序
 ___ ___ ___                      ___ ___ ___ ___
| 1 | 2 | 7 |                    | 4 | 3 | 6 | 5 |

以此类推，后面每一步的结果如下：

二分插入 4：

已排序                           未排序
 ___ ___ ___ ___                  ___ ___ ___
| 1 | 2 | 4 | 7 |                | 3 | 6 | 5 |

二分插入 3：

已排序                           未排序
 ___ ___ ___ ___ ___              ___ ___
| 1 | 2 | 3 | 4 | 7 |            | 6 | 5 |

二分插入 6：

已排序                           未排序
 ___ ___ ___ ___ ___ ___          ___
| 1 | 2 | 3 | 4 | 6 | 7 |        | 5 |

二分插入 5：

已排序                           未排序
 ___ ___ ___ ___ ___ ___ ___
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |

经过 n 轮插入以后，数组就排好序了。

二、算法实现

二分插入排序算法的伪代码如下：

binaryInsertSort(int[] arr) {
    for (i = 1; i < n; i++) {
        // 未排序区间数据元素
        x = arr[i];
        // 二分查找合适的插入位置
        loc = firstGreat(arr, 0, i - 1, x);
        // 插入到已排序区间合适的位置
        for (j = i; j > loc; j--) {
            arr[j] = arr[j - 1];
        }
        arr[loc] = x;
    }
}

执行过程如下：

=====  初始数组 =====
[0, 3, 1, 6, 2, 5, 4]

=====第 1 轮插入=====
[0, 1, 3, 6, 2, 5, 4]

=====第 2 轮插入=====
[0, 1, 3, 6, 2, 5, 4]

=====第 3 轮插入=====
[0, 1, 2, 3, 6, 5, 4]

=====第 4 轮插入=====
[0, 1, 2, 3, 5, 6, 4]

=====第 5 轮插入=====
[0, 1, 2, 3, 4, 5, 6]

三、算法分析

3.1 时间复杂度

• 最好时间复杂度：O(nlogn)
• 最坏时间复杂度：O(n^2)
• 平均时间复杂度：O(n^2)

从复杂度上看，貌似二分插入排序比插入排序的复杂度还要高。

• 二分插入排序只是提升了比较速度，即比较次数从 n^2 -> nlogn
• 二分插入排序的交换次数没有改变，所以总体复杂度和插入排序是一样的

但是在实际排序中，比较次数的影响会更大一些，所以二分插入排序的性能也会显得更好。

3.2 空间复杂度

• 空间复杂度：O(1)
• 原地算法

3.3 稳定性

• 稳定排序算法

附录

/**
 * 二分插入排序
 * <p>
 * 时间复杂度：最好 O(nlogn) 最差 O(n^2) 平均 O(n^2)
 * <p>
 * 空间复杂度：O(1)
 * <p>
 * 稳定性：稳定
 *
 * @author weijiaduo
 * @since 2023/9/28
 */
public class BinaryInsertSort implements Sort {

    @Override
    public void sort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int x = arr[i];
            // 二分查找合适的插入位置
            int loc = firstGreat(arr, 0, i - 1, x);
            // 插入到已排序区间合适的位置
            for (int j = i; j > loc; j--) {
                arr[j] = arr[j - 1];
            }
            arr[loc] = x;
        }
    }

    /**
     * 寻找第一个大于指定值的位置
     *
     * @param arr 数组
     * @param lo  起始位置 [lo, hi]
     * @param hi  结束位置 [lo, hi]
     * @param val 指定值
     * @return 符合条件的索引
     */
    private int firstGreat(int[] arr, int lo, int hi, int val) {
        int left = lo, right = hi;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] > val) {
                if (mid == 0 || arr[mid] <= val) {
                    return mid;
                }
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

}