算法描述：
直接插入排序在有序序列中查找时采用顺序查找，既然是有序序列，自然可以想到采用二分查找减少查找次数。时间复杂度还是 O(N^2)，因为不管是采用二分查找还是顺序查找，算法大部分时间都花在元素的移动上，二分查找只能减少比较次数，在查找位置上节约时间。
性能分析：
时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：稳定
代码实现：
// C++代码 class BinaryInsertionSort { public: static void binaryInsertionSort(int array[], int length) { for (int i = 1; i < length; ++i) {// 遍历无序序列 int left = 0;// 有序序列左指针 int right = i - 1;// 有序序列右指针 int key = array[i];// 记录准备插入的元素 while (left <= right) { int mid = (left + right) / 2;// 有序序列中间位置 if (array[mid] < key) {// 二分查找 left = mid + 1; } else {// array[mid] >= key两种情况合并，便于后续统一处理 right = mid - 1; } } // 找到元素插入位置后，整体后移 for (int j = i - 1; j >= left; --j) { array[j + 1] = array[j]; } array[left] = key;// 填入对应位置 } } };
// Java代码 class BinaryInsertionSort { public static void binaryInsertionSort(int[] array) { for (int i = 1; i < array.length; ++i) {// 遍历无序序列 int left = 0;// 有序序列左指针 int right = i - 1;// 有序序列右指针 int key = array[i];// 记录准备插入的元素 while (left <= right) { int mid = (left + right) / 2;// 有序序列中间位置 if (array[mid] < key) {// 二分查找 left = mid + 1; } else {// array[mid] >= key两种情况合并，便于后续统一处理 right = mid - 1; } } // 找到元素插入位置后，整体后移 for (int j = i - 1; j >= left; --j) { array[j + 1] = array[j]; } array[left] = key;// 填入对应位置 } } }
原文：https://www.cnblogs.com/Acx7/p/14691516.html