设顺序表 va 中的数据元素递增有序①。试写一算法，将 插入到顺序表的 适当位置上，以保持该表的有序性。‘

### 回答1：
1. 定义变量 i 为 0，j 为 va 的元素个数；
2. 若 j 大于等于 va 的容量 size，则返回插入失败；
3. 若 va 为空，则将 x 直接插入到 va 的第一个位置上；
4. 若 va 不为空，则按照以下步骤进行插入：
1. 若 x 大于 va 的最后一个元素，则将 x 直接插入到 va 的最后一个位置上；
2. 否则，从 va 的第一个元素开始遍历，找到第一个大于等于 x 的元素的位置 i，将 x 插入到该位置上，并将 i 后面的元素依次后移一位；
3. 将 va 的元素个数 j 加 1；
5. 返回插入成功。

### 回答2：
算法描述如下：
1. 初始化变量low为0，high为表的长度减1；
2. 若low大于high，则将元素插入到low位置上，即将low及其后的元素依次后移一位，并将值插入到low位置上；
3. 否则，令mid等于low和high的平均值；
4. 若要插入的值小于等于mid位置上的元素值，则将high更新为mid-1，并返回步骤2；
5. 否则，将low更新为mid+1，并返回步骤2。

算法实现：

def insert_element(va, x):
    low, high = 0, len(va)-1
    while low <= high:
        mid = (low + high) // 2
        if x <= va[mid]:
            high = mid - 1
        else:
            low = mid + 1
    va.insert(low, x)

时间复杂度分析：该算法采用二分查找的思想，在有序表中插入元素，最坏情况下需要比较log2(n)次，其中n为表的长度。因此，该算法的时间复杂度为O(log n)。

例如，若有序表va为[1, 3, 5, 7, 9]，要插入的元素为4，则按照算法执行过程：
1. 初始low=0，high=4；
2. mid=(0+4)//2=2，mid位置上的元素为5；
3. 4<=5，因此high=2-1=1；
4. low=0，high=1；
5. mid=(0+1)//2=0，mid位置上的元素为1；
6. 4>1，因此low=0+1=1；
7. low=1，high=1；
8. mid=(1+1)//2=1，mid位置上的元素为3；
9. 4>3，因此low=1+1=2；
10. low=2，high=1，退出循环；
11. 将4插入到low位置上，即[1, 3, 4, 5, 7, 9]。

### 回答3：
算法如下：
1. 定义一个指针 i=0，用于遍历顺序表 va。
2. 当 i 小于顺序表的长度并且 va[i] 小于等于插入元素时，将指针 i 加 1。
3. 插入元素的下标设为 insert_index。
4. 若 i 等于顺序表长度，说明插入元素大于顺序表中的所有元素，将插入元素加到顺序表末尾。
5. 否则，从顺序表的末尾开始，将索引大于等于 insert_index 的元素往后移一位。
6. 将插入元素插入到 insert_index 位置。
7. 输出插入成功的提示信息。

示例代码如下：

def insert_ordered_list(va, num):
    i = 0
    while i < len(va) and va[i] <= num:
        i += 1
    insert_index = i
    if i == len(va):
        va.append(num)
    else:
        va.append(None)
        for j in range(len(va)-1, insert_index, -1):
            va[j] = va[j-1]
        va[insert_index] = num
    print("插入成功！")

# 测试
va = [1, 2, 4, 5, 6]
num = 3
insert_ordered_list(va, num)
print(va)  # 输出 [1, 2, 3, 4, 5, 6]

该算法的时间复杂度为 O(n)，其中 n 是顺序表的长度。