二分插入排序

二分插入排序（Binary Insertion Sort），是在插入第 i 个元素时，对前面的 0 ~ i-1 元素进行折半，先跟他们中间的那个元素比，如果小，则对前半再进行折半，否则对后半进行折半，直到 left < right，然后再把第 i 个元素前 1 位与目标位置之间的所有元素后移，再把第 i 个元素放在目标位置上。¹

实际上，二分插入排序也算是一种对直接插入排序算法的改进。回到直接插入排序那里，其算法的实现过程中有一个地方可以被优化。在小循环中，我们是从右向左，往前进行遍历，但是！这个小循环遍历的是一个有序的序列啊！了解二分查找算法的同学肯定肯不会感到陌生，既然被被遍历的序列是有序的，那么我们就可以通过二分的方式来对其进行优化！

一、实现思路¶

1.1 步骤¶

1.2 流程图¶

注：以下面 C++ 语言的实现过程为准

二、实现代码¶

2.1 多语言版本¶

推荐学习 C++ 版本，更利于理解算法的本质。

template <typename T = int>
void binary_insertion_sort(T* arr, int n) {
    T tmp;
    int l, r, m;  // 左右中
    for (int i = 1; i < n; i++) {
        tmp = arr[i];  // 取出
        l = 0;
        r = i - 1;
        while (l <= r) {  // 二分查找
            m = (l + r) / 2;
            if (tmp < arr[m])  // 稳定性关键点
                r = m - 1;
            else
                l = m + 1;
        }
        for (r = i - 1; r >= l; r--)  // 重用r
            arr[r + 1] = arr[r];  // 移位
        arr[l] = tmp;  // 插入
    }
}

2.2 测试用例¶

9
6 28 13 72 85 39 41 6 20

6 6 13 20 28 39 41 72 85

三、算法性质¶

3.1 时空复杂度¶

3.1.1 时间复杂度分析¶

3.1.2 空间复杂度分析¶

整个算法的过程中，我们只用了 1 个临时变量来存储被取出来的那个元素，因此空间复杂度：

3.2 稳定性与排序方式¶

3.2.1 稳定性分析¶

能否稳定取决于具体的实现，实现细节没把握好也可能导致不稳定。关键在于对元素比较出现相等情况时是否应该插入的判断。

3.2.2 排序方式分析¶

排序方式属于内部排序，没有用到外部的空间。

四、相关习题¶

注：习题不保证与上述算法一定相关，只是可能相关

4.1 编程题¶

4.2 选择题¶