首页 > 试题广场 >

有序序列插入一个数

[编程题]有序序列插入一个数

热度指数：25504 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

有一个有序数字序列，从小到大排序，将一个新输入的数插入到序列中，保证插入新数后，序列仍然是升序。

输入描述:

第一行输入一个整数(0≤N≤50)。

第二行输入N个升序排列的整数，输入用空格分隔的N个整数。

第三行输入想要进行插入的一个整数。

输出描述:

输出为一行，N+1个有序排列的整数。

示例1

输入

5
1 6 9 22 30
8

输出

1 6 8 9 22 30

算法知识视频讲解

Anout

int main() {
    int n, m;
    scanf("%d", &n);
    int arr[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    scanf("%d", &m);

    int end = n;
    int i = 0, j = 0;
    for (i = 0; i < n; i++) {
        if (m >= arr[i] && m < arr[i + 1]) {
            for (j = end; j > i; j--) {
                arr[j + 1] = arr[j];
            }
            arr[i + 1] = m;
            break;
        } else if (m > arr[n - 1]) {
            arr[end] = m;
        } else if (m < arr[0]) {
            for (j = end; j >= 0; j--) {
                arr[j + 1] = arr[j];
            }
            arr[0] = m;
        }
    }

    for (int i = 0; i < n + 1; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

发表于 2024-08-08 10:58:52 回复(0)

徐文达

#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>
#include <malloc.h>

int main()
{
    int n = 0;
    int same_n = 0;
    int* p = NULL;
    int tem = 0;
    int i = 0;

    scanf("%d", &n);

    //开辟空间，用来存放数组
    p = (int*)malloc(sizeof(int) * (n + 1));
    if (!p)
    {
        perror("malloc");
        return 1;
    }

    //录入有序数组
    for (i = 0; i < n; i++)
    {
        scanf("%d", p + i);
    }

    //录入待插入的整数
    scanf("%d", &tem);

    //寻找待插入的位置
    for (i = 0; i < n; i++)
    {
        if (tem < *(p + i))
        {
            //此时的i，就是tem应该在数组里的位置（下标）
            break;
        }
    }

    //进行插入操作
    same_n = n;
    while (same_n != i)
    {
        //数组从后往前拉
        *(p + same_n) = *(p + same_n - 1);
        same_n--;
    }
    *(p + i) = tem;

    //输出结果
    for (i = 0; i <= n; i++)
    {
        printf("%d ", *(p + i));
    }

    //释放空间
    free(p);
    p = NULL;
    
    return 0;
}

编辑于 2024-03-19 14:07:24 回复(0)

夜雨潇湘人断肠

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int main()
{
    int n = 0;
    scanf("%d", &n);
    int arr[100] = { 0 };
    int b = 0;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);

    }
    scanf("%d", &b);
    for (int i = 0; i < n;i++)
    {
        int j = 0;
        for (j = 0; j < n - i-1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                int tmp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = tmp;
            }
        }
    }
    if (n == 1)
    {
        if (b > arr[0])
        {
            printf("%d %d", arr[0], b);
        }
        else
        {
            printf("%d %d", b, arr[0]);
        }
    }
    else
    {
        if (b < arr[0])
        {
            printf("%d ", b);
        }
        for (int i = 0; i < n; i++)
        {
            printf("%d ", arr[i]);
            if (b > arr[i] && b < arr[i + 1])
            {
                printf("%d ", b);
            }
        }
        if (b > arr[n - 1])
            {
                printf("%d ", b);
            }
    }
    return 0;
}

编辑于 2024-01-22 20:56:28 回复(1)

阿明a_6

#include <stdio.h>

int main() {
    int n = 0;
    int arr[60] = {0};
    while (~scanf("%d", &n))//输入有序数的个数
    {
        int i = 0;
        for (i = 0; i < n; i++)
        {
            scanf("%d", &arr[i]);//输入有序数
        }
        int x = 0;
        scanf("%d", &x);//要插入的数
        for (i = 0; i < n; i++) 
        {
            if (x < arr[0]) //当小于此组所有的有序数
            {
                for (i = 0; i < n; i++) 
                {
                    arr[n - i] = arr[n - 1 - i];
                }
                arr[0] = x;

            } 
            else if (x > arr[i] && x < arr[i + 1]) 
            {
                for (int j = n - 1; j > i; j--) 
                {
                    arr[j + 1] = arr[j];
                }
                arr[i + 1] = x;
            } 
            else if (x > arr[n - 1]) //当大于此组有序数的所有数
            {
                arr[n] = x;
            }
        }

        for (int k = 0; k <= n; k++) 
        {
            printf("%d ", arr[k]);
        }
    }
    return 0;
}

发表于 2023-07-14 18:54:27 回复(0)

牛客242206212号

#include <stdio.h>

#include <stdlib.h>

int compar(const void* e1,const void* e2)

{

const int *p1= (const int *)e1;

const int *p2= (const int *)e2;

int value = 0;

value = *p1 > *p2 ? 1 : -1 ;

return value;

}

