本文共 1226 字，大约阅读时间需要 4 分钟。

插入排序中的插入位置查找操作可以通过二分查找优化，提升性能。我们可以通过以下步骤实现这一点。

思路分析

插入排序的核心在于为新元素找到合适的位置。传统方法是从后向前扫描找到插入点，而二分查找则利用有序数组的特性，快速缩小范围。

#include 
   
    using 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函数接受数组和其长度，实现插入排序。
• 外层循环：从第二个元素开始处理，逐步构建有序数组。
• 二分查找：通过low和high确定插入位置，利用中间元素进行范围缩小。
• 插入操作：从当前位置开始，向后移动元素，插入新元素。
• 主函数：初始化数组，调用排序函数，输出结果。

这种方法保持了插入排序的时间复杂度O(n²)，但通过二分查找显著提升查找效率，达到O(log n)。整体复杂度为O(n²)，适合大部分实际应用。