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

在C++中，要实现在顺序表S中插入整数x并保持递增有序，可以采用双指针法。以下是步骤：

1. 定义一个指向当前遍历位置的指针`i`，初始化为0，表示从表头开始。

2. 另外定义一个指向插入点的指针`j`，初始值为0，表示未找到插入位置。

3. 进行循环遍历，直到`i`等于`S`的长度或`S[i] <= x`成立：
- 比较`S[i]`和`x`，如果`S[i] > x`，说明找到了合适的位置，在`i+1`处插入，并结束循环。因为数组索引是从0开始的，所以`S[i+1]`就是插入位置。
- 如果`S[i] <= x`，则移动`i`向前一位，继续比较。

4. 插入操作：将`x`放入`S[j]`的位置，即`S[j] = x`。

5. 更新`j`，使其加1，`j = i + 1`。

6. 遍历结束后，整个序列保持递增有序。

void insertSorted(int S[], int n, int x) {
    if (n == 0 || x <= S[0]) {
        // 如果列表为空或者x小于等于第一个元素，直接插入第一个位置
        S[0] = x;
    } else {
        for (int i = 0; i < n && S[i] < x; ++i) {
            // 找到插入位置并插入
        }
        // 在i+1位置插入
        S[i + 1] = x;
    }
}