c++版折半插入排序源码及注释

以下是C++版的折半插入排序源码及注释：

#include <iostream>
using namespace std;

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;
    }
}

int main(){
    int arr[] = {5, 2, 4, 6, 1, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    binaryInsertionSort(arr, n);
    for (int i = 0; i < n; i++){
        cout << arr[i] << " ";
    }
    return 0;
}

注释：

1. `binaryInsertionSort` 函数是折半插入排序的实现，它接受一个整型数组 `arr` 和数组长度 `n` 作为参数。
2. 折半插入排序的基本思想是将待排序元素按照大小顺序依次插入到已排好序的序列中，使得插入后的序列仍然有序。与普通的插入排序不同的是，折半插入排序是采用折半查找的方式查找待插入位置，因此可以减少比较次数。
3. 在 `binaryInsertionSort` 函数中，变量 `i` 表示待插入元素的下标，变量 `key` 表示待插入元素的值。
4. 初始化折半查找的边界为第一个元素到待插入元素的前一个元素，即 `left = 0` 和 `right = i - 1`。
5. 在 while 循环中，不断折半缩小查找范围，直到找到待插入位置。
6. 将待插入位置之后的元素全部后移一位，为待插入元素腾出位置。
7. 将待插入元素插入到正确位置上。
8. `main` 函数中是一个简单的测试，输出排序后的数组。