在一个已按升序排列的数组中插入一个数,插入后,数组元素仍按升序排列,已知升序数组{1, 2, 4, 6, 8, 9, 12, 15, 149, 156 }的代码注释c语言
时间: 2024-09-15 11:12:18 浏览: 25
在C语言中,你可以使用二分查找法找到插入位置,并保持数组有序。以下是一个简单的示例代码,假设`arr[]`是你给出的数组,`num`是要插入的数:
```c
#include <stdio.h>
// 二分查找函数,返回值为需要插入的位置(索引),如果num比所有元素都大则返回数组长度
int binary_search(int arr[], int low, int high, int num) {
if (high >= low) {
int mid = low + (high - low) / 2;
// 如果中间元素大于等于num,则在左半部分查找
if (arr[mid] == num)
return mid;
else if (arr[mid] > num)
return binary_search(arr, low, mid - 1, num); // 在左半边递归查找
else
return binary_search(arr, mid + 1, high, num); // 在右半边递归查找
}
// 如果遍历结束还没找到插入点,说明应该在末尾添加
return low;
}
// 主函数插入操作
void insert_sorted(int arr[], int n, int num) {
int index = binary_search(arr, 0, n - 1, num);
// 将num插入到数组相应位置
for (int i = n; i > index; i--) {
arr[i] = arr[i - 1];
}
arr[index] = num; // 插入num
}
// 测试函数
int main() {
int arr[] = {1, 2, 4, 6, 8, 9, 12, 15, 149, 156};
int n = sizeof(arr) / sizeof(arr[0]);
int num = 10; // 要插入的数字
printf("Original array:\n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
insert_sorted(arr, n, num);
printf("\nArray after insertion of %d:\n", num);
for (int i = 0; i <= n; i++)
printf("%d ", arr[i]); // 注意这里是n+1,因为包括了新插入的元素
return 0;
}