请用C++完成折半插入排序并给出实现

好的，以下是折半插入排序的C++实现：

void binaryInsertionSort(vector<int>& nums) {
    int n = nums.size();
    for (int i = 1; i < n; ++i) {
        int key = nums[i];
        int left = 0, right = i - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;  // 防止溢出
            if (nums[mid] > key) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        for (int j = i - 1; j >= left; --j) {
            nums[j + 1] = nums[j];
        }
        nums[left] = key;
    }
}

折半插入排序的思路和插入排序类似，都是将数组分成已排序和未排序两部分，每次从未排序部分中取出一个元素，插入到已排序部分中的正确位置。不同的是，折半插入排序在查找插入位置时使用了折半查找的方法，因此可以更快地找到插入位置。具体来说，每次需要插入一个元素时，我们先用折半查找在已排序的子数组中找到第一个大于等于该元素的位置，然后将该位置后的元素全部后移一位，最后将该元素插入到该位置。这样，我们就可以在O(nlogn)的时间复杂度内完成排序。