用C++实现折半插入排序

以下是C语言实现折半插入排序的代码：

void binaryInsertionSort(int arr[], int n) {
    int i, j, left, right, middle, key;
    for (i = 1; i < n; i++) {
        key = arr[i];
        left = 0;
        right = i - 1;
        while (left <= right) {
            middle = (left + right) / 2;
            if (key < arr[middle])
                right = middle - 1;
            else
                left = middle + 1;
        }
        for (j = i - 1; j >= left; j--)
            arr[j + 1] = arr[j];
        arr[left] = key;
    }
}

折半插入排序的思路是，在已排好序的序列中使用二分查找找到待插入元素的位置，然后将该位置后面的所有元素后移一位，最后将待插入元素插入到正确的位置。该算法的时间复杂度为O(n^2)，但是相比于直接插入排序，折半插入排序的比较次数减少了，因此在某些情况下会更快。

相关问题

请用C++完成折半插入排序

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

void binaryInsertionSort(int arr[], int n) {
    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int left = 0, right = i - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (key < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        for (int j = i - 1; j >= left; --j) {
            arr[j + 1] = arr[j];
        }
        arr[left] = key;
    }
}

折半插入排序的思路类似于插入排序，但是它在寻找插入位置时使用了折半查找的方法，因此可以更快地找到插入位置。具体来说，每次需要将第i个元素插入到前i-1个已排序元素中的正确位置时，我们先利用折半查找找到插入位置，然后将插入位置后的元素全部后移一位，最后将第i个元素插入到插入位置。这样，我们就可以在O(nlogn)的时间复杂度内完成排序。

请用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)的时间复杂度内完成排序。