C++向一个有序数组a中插入一个数据,使其依然保持有序性。如数组a={1,3,5,7,9},插入4后的a是{1,3,4,5,7,9}。
时间: 2023-08-19 19:39:46 浏览: 136
可以使用二分查找的思想来实现有序数组的插入操作。具体步骤如下:
1.利用二分查找找到插入位置的下标,如果数组中已经存在要插入的数据,则直接返回。
2.将插入位置及其后面的数据全部后移一位。
3.将要插入的数据放到插入位置上。
下面是C++代码实现:
```
void insert(int a[], int n, int x) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (a[mid] == x) {
return;
} else if (a[mid] < x) {
left = mid + 1;
} else {
right = mid - 1;
}
}
for (int i = n - 1; i >= left; i--) {
a[i + 1] = a[i];
}
a[left] = x;
}
```
调用该函数可以实现对有序数组的插入操作:
```
int main() {
int a[] = {1, 3, 5, 7, 9};
int n = sizeof(a) / sizeof(int);
int x = 4;
insert(a, n, x);
for (int i = 0; i < n + 1; i++) {
cout << a[i] << " ";
}
return 0;
}
```
输出结果为:1 3 4 5 7 9。