二分插入排序¶
一、算法描述¶
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;
}
}