龙岩市网站建设,济南建行网点,wordpress 企业主模板,广州越秀区最新通知题目:有一个已经排好序的数组。现输入一个数#xff0c;要求按原来的规律将它插入数组中。
程序分析
要将一个数插入已经排好序的数组中#xff0c;我们可以采用以下步骤#xff1a;
遍历数组#xff0c;找到第一个大于待插入数的位置。将待插入数插入到该位置#xff…题目:有一个已经排好序的数组。现输入一个数要求按原来的规律将它插入数组中。
程序分析
要将一个数插入已经排好序的数组中我们可以采用以下步骤
遍历数组找到第一个大于待插入数的位置。将待插入数插入到该位置同时将该位置后面的元素依次后移一位。
下面我们将使用三种不同的方法来实现这个任务并分析它们的优缺点。
方法一插入排序
解题思路
插入排序是一种简单的排序算法适用于已经部分有序的数组。我们可以利用插入排序的思想来解决这个问题。
实现代码
#include stdio.hvoid insertSorted(int arr[], int size, int num) {int i, j;for (i 0; i size; i) {if (arr[i] num) {for (j size - 1; j i; j--) {arr[j 1] arr[j];}arr[i] num;break;}}
}int main() {int arr[] {1, 3, 5, 7, 9};int size sizeof(arr) / sizeof(arr[0]);int num 4;printf(Original Array: );for (int i 0; i size; i) {printf(%d , arr[i]);}insertSorted(arr, size, num);size;printf(\nArray after insertion: );for (int i 0; i size; i) {printf(%d , arr[i]);}return 0;
}优缺点
优点
简单易懂容易实现。对于小规模数组或已经基本有序的数组性能较好。
缺点
对于大规模数组性能较差时间复杂度为O(n^2)。
方法二二分查找 插入
解题思路
我们可以使用二分查找来快速找到待插入数的位置然后再进行插入操作。
实现代码
#include stdio.hint binarySearch(int arr[], int left, int right, int num) {while (left right) {int mid left (right - left) / 2;if (arr[mid] num) {return mid;} else if (arr[mid] num) {left mid 1;} else {right mid - 1;}}return left;
}void insertSorted(int arr[], int size, int num) {int pos binarySearch(arr, 0, size - 1, num);for (int i size - 1; i pos; i--) {arr[i 1] arr[i];}arr[pos] num;
}int main() {int arr[] {1, 3, 5, 7, 9};int size sizeof(arr) / sizeof(arr[0]);int num 4;printf(Original Array: );for (int i 0; i size; i) {printf(%d , arr[i]);}insertSorted(arr, size, num);size;printf(\nArray after insertion: );for (int i 0; i size; i) {printf(%d , arr[i]);}return 0;
}优缺点
优点
较方法一更高效时间复杂度为O(log n)。适用于大规模数组。
缺点
实现稍微复杂一些。
方法三使用标准库函数
解题思路
我们可以使用C标准库函数bsearch来进行二分查找然后使用memmove函数来移动元素实现插入操作。
实现代码
#include stdio.h
#include stdlib.h
#include string.hint compare(const void *a, const void *b) {return (*(int *)a - *(int *)b);
}void insertSorted(int arr[], int *size, int num) {int *pos (int *)bsearch(num, arr, *size, sizeof(int), compare);if (pos NULL) {pos arr (*size);}memmove(pos 1, pos, (*size - (pos - arr)) * sizeof(int));*pos num;(*size);
}int main() {int arr[] {1, 3, 5, 7, 9};int size sizeof(arr) / sizeof(arr[0]);int num 4;printf(Original Array: );for (int i 0; i size; i) {printf(%d , arr[i]);}insertSorted(arr, size, num);printf(\nArray after insertion: );for (int i 0; i size; i) {printf(%d , arr[i]);}return 0;
}优缺点
优点
使用标准库函数简化了实现。高效时间复杂度为O(log n)。适用于大规模数组。
缺点
对C标准库的依赖可能不适用于嵌入式系统等环境。
总结
对于小规模数组或者已经基本有序的数组方法一插入排序是一个简单且直观的选择。但是对于大规模数组它的性能较差。
方法二二分查找插入在大规模数组中性能更好时间复杂度为O(log n)适用于大型数据集。
方法三使用标准库函数也具有高效的性能同时简化了实现但需要依赖C标准库。
综合考虑方法二和方法三都是不错的选择具体取决于项目需求和对性能的要求。如果对性能要求较高且可以使用标准库函数那么方法三是一个不错的
