32.有序序列插入一个整数（刷题）

描述

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

输入描述：

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

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

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

输出描述：

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

解法思想： 

1. 首先在 insertnum 函数中，使用一个循环遍历已排序的整数序列，找到第一个大于新数的位置。通过比较当前元素和新数的大小，如果当前元素大于新数，则跳出循环，得到插入位置 i。

2. 然后使用另一个循环，从序列的最后一个元素开始，将每个元素后移一位，为新数腾出插入位置。

3. 最后将新数插入到找到的位置 i。

4. 在主函数 main 中，首先读取整数 n，表示待插入的整数序列的长度。然后声明一个整数数组 arr，用于存储输入的整数序列。接着使用循环逐个读取整数序列中的元素。

5. 读取整数 num，表示要插入的新数。调用 insertnum 函数将新数插入到整数序列中。

6. 最后使用循环打印整数序列，包括插入后的结果。

#include <stdio.h>

void insertnum(int arr[], int n, int num) {
    int i, j;

 // 寻找插入位置
    for (i = 0; i < n; i++) {
        if (arr[i] > num){
            break;
        }
    }

// 后移元素腾出插入位置
    for (j = n - 1; j >= i; j--) {
        arr[j + 1] = arr[j];
    }

 // 插入新数
    arr[i] = num;
}

int main() {
    int n, num;
    scanf("%d", &n);// 读取已排序序列的元素个数
    int arr[n];

    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);// 读取已排序序列的元素
    }

    scanf("%d", &num);// 读取新输入的数
 // 插入新数并保持升序
    insertnum(arr, n, num);

// 输出插入后的有序序列
    for (int i = 0; i <= n; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}

如果要将 arr 改为动态数组，可以使用 malloc 函数动态分配内存空间。下面是修改后的代码示例： 

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

void insertnum(int arr[], int n, int num) {
    int i, j;

    for (i = 0; i < n; i++) {
        if (arr[i] > num) {
            break;
        }
    }

    for (j = n - 1; j >= i; j--) {
        arr[j + 1] = arr[j];
    }

    arr[i] = num;
}

int main() {
    int n, num;
    scanf_s("%d", &n);
    int* arr = (int*)malloc(n * sizeof(int));

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

    scanf_s("%d", &num);
    insertnum(arr, n, num);

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

    return 0;
}