输入一个数插入有序数组中

假设要插入的数为 x，有序数组为 arr，可以采用二分查找的方法找到插入位置，然后将该位置及其后面的所有元素后移一位，最后将 x 插入到该位置。

具体实现如下（使用 Python 语言）：

def insert_to_sorted_array(arr, x):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == x:
            return mid   # 如果 x 已经在数组中，直接返回其位置
        elif arr[mid] < x:
            left = mid + 1
        else:
            right = mid - 1
    # 此时 left 表示应该插入的位置
    for i in range(len(arr)-1, left-1, -1):
        arr[i+1] = arr[i]
    arr[left] = x
    return left

时间复杂度为 O(log n + n)，其中 log n 是二分查找的时间复杂度，n 是移动元素的时间复杂度。

相关问题

输入一个数插入有序数组中的C语言代码

在C语言中，如果你想将一个数插入到已经排序的有序数组中，可以按照二分查找法的思想找到合适的位置，然后将新元素插入。这里是一个简单的示例：

#include <stdio.h>

// 定义一个函数来插入元素
void insert(int arr[], int n, int key) {
    int i; // 遍历索引
    for (i = 0; i < n; i++) { // 当找到比key小的元素或到达数组末尾
        if (arr[i] > key) {
            break;
        }
    }

    // 将元素复制到右侧
    for (int j = n - 1; j >= i; j--) {
        arr[j + 1] = arr[j];
    }

    // 插入key
    arr[i] = key;
}

// 测试函数
void print_array(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {1, 3, 5, 7, 9}; // 示例数组
    int n = sizeof(arr) / sizeof(arr[0]);
    int key = 4; // 要插入的值

    printf("Before insertion:\n");
    print_array(arr, n);

    insert(arr, n, key); // 插入元素

    printf("After insertion with key %d:\n", key);
    print_array(arr, n);

    return 0;
}

这段代码首先找到给定键值应该插入的正确位置，然后将后面的元素向右移动一位以便插入新的元素。请注意，这个实现假设输入数组是升序排列的。

C语言编写：用冒泡排序法对输入的20个数进行降序排序并存入数组中，然后再输入一个数插入该数组中，要求保持原序不变并输出该数组的21个数

在C语言中，我们可以使用冒泡排序算法先对20个数进行降序排序，然后通过二分查找找到合适的位置插入新数，保证数组的有序性。以下是简单的步骤：

首先，创建一个大小为20的整型数组，并读取20个数存入其中。由于是降序排列，每次比较都是较大值与较小值交换。

#include <stdio.h>

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] < arr[j + 1]) {
                // 降序排列，所以这里是大于号
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main() {
    int arr[20], num;
    printf("请输入20个数：\n");
    for (int i = 0; i < 20; i++) {
        scanf("%d", &arr[i]);
    }

    bubbleSort(arr, 20);

    printf("排序后的数组（降序）：\n");
    for (int i = 0; i < 20; i++) {
        printf("%d ", arr[i]);
    }

    printf("\n请输入需要插入的新数：");
    scanf("%d", &num);
    
    // 插入操作
    for (int i = 19; i >= 0; i--) {
        if (arr[i] > num) {
            arr[i + 1] = arr[i];
        } else {
            arr[i + 1] = num;
            break;
        }
    }

    printf("\n插入新数后，数组（包括新数）：\n");
    for (int i = 0; i <= 20; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}

运行程序后，按照提示输入数字，程序会将它们降序排列并显示结果，接着插入新数并保持原序输出整个数组。