二分插入排序算法c++

二分插入排序是一种基于比较的排序算法，它利用了数组已经部分有序的特点。在C++中，它的基本思想是：

1. 首先，假设数组的第一个元素是已排序的。
2. 然后，从第二个元素开始，对于每个未排序的元素，算法会在已排序的部分找到其正确的位置（通常是中间位置），通过不断将比当前元素大的元素向右移动来完成插入。
3. 插入过程中，每次查找中间位置的过程都是通过二分搜索的方式进行的，这大大减少了查找次数，提高了效率。
4. 当找到正确位置后，将该元素插入到这个位置，并继续处理下一个未排序的元素，直到所有元素都被排序。

以下是简单的C++二分插入排序示例代码：

#include <vector>
using namespace std;

void binaryInsertionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int low = 0, high = i - 1;
        
        // 使用二分查找
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] > key) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        // 将key插入到低索引处
        for (int j = i; j > low; --j) {
            arr[j] = arr[j - 1];
        }
        arr[low] = key;
    }
}

// 示例
int main() {
    vector<int> arr = {9, 5, 7, 1, 6};
    binaryInsertionSort(arr);
    for (int num : arr) {
        cout << num << " ";
    }
    return 0;
}