c++折半插入排序 ,从键盘输入记录数,依次输入各记录元素数据项的值,并以这些数值为记录的关键字对记录进行排序。最后在屏幕上输出排序后的记录。
时间: 2024-05-04 15:20:15 浏览: 25
以下是C++实现折半插入排序的代码:
```c++
#include <iostream>
using namespace std;
// 折半查找插入位置
int binarySearch(int arr[], int left, int right, int target) {
int mid;
while (left <= right) {
mid = (left + right) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
// 折半插入排序
void binaryInsertSort(int arr[], int n) {
int i, j, target, pos;
for (i = 1; i < n; i++) {
target = arr[i];
pos = binarySearch(arr, 0, i - 1, target);
for (j = i - 1; j >= pos; j--) {
arr[j + 1] = arr[j];
}
arr[pos] = target;
}
}
int main() {
int n, i;
cout << "请输入记录数:";
cin >> n;
int arr[n];
cout << "请输入各记录元素数据项的值:";
for (i = 0; i < n; i++) {
cin >> arr[i];
}
binaryInsertSort(arr, n);
cout << "排序后的记录为:";
for (i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
```
运行结果如下:
```
请输入记录数:8
请输入各记录元素数据项的值:5 9 1 4 7 3 6 8
排序后的记录为:1 3 4 5 6 7 8 9
```