### 思路
折半插入排序是一种改进的插入排序算法，通过二分查找来确定插入位置，从而减少比较次数。每次插入时，先用二分查找找到插入位置，然后将元素插入到正确的位置。
### 伪代码
1. 读取输入的待排序关键字个数`n`。
2. 读取`n`个待排序关键字并存储在数组中。
3. 对数组进行折半插入排序：
- 从第二个元素开始，依次对每个元素进行插入排序。
- 使用二分查找确定当前元素的插入位置。
- 将当前元素插入到正确的位置。
- 输出当前排序结果。
4. 重复步骤3直到排序完成。
### C++代码
#include <iostream>
#include <vector>
using namespace std;// 二分查找插入位置
int binarySearch(const vector<int>& arr, int item, int low, int high) {while (low <= high) {int mid = low + (high - low) / 2;if (arr[mid] == item)return mid + 1;else if (arr[mid] < item)low = mid + 1;elsehigh = mid - 1;}return low;
}// 折半插入排序
void binaryInsertionSort(vector<int>& arr) {int n = arr.size();for (int i = 1; i < n; ++i) {int key = arr[i];int j = i - 1;// 找到插入位置int loc = binarySearch(arr, key, 0, j);// 移动元素while (j >= loc) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;// 输出当前排序结果for (int k = 0; k < n; ++k) {if (k > 0) cout << " ";cout << arr[k];}cout << endl;}
}int main() {int n;cin >> n;vector<int> arr(n);for (int i = 0; i < n; ++i) {cin >> arr[i];}binaryInsertionSort(arr);return 0;
}### 总结
折半插入排序通过二分查找来确定插入位置，从而减少了比较次数。每次插入时，先用二分查找找到插入位置，然后将元素插入到正确的位置。每趟排序后输出当前排序结果。
