本文共 1226 字，大约阅读时间需要 4 分钟。
插入排序中的插入位置查找操作可以通过二分查找优化，提升性能。我们可以通过以下步骤实现这一点。
插入排序的核心在于为新元素找到合适的位置。传统方法是从后向前扫描找到插入点，而二分查找则利用有序数组的特性，快速缩小范围。
基本原理：由于每次插入的子数组都是有序的，二分查找能高效找到插入位置。我们从数组的前端开始，逐步处理每个元素。
查找过程：设置low和high初始值，通过循环确定插入位置。若中间元素大于当前元素，调整high；反之调整low，直到找到正确位置。
插入操作：找到位置后，从后向前移动元素，腾出位置，插入当前元素。
优化灵活性：通过调换条件，可以实现插入排序的不同策略，如降序排序。
#includeusing namespace std;void sort(int arr[], int n) { int low, high, place, temp; for (int i = 1; i < n; ++i) { low = 0, high = i - 1; temp = arr[i]; while (low <= high) { int mid = (low + high) / 2; if (temp <= arr[mid]) { high = mid - 1; } else { low = mid + 1; } } place = low; for (int j = i - 1; j >= place; --j) { arr[j + 1] = arr[j]; } arr[place] = temp; }}int main() { int arr[9] = {3, 5, 1, 2, 7, 9, 12, 14, 8}; sort(arr, 9); for (int i = 0; i < 9; ++i) { cout << arr[i] << " "; } cout << endl; return 0;}
sort函数接受数组和其长度，实现插入排序。这种方法保持了插入排序的时间复杂度O(n²)，但通过二分查找显著提升查找效率，达到O(log n)。整体复杂度为O(n²)，适合大部分实际应用。
转载地址：http://dbgr.baihongyu.com/