折半插入排序是插入排序的优化，用二分查找确定插入位置以减少比较次数至O(log n)，但移动元素仍为O(n)，总时间复杂度仍为O(n²)。
折半插入排序并不是标准术语，实际指的是在插入排序过程中，对已排序部分使用二分查找（折半查找）来定位新元素的插入位置，从而减少比较次数。Java 中无法直接用数组“自动”实现折半插入排序，但可以手动结合 Arrays.binarySearch 或手写二分逻辑，在每次插入前快速确定插入索引，再移动元素完成插入。
核心思路：用二分找位置，用移动腾空间
普通插入排序每插入一个元素，需从右往左逐个比较；而折半插入排序改用二分法在已排序子数组中查找插入点（即第一个 ≥ 当前元素的位置），将比较次数从 O(n) 降至 O(log n)。注意：移动元素仍需 O(n)，所以总时间复杂度仍是 O(n²)，但比较操作显著减少，对大数据量、高比较开销的场景有实际价值。
关键步骤与代码要点
- 外层循环遍历未排序部分（下标 i 从 1 到 length−1）
- 暂存
arr[i]为待插入元素key - 在
arr[0..i−1]子数组中用二分查找确定key应插入的最左位置pos（即满足arr[pos] >= key的最小下标） - 将
arr[pos..i−1]整体后移一位（用System.arraycopy或循环） - 把
key赋值给arr[pos]
手写二分查找定位插入点（推荐）
避免 Arrays.binarySearch 的局限性：它返回负值时需转换为插入点，且对重复元素行为不直观。手写更可控：
分析 Java Spring Boot 后端 Controller 代码，自动生成 Markdown 格式的接口文档。当用户说“生成 Java 接口文档”、“生成 API 文档”、“从 Spring 代码生成文档”时触发。
立即学习“Java免费学习笔记（深入）”；
int binarySearchInsertPos(int[] arr, int left, int right, int key) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] < key) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left; // 即第一个 >= key 的位置
}
调用示例：int pos = binarySearchInsertPos(arr, 0, i-1, key);
完整可运行示例（升序）
public static void binaryInsertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
// 在 [0, i-1] 中找插入位置
int pos = binarySearchInsertPos(arr, 0, i - 1, key);
// 将 [pos, i-1] 向右移动一位
System.arraycopy(arr, pos, arr, pos + 1, i - pos);
arr[pos] = key;
}
}
注意：System.arraycopy 比手动循环移动更高效，且天然支持重叠区域复制。
适用场景与注意事项
- 适合 小规模数组（如 n 比较代价极高 的对象排序（如自定义类重写了耗时的
compareTo） - 对基本类型（如
int）效果有限，因移动和赋值开销可能抵消比较节省 - 稳定排序：相同元素相对顺序不变（因插入时总是插在相等元素左侧）
- 原地排序：仅需 O(1) 额外空间
