有序序列插入一个数

#include <stdio.h>
//方法一：二分查找+静态数组（适用于数据量很大的情况）
int main() {
    int n;
    // 读取序列长度，题目限制 n 最大为 50，数组开 51 是为插入元素留空间
    scanf("%d", &n);
    int arr[51];
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    int num;
    scanf("%d", &num);

    // 二分查找确定插入位置
    int left = 0, right = n;
    int pos = n; // 初始设为数组末尾，若 num 比所有元素大，就插在最后
    while (left < right) {
        int mid = left + (right - left) / 2;//防止溢出
        if (arr[mid] >= num) {
            pos = mid;
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    // 元素后移：从数组末尾开始，把插入位置及之后元素依次后移
    for (int i = n; i > pos; i--) {
        arr[i] = arr[i - 1];
    }
    // 插入新元素到 pos 位置
    arr[pos] = num;

    // 输出结果：按顺序打印 N + 1 个有序整数
    for (int i = 0; i <= n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}


//方法2：动态内存+直接遍历（适用于此题，数据量小）

#include <stdio.h>
#include <stdlib.h>

int main() {
    int n;
    scanf("%d", &n);

    // 动态分配初始数组内存
    int* arr = (int*)malloc(n * sizeof(int));
    if (arr == NULL) {
        printf("内存分配失败\n");
        return 1;
    }

    // 读取原始有序序列
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    int num;
    scanf("%d", &num);

    // 动态扩容数组（增加1个元素的空间）
    int* new_arr = (int*)realloc(arr, (n + 1) * sizeof(int));
    if (new_arr == NULL) {
        printf("内存扩容失败\n");
        free(arr); // 释放原始内存，避免泄漏
        return 1;
    }
    arr = new_arr; // 指向扩容后的内存

    // 直接遍历找到插入位置（简单直观，适合数据量不大的场景）
    int pos = n; // 默认插在末尾
    for (int i = 0; i < n; i++) {
        if (arr[i] >= num) {
            pos = i;
            break;
        }
    }

    // 元素后移
    for (int i = n; i > pos; i--) {
        arr[i] = arr[i - 1];
    }

    // 插入元素
    arr[pos] = num;

    // 输出结果
    for (int i = 0; i < n + 1; i++) {
        printf("%d ", arr[i]);
    }

    // 释放动态分配的内存
    free(arr);
    return 0;
}

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;
}

#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;
}

#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;
}

#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;
}

#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;
}

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;
}

#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;
}

#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;
}