使用cpp语言实现 两个表合并成一个有序表。要求设计两种以上储存方式、两种以上处理流程方式，要求： 抽象数据类型独立实现，写出完整可直接运行的代码并分析各代码性能

一、储存方式

1. 数组储存：将两个表合并后，将所有元素存储到一个数组中，再进行排序。

2. 链表储存：将两个表的元素存储到两个链表中，然后将两个链表合并成一个有序链表。

二、处理流程方式

1. 归并排序：将两个有序表进行归并排序，得到一个有序表。

2. 顺序比较法：将两个有序表的元素逐一进行比较，将较小的元素放入新的有序表中。

代码实现：

1. 数组储存+归并排序

#include <iostream>
using namespace std;

void merge(int a[], int b[], int c[], int n, int m)
{
    int i = 0, j = 0, k = 0;
    while (i < n && j < m)
    {
        if (a[i] <= b[j])
            c[k++] = a[i++];
        else
            c[k++] = b[j++];
    }
    while (i < n)
        c[k++] = a[i++];
    while (j < m)
        c[k++] = b[j++];
}

int main()
{
    int a[5] = {1, 3, 5, 7, 9};
    int b[4] = {2, 4, 6, 8};
    int c[9];

    merge(a, b, c, 5, 4);

    for (int i = 0; i < 9; i++)
        cout << c[i] << " ";

    return 0;
}

2. 数组储存+顺序比较法

#include <iostream>
using namespace std;

void merge(int a[], int b[], int c[], int n, int m)
{
    int i = 0, j = 0, k = 0;
    while (i < n && j < m)
    {
        if (a[i] <= b[j])
            c[k++] = a[i++];
        else
            c[k++] = b[j++];
    }
    while (i < n)
        c[k++] = a[i++];
    while (j < m)
        c[k++] = b[j++];
}

int main()
{
    int a[5] = {1, 3, 5, 7, 9};
    int b[4] = {2, 4, 6, 8};
    int c[9];

    merge(a, b, c, 5, 4);

    for (int i = 0; i < 9; i++)
        cout << c[i] << " ";

    return 0;
}

3. 链表储存+归并排序

#include <iostream>
using namespace std;

struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode *merge(ListNode *l1, ListNode *l2)
{
    ListNode *dummy = new ListNode(-1);
    ListNode *cur = dummy;

    while (l1 && l2)
    {
        if (l1->val <= l2->val)
        {
            cur->next = l1;
            l1 = l1->next;
        }
        else
        {
            cur->next = l2;
            l2 = l2->next;
        }
        cur = cur->next;
    }

    if (l1)
        cur->next = l1;
    if (l2)
        cur->next = l2;

    return dummy->next;
}

int main()
{
    ListNode *l1 = new ListNode(1);
    l1->next = new ListNode(3);
    l1->next->next = new ListNode(5);
    l1->next->next->next = new ListNode(7);
    l1->next->next->next->next = new ListNode(9);

    ListNode *l2 = new ListNode(2);
    l2->next = new ListNode(4);
    l2->next->next = new ListNode(6);
    l2->next->next->next = new ListNode(8);

    ListNode *l3 = merge(l1, l2);

    while (l3)
    {
        cout << l3->val << " ";
        l3 = l3->next;
    }

    return 0;
}

4. 链表储存+顺序比较法

#include <iostream>
using namespace std;

struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode *merge(ListNode *l1, ListNode *l2)
{
    ListNode *dummy = new ListNode(-1);
    ListNode *cur = dummy;

    while (l1 && l2)
    {
        if (l1->val <= l2->val)
        {
            cur->next = l1;
            l1 = l1->next;
        }
        else
        {
            cur->next = l2;
            l2 = l2->next;
        }
        cur = cur->next;
    }

    if (l1)
        cur->next = l1;
    if (l2)
        cur->next = l2;

    return dummy->next;
}

int main()
{
    ListNode *l1 = new ListNode(1);
    l1->next = new ListNode(3);
    l1->next->next = new ListNode(5);
    l1->next->next->next = new ListNode(7);
    l1->next->next->next->next = new ListNode(9);

    ListNode *l2 = new ListNode(2);
    l2->next = new ListNode(4);
    l2->next->next = new ListNode(6);
    l2->next->next->next = new ListNode(8);

    ListNode *l3 = merge(l1, l2);

    while (l3)
    {
        cout << l3->val << " ";
        l3 = l3->next;
    }

    return 0;
}

性能分析：

从代码实现来看，归并排序的时间复杂度为O(nlogn)，顺序比较法的时间复杂度为O(n)，其中n为两个表的元素总数。对于数组储存，归并排序的空间复杂度为O(n)，顺序比较法的空间复杂度为O(n)，因为需要额外的空间存储合并后的表。对于链表储存，归并排序的空间复杂度为O(1)，顺序比较法的空间复杂度为O(1)，因为只需要改变指针指向，不需要额外的空间存储合并后的表。因此，链表储存+归并排序的性能最优。