已知一个顺序表A,其长度为n,其中的元素按值非递减有序排列，请编写一个算法，该算法功能为插人一个元素X后，保持该顺序表仍按非递减有序排列。该顺序表的存储结构定义如下:

define maxlen 100

struct sqlisttp{

int elem[ maxlen];

int length;

};

typedef struct sqlisttp sqlist;

求算法形式为void insert(sqlist &.A，int x)。

供参考：

void insert(sqlist& A,int x)
{
    int i;
    if (A.length == maxlen) //判断表满
        return;
    for(i = A.length - 1;i >= 0; i--)
        if(A.elem[i] > x)
            A.elem[i+1] = A.elem[i];
        else
            break;
    A.elem[i+1] = x;
    A.length++;
}

可以先找到插入元素X在顺序表中的位置，然后将该位置及其后面的元素向后移动一位，最后将X插入到该位置。

具体实现如下：

void insert(sqlist &A, int x) {
    if (A.length == maxlen) { // 顺序表已满，不能插入
        std::cerr << "顺序表已满，无法插入元素" << x << std::endl;
        return;
    }
    int i = 0;
    while (i < A.length && A.elem[i] <= x) { // 找到插入位置
        ++i;
    }
    for (int j = A.length - 1; j >= i; --j) { // 将该位置及其后面的元素向后移动一位
        A.elem[j+1] = A.elem[j];
    }
    A.elem[i] = x; // 插入X
    ++A.length; // 更新顺序表长度
}

该算法的时间复杂度为$O(n)$，因为需要将插入位置及其后面的元素向后移动一位，最坏情况下需要移动$n-i$个元素。