在一个有序序列中,输入一个数,将该数插入在正确的位置,使得插入后的序列依然有序。用c语言写
时间: 2024-10-12 10:09:07 浏览: 5
在C语言中,你可以使用二分查找算法找到合适的位置,然后插入给定的数,保持数组的有序性。这里是一个简单的示例,假设数组是升序排列:
```c
#include <stdio.h>
#include <stdlib.h>
// 二分查找函数
int binarySearch(int arr[], int low, int high, int key) {
if (high >= low) {
int mid = low + (high - low) / 2;
if (arr[mid] == key)
return mid;
if (arr[mid] > key)
return binarySearch(arr, low, mid - 1, key);
return binarySearch(arr, mid + 1, high, key);
}
// 如果找不到则返回数组末尾的插入位置
return high;
}
// 插入元素到有序数组
void insertSorted(int arr[], int n, int key) {
int index = binarySearch(arr, 0, n - 1, key);
memmove(arr + index + 1, arr + index, sizeof(arr[0]) * (n - index)); // 移动元素
arr[index] = key; // 插入元素
n++; // 更新数组长度
printf("元素 %d 已经成功插入到位置 %d\n", key, index);
}
// 打印数组
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {1, 3, 5, 6, 8, 9}; // 示例数组
int n = sizeof(arr) / sizeof(arr[0]); // 数组长度
int key = 7; // 要插入的元素
// 先打印原始数组
printf("Original array is: ");
printArray(arr, n);
// 插入元素
insertSorted(arr, n, key);
// 再次打印排序后的数组
printf("After insertion, the sorted array is: ");
printArray(arr, n);
return 0;
}
```
当你运行这段代码时,它会在给定的有序数组中插入指定的元素,并保持数组的有序状态。