适合个人做的网站,学生怎样建设网站,网站建设解决方案好处,中国商标网官方查询在一个升序数组中插入一个数仍升序输出
题目举例#xff1a; 有一个升序数组nums#xff0c;给一个数字data#xff0c;将data插入数组nums中仍旧保证nums升序#xff0c;返回数组中有效元素个数。 比如#xff1a;nums[100] {1, 2, 3, 5, 6, 7, 8, 9} size 8 data 4 …在一个升序数组中插入一个数仍升序输出
题目举例 有一个升序数组nums给一个数字data将data插入数组nums中仍旧保证nums升序返回数组中有效元素个数。 比如nums[100] {1, 2, 3, 5, 6, 7, 8, 9} size 8 data 4 插入之后nums为{1, 2, 3, 4, 5, 6, 7, 8, 9} 返回 size 9 方法一插入排序
1.1方法解析 1.遍历数组nums找到第一个大于等于data的元素位置index。 2.将index及其之后的元素都往后移动一位腾出位置给数据。 3.将data插入到index位置。 4.size加1。 1.2函数实现
int insertIntoArray(int nums[], int size, int data) {int i, index;// 找到第一个大于等于data的元素位置for (i 0; i size; i) {if (nums[i] data) {index i;break;}}// 将index及其之后的元素都往后移动一位for (i size - 1; i index; i--) {nums[i 1] nums[i];}// 将data插入到index位置nums[index] data;// size加1size;1.3实际代入
void insertIntoArray(int nums[], int size, int data) {int i, index;// 找到第一个大于等于data的元素位置for (i 0; i size; i) {if (nums[i] data) {index i;break;}}// 将index及其之后的元素都往后移动一位for (i size - 1; i index; i--) {nums[i 1] nums[i];}// 将data插入到index位置nums[index] data;// size加1size;
for (int i 0; i size; i){printf(%d , nums[i]);}printf(\n);printf(size %d, size);
}
int main()
{int nums[100] { 1,2,3,5,6,7,8,9 };int size 8;printf(插入前);for (int i 0; i size; i){printf(%d , nums[i]);}printf(\nsize %d\n, size);int data 0;scanf(%d, data);printf(插入后);Inserdata(nums, size, data);return 0;}1.4运行结果举例 方法二 二分查找插入排序
2.1方法解析 首先初始化两个指针和分别指向数组的起始和结束位置。然后进行循环直到大于等于为止。在每一次循环中计算中间位置并将中间元素与要插入的值进行比较。leftrightleftrightmid 如果中间元素大于要插入的值说明要插入的值在左半部分将指针更新为 如果中间元素小于要插入的值说明要插入的值在右半部分将指针更新为 如果中间元素等于要插入的值说明要插入的值已rightmid-1leftmid1 最终当大于时并将要插入的值放入该位置即可。返回数组大小加1。leftright 2.2函数实现
void Inserdata(int nums[], int size, int data) //方法二二分法查找插入排序
{int left 0;int right size - 1;while (left right){int mid (left right) / 2;int midvalue nums[mid];if (nums[mid] data)//找到中间数和data对比{left mid 1;}else{right mid - 1;}}for (int i size - 1; i left; i--){nums[i 1] nums[i];}nums[left] data;size;for (int i 0; i size; i){printf(%d , nums[i]);}printf(\n);printf(size %d, size);
}2.3实际代入
void Inserdata(int nums[], int size, int data) //方法二二分法查找插入排序
{int left 0;int right size - 1;while (left right){int mid (left right) / 2;int midvalue nums[mid];if (nums[mid] data){left mid 1;}else{right mid - 1;}}for (int i size - 1; i left; i--){nums[i 1] nums[i];}nums[left] data;size;for (int i 0; i size; i){printf(%d , nums[i]);}printf(\n);printf(size %d, size);
}
int main()
{int nums[100] { 1,2,3,5,6,7,8,9 };int size 8;printf(插入前);for (int i 0; i size; i){printf(%d , nums[i]);}printf(\nsize %d\n, size);int data 0;scanf(%d, data);printf(插入后);Inserdata(nums, size, data);return 0;
}2.4运行结果举例 方法三 依次次对比
3.1方法解析 1.数组为升序 2在数组中找待插入元素的位置具体找的方式为 3.从后往前依次与数组中元素进行比较如果要插入元素num比end位置数据小则num一定插在end位置之前 4.因此将end位置数据往后搬移一个位置 5.如果num大于end位置元素或者end已经在区间最左侧则位置找到/ 最后将新元素插入到end1的位置 3.2函数实现
void Inserdata(int nums[], int size, int data) //方法三依次对比
{int end size - 1;while (end 0 data nums[end]){nums[end 1] nums[end];end--;}nums[end 1] data;// 返回插入之后数组中有效元素个数size;for (int i 0; i size; i){printf(%d , nums[i]);}printf(\n);printf(size %d, size);
}3.3实际代入
void Inserdata(int nums[], int size, int data) //方法三依次对比
{int end size - 1;while (end 0 data nums[end]){nums[end 1] nums[end];end--;}nums[end 1] data;// 返回插入之后数组中有效元素个数size;for (int i 0; i size; i){printf(%d , nums[i]);}printf(\n);printf(size %d, size);
}
int main()
{int nums[100] { 1,2,3,5,6,7,8,9 };int size 8;printf(插入前);for (int i 0; i size; i){printf(%d , nums[i]);}printf(\nsize %d\n, size);int data 0;scanf(%d, data);printf(插入后);Inserdata(nums, size, data);return 0;
}3.4运行结果举例