int main() {

int N = 0;

scanf("%d",&N);

int arr[N] ;

for(int i=0 ; i<N ; i++ )

{

scanf("%d",&arr[i]);

}

int sz = sizeof(arr)/sizeof(arr[0]);

int k = 0;a

scanf("%d",&k);

arr[sz] = k;

qsort(arr, (sz+1), sizeof(arr[0]), compar);

for(int j = 0 ; j < (sz+1) ; j++)

{

printf("%d " , arr[j]);

}

return 0;

}

发表于 2023-03-27 23:47:34 回复(0)

淮安A

#include <stdio.h>

int main() {
    int n = 0, i = 0, temp, ret;
    int arr[52] = {0};
    while (scanf("%d", &n) != EOF) {
        arr[i++] = n; //将所有的数都读入到数组中
        //arr[0] - 数组的个数，arr[arr[0]+1] - 待插入的数
    }
    //将arr[count]的数插入到1～count-1的数组中
    for (i = 1; i <= arr[0]; i++) {
        if (arr[arr[0] + 1] < arr[i]) break;
        //此时i的值为待插入的下标
    }
    ret = arr[arr[0] + 1]; //保存待插入的数
    for (int j = arr[0] + 1; j > i; j--) {
        arr[j] = arr[j - 1];
    }
    arr[i] = ret;
    for (int i = 1; i <= arr[0] + 1; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

发表于 2023-03-14 09:44:19 回复(0)

葬叶

#include <stdio.h>
int main()
{
    int n = 0;
    scanf("%d", &n);
    int arr[n];
    int i = 0;
    for (i = 0; i < n; i++)
    {
        scanf("%d ", &arr[i]);
    }

    int count = 0;
    int flag = 0;
    scanf("%d", &count);
    for (i = 0; i < n; i++)
    {
        if (count < arr[i])
        {
            flag++;
            printf("%d ", count);
            count = arr[n - 1] + 1; //被赋予最大值
        }
        printf("%d ", arr[i]);
    }
    if (flag == 0)  //此时 升序数组只有一个，在打印count;
    {
        printf("%d ", count);
    }

    return 0;
}

发表于 2022-12-12 15:26:52 回复(0)

牛客671537402号

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
void add(int a[],int n)
{
    int c, j;
    for (c = 0; c<=n-1; c++)
    {
        if (a[n-1] > a[c])
        {
            if (a[n-1] < a[c + 1])
            {
                int app;
                for (app = c+1; app<=n-1; app++)
                {
                    int b = a[app];
                    a[app] = a[n-1];
                    a[n-1] = b;
                }
            }

        }
        else if(a[c]>a[n-1]){
            int app;
            for (app = 0; app <= n-1; app++)
            {
                int b = a[app];
                a[app] = a[n-1];
                a[n-1] =b;
            }
        }
    }
}
void print(int arr[],int n)
{
    int a;
    for (a = 0; a < n+1; a++)
    {
        printf("%d ", arr[a]);
    }
}

int main()
{
    int n = 0, c = 0, b = 0;
    scanf("%d", &n);
    int arr[10] = { 0 };
    for (c = 0; scanf("%d", arr + c)!=EOF; c++)
    {
        if (c == n-1)break;
    }
    scanf("%d", &b);
    arr[n] = b;
    add(arr,n+1);
    print(arr,n);
    return 0;
}

发表于 2022-09-13 23:13:12 回复(0)

IT_NunU

int main()
{
	int n = 0;
	int arr[50] = { 0 };
	scanf("%d", &n);
	int i = 0;
	int a = 0;
	for ( i = 0; i < n; i++)
	{
		scanf("%d", arr + i);
	}
	scanf("%d", &a);
	arr[n] = a;

	for (i = n; i > 0; i--)
	{
		if (arr[i]< arr[i-1])
		{
			int temp = arr[i];
			arr[i] = arr[i - 1];
			arr[i - 1] = temp;
		}
		else
		{
			break;
		}
	}
	for (i = 0; i < n + 1; i++)
	{
		printf("%d ", arr[i]);
	}

	return 0;
}

发表于 2022-08-12 15:07:21 回复(0)

牛客750631111号

#include <stdio.h>
void bubble_sort(int arr[], int sz)
{
    int i = 0;
    int j = 0;
    int tmp = 0;
    for (i = 0; i < sz; i++)
    {
        for (j = 0; j < sz - i - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
}
int main()
{
    int N = 0;
    scanf("%d", &N);
    int i = 0;
    int arr[51] = {0};
    for (i = 0; i < N; i++)
        scanf("%d", &arr[i]);
    scanf("%d", &arr[N]);
    bubble_sort(arr, N + 1);
    for (i = 0; i < N + 1; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

发表于 2022-05-06 14:11:31 回复(0)

许愿面试顺利的大老虎很爱看电影

很懒。就直接用qsort了，请见谅

#include<stdio.h>

#include<stdlib.h>
int cmp_int(const void* _a, const void* _b)
{
    int* a = (int*)_a;
    int* b = (int*)_b;
    return *a - *b;
}
int main()
{
    int n;
    scanf("%d", &n);
    int arr[50]={0};
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
    }
    scanf("%d", &arr[n]);
    qsort(arr, n+1, sizeof(arr[0]), cmp_int);
for (int j = 0; j < n + 1; j++)
    {
        printf("%d ", arr[j]);
    }
    return 0;
}

发表于 2022-05-02 14:10:09 回复(0)

会越来越强的哒哒

#include<stdio.h>
int main()
{
int n = 0;
    scanf("%d",&n);
    int arr[50];
    int i = 0;
    for(i = 0;i<n;i++)
    {
        scanf("%d ",&arr[i]);
    }
    int x = 0;
    scanf("%d ",&x);
    int ret = 0;//放被插入位置的原元素
    int j = 0;
    for(i = 0;i<n+1;i++)
    {
        if(x>=arr[i]&&x<=arr[i+1])//找到插入的位置i+1
        {
            for(j = n;j>i;j--)//接下来把这个元素后面的元素都向后挪一个
            {
                arr[j] = arr[j-1];//从最后一个开始挪
            }
            arr[i+1] = x;
            i++;
        }
    }
    if(x<arr[0])
    {
        int j = 0;
        ret = arr[0];
        arr[0] = x;//arr[1]需要空出来
        for(j = n;j>1;j--)//接下来把这个元素后面的元素都向后挪一个
        {
            arr[j] = arr[j-1];//从最后一个开始挪
        }
        arr[1] = ret;//把被插入位置的原元素放进去
    }
    if(x>arr[n-1])
    {
        arr[n] = x;
    }
    for(i = 0;i<=n;i++)
    {
        printf("%d ",arr[i]);
    }
    return 0;
}

发表于 2022-03-09 21:16:37 回复(0)

Tomboy521

#include<stdio.h>
int main(void) {
int n, temp, number;
int arr[50];

scanf("%d", &n); // 接收整数序列中整数的个数
for (int i = 0; i < n; i++) // 接收整数序列中的整数
scanf("%d", &arr[i]);
scanf("%d", &number);

for (int i = 0; i < n - 1; i++) { // 对整个数组进行排序
for (int j = i; j < n; j++) {
if (arr[i] > arr[j]) { // 冒泡排序，如果前面的数比后面的大则交换位置
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}

temp = -1; // 重新赋值temp，令它== -1 如果temp一直等于-1说明数列中没有一个值比number大
for (int i = 0; i < n; i++) { // 循环拿数arr[i]与number比较
if (number < arr[0]) // 如果number比arr[0]还小，则原数列每个向后移动一位，arr[0] = number
temp = 0;
else if (arr[i] > number) { // 如果存在arr[i] > number，则移动后arr[i] = number,temp为arr的索引即i
temp = i;
break;
}
}
if (temp == -1) {
arr[n] = number; // 原数列没有一个值大于number，number直接添加到原数列的末尾
}
else {
for (int i = n - 1; i >= temp; i--) { // 原数列存在一个或多个大于number的值，把number放在新数列的temp索引下
arr[i+1] = arr[i]; // 每一位大于number的值都后移一位
}
arr[temp] = number; // number插入新数列的置空的位置
}

for (int i = 0; i < n + 1; i++) { // 打印出插入number后的新数列
printf("%d", arr[i]);
if (i != n) // 如果没有打印到最后一个数字，则每打印一个数字跟着再打印一个空格
printf(" ");
}

return 0;
}

发表于 2022-02-05 16:25:11 回复(3)

六子的猫猫会后空翻

这道题理论上可以先定义一个 n+1 的数组，先把所有数都接收到，随后再进行排序，但是由于排序的开销更大。所以推荐还是使用数组后移的思路来做。

#include <stdio.h>

int main(void)
{
    int num, n, index;
    scanf("%d", &n);
    int arr[n + 1];
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
    scanf("%d", &num);
    n++;
    for (int i = 0; i < n; i++)
    {
        if (arr[i] > num)
        {
            index = i;
            break;
        }
    }
    for (int i = n; i > index; i--)
        arr[i] = arr[i - 1];
    arr[index] = num;
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}

发表于 2022-01-09 21:25:07 回复(0)

阿金要努力

#include<stdio.h>
int main()
{
	int b = 0;
	int c[100] = { 0 };
	scanf("%d", &b);//输入一个数，表示一共有b个数；
	for (int i = 0; i < b; i++)
	{
		scanf("%d", &c[i]);//输入一个有序数组
	}
	int a = 0;
	scanf("%d", &a);
	for (int i = b; i >=0; i--)//从最后一个开始比较
	{
		if (a>c[i-1])
		{
			c[i] = a;//如果大于最后一个数，直接赋值，程序循环结束，打印数组
			break;
		}
		else
		{//如果小，那就交换
			c[i] = c[i - 1];
			c[i - 1] = a;
		}
	}
	for (int i = 0; i < b + 1; i++)//打印最后的数组
	{
		printf("%d ", c[i]);
	}
	return 0;
}

发表于 2021-12-25 21:13:04 回复(0)