用c语言写 设线性表的数据元素都为整数，存放在顺序表 S 中且递增有序。设计算法，将 x 插入 到顺序表 S 的适当位置上，以保持线性表的有序性。要求算法的时间复杂度为 O(n)，空间复 杂度为 O(1)。

为了在C语言中实现将整数`x`插入到递增有序的顺序表`S`中并保持有序性，你可以采用以下算法：

1. **初始化顺序表**[^1]:
- 创建一个动态数组表示顺序表。

2. **插入操作**[^2]:
- 输入新元素`x`。
- 使用一个指针`i`从后向前遍历顺序表，直到找到第一个大于等于`x`的元素或者到达表头。

   int *ptr = &S[strlen(S)]; // 指向顺序表末尾
   while (ptr > S && *ptr >= x) { // 当前元素大于等于x时
       ptr--; // 移动指针
   }

3. **插入新元素**:
- 在`ptr`指向的位置插入`x`。

   memmove(ptr + 1, ptr, (strlen(S) - ptr) * sizeof(int)); // 向右移动其他元素
   *ptr = x; // 插入x

4. **更新长度**:
- 更新顺序表的长度。

   strlen(S)++;

完整示例代码如下：

#include <stdio.h>
#include <string.h>

void insertInOrder(int* S, int n, int x) {
    if (n == 0 || x <= S[n- 1;
    while (i >= 0 && S[i] >= x) {
        S[i+1] = S[i];
        i--;
    }
    S[i+1] = x;
}

int main() {
    int S[] = {1, 3, 5, 7, 9}; // 示例顺序表
    int n = sizeof(S) / sizeof(S[0]);
    int x = 4;

    insertInOrder(S, n, x);
    
    printf("Sorted array after insertion: ");
    for (int i = 0; i <= n; i++) {
        printf("%d ", S[i]);
    }
    printf("\n");

    return 0;
}