C语言实现
方法一：直接遍历插入
这种方法直接遍历数组，找到合适的位置插入新元素，然后移动后续元素。
c复制代码 #include <stdio.h> void insertSorted(int arr[], int *n, int elem) { int i; // 数组扩容（这里假设数组足够大，不进行动态扩容） // 如果需要动态扩容，则需要在函数外部处理 (*n)++; // 从后向前遍历，找到插入位置 for (i = *n - 1; (i > 0 && arr[i - 1] > elem); i--) { arr[i] = arr[i - 1]; } arr[i] = elem; } int main() { int arr[] = {1, 3, 5, 7, 9}; int n = sizeof(arr) / sizeof(arr[0]); int elem = 4; insertSorted(arr, &n, elem); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } return 0; }
方法二：二分查找插入位置
由于数组已排序，可以使用二分查找来找到插入位置，然后插入。
c复制代码 #include <stdio.h> void insertSortedBinary(int arr[], int *n, int elem) { int low = 0, high = *n - 1, mid; // 二分查找插入位置 while (low <= high) { mid = (low + high) / 2; if (arr[mid] == elem) { // 如果元素已存在，则不插入 return; } else if (arr[mid] < elem) { low = mid + 1; } else { high = mid - 1; } } // 数组扩容（这里假设数组足够大） (*n)++; // 插入元素并移动后续元素 for (int i = *n - 1; i > low; i--) { arr[i] = arr[i - 1]; } arr[low] = elem; } int main() { // 示例代码与上述相同 }
Python实现
方法一：直接遍历插入
Python 的列表操作比 C 语言更方便，可以直接使用 insert() 方法。
python复制代码 def insert_sorted(arr, elem): arr.append(float('inf')) # 临时添加一个极大值，简化插入逻辑 i = len(arr) - 2 while arr[i] > elem: arr[i + 1] = arr[i] i -= 1 arr[i + 1] = elem arr.pop() # 移除临时添加的极大值 # 示例 arr = [1, 3, 5, 7, 9] elem = 4 insert_sorted(arr, elem) print(arr)
方法二：二分查找插入位置
Python 的 bisect 模块提供了二分查找的支持，可以直接用于找到插入位置。
python复制代码 from bisect import insort # 示例 arr = [1, 3, 5, 7, 9] elem = 4 insort(arr, elem) print(arr)
这里 insort() 函数直接完成了查找插入位置并插入元素的操作，非常简洁。
