Question

设线性表存放在向量 A [ arrsize ］的前 elenum 个分量中，且递增有序。试写一算法，将 x 插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。

Answer 1

问：设线性表存放在向量 A [ arrsize ］的前 elenum 个分量中，且递增有序。试写一算法，将 x 插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。

答：算法如下：1. 如果线性表已满，则返回错误信息。2. 从线性表的最后一个元素开始向前遍历，找到第一个小于等于 x 的元素位置 i。3. 将 A[i+1] 到 A[elenum] 的所有元素向后移动一个位置，为 x 腾出空间。4. 将 x 插入到位置 i+1 上。5. elenum 加 1，表示线性表长度增加了一个。时间复杂度分析：在最坏情况下，需要将 x 插入到线性表的第一个位置上，此时需要将所有元素都向后移动一位。因此，时间复杂度为 O(n)。在平均情况下，需要移动 n/2 个元素，因此时间复杂度为 O(n/2)，即 O(n)。