C++ 实现折半插入排序：附测试主函数及边界处理要点

以下是使用 C++实现折半插入排序并设计测试主函数的代码： ```cpp #include <iostream> using namespace std; // 折半插入排序函数 void binaryInsertionSort(int arr[], int n) { int i, j, key, mid, low, high; for (i = 1; i < n; i++) { key = arr[i]; low = 0; high = i - 1; while (low <= high) { // 在有序区间内进行折半查找 mid = (low + high) / 2; if (arr[mid] < key) low = mid + 1; else high = mid - 1; } for (j = i - 1; j >= low; j--) // 将大于 key 的元素后移 arr[j + 1] = arr[j]; arr[low] = key; // 将 key 插入到合适位置 } } // 测试主函数 int main() { int arr[] = {12, 11, 13, 5, 6}; int n = sizeof(arr) / sizeof(arr[0]); cout << "排序前的数组为: "; for (int i = 0; i < n; i++) cout << arr[i] << " "; cout << endl; binaryInsertionSort(arr, n); cout << "排序后的数组为: "; for (int i = 0; i < n; i++) cout << arr[i] << " "; cout << endl; return 0; } ``` 额外需要注意的逻辑点： 1. 边界情况的处理，比如数组为空或者只有一个元素的情况。 2. 注意循环的条件和变量的更新，避免出现死循环或者越界访问。 3. 对于相同元素的处理，要保证排序的稳定性。 ######[AI写代码神器 | 464点数解答 | 2024-12-17 10:00:18]