【数据结构陈越版笔记】基础实验1-2.1：有序数组的插入

我这答案做的可能不对，如果不对，欢迎大家指出错误，思路大部分直接写在注释中了。

基础实验1-2.1：有序数组的插入

本题要求将任一给定元素插入从大到小排好序的数组中合适的位置，以保持结果依然有序。

函数接口定义：

bool Insert( List L, ElementType X );

其中List结构定义如下：

typedef int Position;
typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last; /* 保存线性表中最后一个元素的位置 */
};

L是用户传入的一个线性表，其中ElementType元素可以通过>、==、<进行比较，并且题目保证传入的数据是递减有序的。函数Insert要将X插入Data[]中合适的位置，以保持结果依然有序（注意：元素从下标0开始存储）。但如果X已经在Data[]中了，就不要插入，返回失败的标记false；如果插入成功，则返回true。另外，因为Data[]中最多只能存MAXSIZE个元素，所以如果插入新元素之前已经满了，也不要插入，而是返回失败的标记false。

裁判测试程序样例：

#include 
#include 

#define MAXSIZE 10
typedef enum {false, true} bool;
typedef int ElementType;

typedef int Position;
typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last; /* 保存线性表中最后一个元素的位置 */
};

List ReadInput(); /* 裁判实现，细节不表。元素从下标0开始存储 */
void PrintList( List L ); /* 裁判实现，细节不表 */
bool Insert( List L, ElementType X );

int main()
{
    List L;
    ElementType X;

    L = ReadInput();
    scanf("%d", &X);
    if ( Insert( L, X ) == false )
        printf("Insertion failed.\n");
    PrintList( L );

    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例1：

5
35 12 8 7 3
10

输出样例1：

35 12 10 8 7 3
Last = 5

思路与答案

通过输入样例得知，第一行是输入数组长度，第二行是数组元素，第三行是待插入的值

方法一：暴力法找到下标后再移动元素

bool Insert(List L, ElementType X)
{
    //插入失败，数组满了
    if(L->Last + 1 == MAXSIZE)
    {
        return false;
    }
    //暴力法找到要插入元素的下标
    Position index = -1;
    //递减顺序，找到第一个小于X的元素对应的下标，就是其待插入的元素的下标，然后跳出循环
    for(int i = 0;i <= L->Last;i++)
    {
        //如果遇到和X相等的，说明重复插入，返回false
        if(X == L->Data[i])
        {
            return false;
        }
        if(X > L->Data[i])
        {
            index = i;
            break;
        }
    }
    //如果下标是-1，则说明所有元素都大于X，最后位置插入
    if(index == -1)
    {
        L->Data[L->Last + 1] = X;
    }
    else
    {
        //其他情况，需要依次向右移动
        for(int i = L->Last + 1; i>index ;i--)
        {
            L->Data[i] = L->Data[i-1];
        }
        //最后给腾出位置的index那儿赋值后
        L->Data[index] = X;
    }
    //last自增（数组长度增加）
    L->Last++;
    return true;
}

方法二：先用二分法查找待插入的下标，然后再移动元素

bool Insert(List L, ElementType X)
{
    //插入失败，数组满了
    if(L->Last + 1 == MAXSIZE)
    {
        return false;
    }
    //二分查找找到插入位置
    Position left = 0;
    Position right = L->Last;
    Position middle = 0;
    //左闭右闭
    while(left<=right)
    {
        middle = (right + left) >> 1;//二分
        //X已经在L->Data中，不插入
        if(L->Data[middle] == X)
        {
            return false;
        }
        else if(L->Data[middle] < X)
        {
            right = middle - 1; //向左查找
        }
        else
        {
            left = middle + 1;
        }
    }
    //最后left是要插入的下标，从最后+1（闭）到left（开），元素依次向后移动一个
    for(int i = L->Last + 1; i>left ;i--)
    {
        L->Data[i] = L->Data[i-1];
    }
    //最后给腾出位置的left那儿赋值后，last自增（数组长度增加）
    L->Data[left] = X;
    L->Last++;
    return true;
}

至于left为何是最后插入位置，详见【代码随想录刷题记录】LeetCode35搜索插入位置

时间复杂度

方法一时间复杂度是$O(N)$，方法二查找部分的时间复杂度为$O(logN)$，插入部分还是$O(N)$，最后总的时间复杂度还是$O(logN)+O(N)=O(N)$

实验思考题

如果修改题目要求，允许重复的数字插入，则两种方法的效率是否还有区别？哪种方法在何种情况下比较快？
【答】如果允许重复插入，就改一下条件，把暴力法中的

//如果遇到和X相等的，说明重复插入，返回false
        if(X == L->Data[i])
        {
            return false;
        }

去掉，然后将下面的条件修改为：

		if(X >= L->Data[i])
        {
            index = i;
            break;
        }

时间复杂度还是$O(N)$
二分法中，改成：

		if(L->Data[middle] == X)
        {
            left = middle;
        }

时间复杂度还是$O(N)$