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

在C++中，为了将整数 `x` 插入到递增有序的顺序表 `S` 中并保持有序性，可以采用类似于二分查找的方式找到插入的位置。以下是简单的步骤：

1. 定义两个指针，`left` 和 `right`，初始化为列表的开始（0）和结束（`S.size() - 1`）。

2. 当 `left` 小于等于 `right` 时，继续循环：
a. 计算中间索引 `mid`：`mid = (left + right) / 2`。
b. 比较 `x` 和 `S[mid]` 的大小：
- 如果 `x` 小于 `S[mid]`，说明应该把 `x` 插入到 `mid+1` 到 `right` 之间的某个位置，更新 `right = mid - 1`。
- 否则，如果 `x` 大于等于 `S[mid]`，说明应该把 `x` 插入到 `left` 到 `mid - 1` 之间的某个位置，更新 `left = mid + 1`。

3. 当找到正确位置 `left` 时，将 `S[left]` 移动一位，腾出空位，并将 `x` 放入该位置。

4. 由于插入操作只涉及到一次移动，所以时间复杂度为 O(n)，因为最坏情况下需要遍历整个列表。空间复杂度为 O(1)，因为我们只需要常量级别的额外空间。

以下是伪代码表示上述过程：

void insert(int x, int S[], int n) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (x < S[mid]) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    // Move elements to make space for x
    for (int i = n; i > left; --i) {
        S[i] = S[i - 1];
    }
    S[left] = x;
}