【在一个升序数组中插入一个数仍升序输出】

这篇具有很好参考价值的文章主要介绍了【在一个升序数组中插入一个数仍升序输出】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

在一个升序数组中插入一个数仍升序输出

题目举例:

有一个升序数组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加1
    size++;
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加1
    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;

}
1.4运行结果举例

【在一个升序数组中插入一个数仍升序输出】,C语言,# 循环,#排序,c语言

方法二 :二分查找插入排序

2.1方法解析

首先,初始化两个指针和分别指向数组的起始和结束位置。然后进行循环,直到大于等于为止。在每一次循环中,计算中间位置,并将中间元素与要插入的值进行比较。leftrightleftrightmid
如果中间元素大于要插入的值,说明要插入的值在左半部分,将指针更新为;
如果中间元素小于要插入的值,说明要插入的值在右半部分,将指针更新为;
如果中间元素等于要插入的值,说明要插入的值已rightmid-1leftmid+1
最终,当大于时,并将要插入的值放入该位置即可。返回数组大小加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运行结果举例

【在一个升序数组中插入一个数仍升序输出】,C语言,# 循环,#排序,c语言

方法三 依次次对比

3.1方法解析

1.数组为升序
2在数组中找待插入元素的位置,具体找的方式为
3.从后往前依次与数组中元素进行比较,如果要插入元素num比end位置数据小,则num一定插在end位置之前
4.因此将end位置数据往后搬移一个位置
5.如果num大于end位置元素或者end已经在区间最左侧,则位置找到/ 最后将新元素插入到end+1的位置

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运行结果举例

【在一个升序数组中插入一个数仍升序输出】,C语言,# 循环,#排序,c语言文章来源地址https://www.toymoban.com/news/detail-637178.html

到了这里,关于【在一个升序数组中插入一个数仍升序输出】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包