两个表合并成一个有序表。要求设计两种以上储存方式、两种以上处理流程方式。分析各代码性能。

储存方式：

1. 数组：将两个表储存在两个数组中，再将两个数组合并成一个新的有序数组。
2. 链表：将两个表储存在两个链表中，再将两个链表合并成一个新的有序链表。

处理流程方式：

1. 归并排序：将两个有序表合并成一个有序表的经典算法，通过递归分治的方式将表分成更小的子表，再将子表两两合并，直到合并成一个完整的有序表。时间复杂度为O(nlogn)。
2. 双指针：将两个有序表的头部元素进行比较，将较小的元素放入新的有序表中，再将指针向后移动，直到其中一个表的元素全部放入新的有序表中，再将剩余的元素全部放入新的有序表中。时间复杂度为O(n)。

代码性能分析：

- 数组+归并排序：空间复杂度为O(n)，时间复杂度为O(nlogn)，适用于数据量较大的情况。
- 链表+归并排序：空间复杂度为O(1)，时间复杂度为O(nlogn)，适用于数据量较大且内存资源有限的情况。
- 数组+双指针：空间复杂度为O(n)，时间复杂度为O(n)，适用于数据量较小的情况。
- 链表+双指针：空间复杂度为O(1)，时间复杂度为O(n)，适用于数据量较小且内存资源有限的情况。

相关问题

两个表合并成一个有序表。要求设计两种以上储存方式、两种以上处理流程方式。的代码

以下是一种基于链表的储存方式和一种归并排序的处理流程方式的代码实现：

储存方式一：链表

// 定义链表节点结构体
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};

// 合并两个有序链表
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode dummy(0);
ListNode* tail = &dummy;

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

tail->next = l1 ? l1 : l2;

return dummy.next;
}

// 合并多个有序链表
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.empty()) {
return NULL;
}

int n = lists.size();

while (n > 1) {
int k = (n + 1) / 2;
for (int i = 0; i < n / 2; i++) {
lists[i] = mergeTwoLists(lists[i], lists[i + k]);
}
n = k;
}

return lists[0];
}

储存方式二：数组

// 合并两个有序数组
vector<int> mergeTwoArrays(vector<int>& nums1, vector<int>& nums2) {
vector<int> res;
int m = nums1.size(), n = nums2.size();
int i = 0, j = 0;

while (i < m && j < n) {
if (nums1[i] <= nums2[j]) {
res.push_back(nums1[i]);
i++;
} else {
res.push_back(nums2[j]);
j++;
}
}

while (i < m) {
res.push_back(nums1[i]);
i++;
}

while (j < n) {
res.push_back(nums2[j]);
j++;
}

return res;
}

// 合并多个有序数组
vector<int> mergeKArrays(vector<vector<int>>& nums) {
if (nums.empty()) {
return {};
}

while (nums.size() > 1) {
vector<vector<int>> temp;
int n = nums.size();

for (int i = 0; i < n - 1; i += 2) {
temp.push_back(mergeTwoArrays(nums[i], nums[i + 1]));
}

if (n % 2 == 1) {
temp.push_back(nums[n - 1]);
}

nums = temp;
}

return nums[0];
}

处理流程方式一：归并排序

// 归并排序
void mergeSort(vector<int>& nums, int left, int right) {
if (left >= right) {
return;
}

int mid = (left + right) / 2;
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);

vector<int> temp(right - left + 1);
int i = left, j = mid + 1, k = 0;

while (i <= mid && j <= right) {
if (nums[i] <= nums[j]) {
temp[k] = nums[i];
i++;
} else {
temp[k] = nums[j];
j++;
}
k++;
}

while (i <= mid) {
temp[k] = nums[i];
i++;
k++;
}

while (j <= right) {
temp[k] = nums[j];
j++;
k++;
}

for (int p = 0; p < temp.size(); p++) {
nums[left + p] = temp[p];
}
}

// 合并多个有序数组
vector<int> mergeKArrays(vector<vector<int>>& nums) {
if (nums.empty()) {
return {};
}

vector<int> res;

for (int i = 0; i < nums.size(); i++) {
for (int j = 0; j < nums[i].size(); j++) {
res.push_back(nums[i][j]);
}
}

mergeSort(res, 0, res.size() - 1);

return res;
}

处理流程方式二：堆排序

// 堆排序
void heapSort(vector<int>& nums) {
int n = nums.size();
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(nums, n, i);
}
for (int i = n - 1; i >= 0; i--) {
swap(nums[0], nums[i]);
heapify(nums, i, 0);
}
}

void heapify(vector<int>& nums, int n, int i) {
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;

if (l < n && nums[l] > nums[largest]) {
largest = l;
}

if (r < n && nums[r] > nums[largest]) {
largest = r;
}

if (largest != i) {
swap(nums[i], nums[largest]);
heapify(nums, n, largest);
}
}

// 合并多个有序数组
vector<int> mergeKArrays(vector<vector<int>>& nums) {
if (nums.empty()) {
return {};
}

vector<int> res;

for (int i = 0; i < nums.size(); i++) {
for (int j = 0; j < nums[i].size(); j++) {
res.push_back(nums[i][j]);
}
}

heapSort(res);

return res;
}

课后作业-07 内容：07. 两个表合并成一个有序表。要求设计两种以上储存方式、两种以上处理流程方式。分析各代码性能。 要求： 抽象数据类型独立实现。

抽象数据类型：有序表

定义：

- 数据元素：具有相同数据类型的元素组成。
- 结构属性：有序表是一种线性结构，相邻数据元素具有前驱和后继关系。
- 基本操作：插入、删除、查找、合并。

实现方式：

1. 储存方式一：顺序存储结构

使用一维数组存储有序表，插入、删除、查找操作需要移动元素，合并操作需要新建一个数组。

class OrderedList:
    def __init__(self, maxsize):
        self.maxsize = maxsize
        self.array = [None] * self.maxsize
        self.length = 0

    def __len__(self):
        return self.length

    def __getitem__(self, index):
        if index < 0 or index >= self.length:
            raise IndexError('Index out of range')
        return self.array[index]

    def __setitem__(self, index, value):
        if index < 0 or index >= self.length:
            raise IndexError('Index out of range')
        self.array[index] = value

    def insert(self, value):
        if self.length == self.maxsize:
            raise Exception('OrderedList is full')
        index = 0
        while index < self.length and self.array[index] < value:
            index += 1
        for i in range(self.length, index, -1):
            self.array[i] = self.array[i-1]
        self.array[index] = value
        self.length += 1

    def delete(self, value):
        index = 0
        while index < self.length and self.array[index] != value:
            index += 1
        if index == self.length:
            raise ValueError('Value not found')
        for i in range(index, self.length-1):
            self.array[i] = self.array[i+1]
        self.length -= 1

    def find(self, value):
        index = 0
        while index < self.length and self.array[index] != value:
            index += 1
        if index == self.length:
            raise ValueError('Value not found')
        return index

    def merge(self, other):
        if self.length + other.length > self.maxsize:
            raise Exception('OrderedList is full')
        i = j = k = 0
        while i < self.length and j < other.length:
            if self.array[i] < other.array[j]:
                self.array[k] = self.array[i]
                i += 1
            else:
                self.array[k] = other.array[j]
                j += 1
            k += 1
        while i < self.length:
            self.array[k] = self.array[i]
            i += 1
            k += 1
        while j < other.length:
            self.array[k] = other.array[j]
            j += 1
            k += 1
        self.length += other.length

2. 储存方式二：链式存储结构

使用链表存储有序表，插入、删除、查找操作需要遍历链表，合并操作需要新建一个链表。

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class OrderedList:
    def __init__(self):
        self.head = Node(None)
        self.length = 0

    def __len__(self):
        return self.length

    def __getitem__(self, index):
        if index < 0 or index >= self.length:
            raise IndexError('Index out of range')
        node = self.head.next
        for i in range(index):
            node = node.next
        return node.value

    def __setitem__(self, index, value):
        if index < 0 or index >= self.length:
            raise IndexError('Index out of range')
        node = self.head.next
        for i in range(index):
            node = node.next
        node.value = value

    def insert(self, value):
        node = self.head
        while node.next and node.next.value < value:
            node = node.next
        new_node = Node(value)
        new_node.next = node.next
        node.next = new_node
        self.length += 1

    def delete(self, value):
        node = self.head
        while node.next and node.next.value != value:
            node = node.next
        if not node.next:
            raise ValueError('Value not found')
        node.next = node.next.next
        self.length -= 1

    def find(self, value):
        node = self.head.next
        index = 0
        while node and node.value != value:
            node = node.next
            index += 1
        if not node:
            raise ValueError('Value not found')
        return index

    def merge(self, other):
        new_list = OrderedList()
        i = j = 0
        while i < self.length and j < other.length:
            if self[i] < other[j]:
                new_list.insert(self[i])
                i += 1
            else:
                new_list.insert(other[j])
                j += 1
        while i < self.length:
            new_list.insert(self[i])
            i += 1
        while j < other.length:
            new_list.insert(other[j])
            j += 1
        return new_list

3. 处理流程方式一：顺序处理

先将两个表合并成一个无序表，再对无序表进行排序，得到有序表。

def merge_sort(lst):
    if len(lst) <= 1:
        return lst
    mid = len(lst) // 2
    left = merge_sort(lst[:mid])
    right = merge_sort(lst[mid:])
    return merge(left, right)

def merge(lst1, lst2):
    i = j = 0
    new_lst = []
    while i < len(lst1) and j < len(lst2):
        if lst1[i] < lst2[j]:
            new_lst.append(lst1[i])
            i += 1
        else:
            new_lst.append(lst2[j])
            j += 1
    new_lst += lst1[i:]
    new_lst += lst2[j:]
    return new_lst

def merge_ordered_lists(lst1, lst2):
    lst = []
    for value in lst1:
        lst.append(value)
    for value in lst2:
        lst.append(value)
    return merge_sort(lst)

4. 处理流程方式二：并行处理

将两个表分别拆分成若干个子表，分别进行合并，最后将所有子表合并成一个有序表。

import threading

class MergeThread(threading.Thread):
    def __init__(self, lst1, lst2, result):
        threading.Thread.__init__(self)
        self.lst1 = lst1
        self.lst2 = lst2
        self.result = result

    def run(self):
        self.result.extend(merge(self.lst1, self.lst2))

def merge_ordered_lists(lst1, lst2):
    result = []
    threads = []
    num_threads = min(len(lst1), len(lst2))
    for i in range(num_threads):
        len1 = len(lst1) // num_threads
        len2 = len(lst2) // num_threads
        start1 = i * len1
        end1 = start1 + len1
        start2 = i * len2
        end2 = start2 + len2
        if i == num_threads - 1:
            end1 = len(lst1)
            end2 = len(lst2)
        thread = MergeThread(lst1[start1:end1], lst2[start2:end2], result)
        threads.append(thread)
        thread.start()
    for thread in threads:
        thread.join()
    return merge_sort(result)

性能分析：

1. 储存方式一：顺序存储结构

- 插入、删除、查找操作的时间复杂度均为 O(n)，其中 n 为有序表长度。
- 合并操作的时间复杂度为 O(m+n)，其中 m 和 n 分别为两个有序表的长度。
- 空间复杂度为 O(m+n)，需要新建一个长度为 m+n 的数组。

2. 储存方式二：链式存储结构

- 插入、删除、查找操作的时间复杂度均为 O(n)，其中 n 为有序表长度。
- 合并操作的时间复杂度为 O(m+n)，其中 m 和 n 分别为两个有序表的长度。
- 空间复杂度为 O(m+n)，需要新建一个长度为 m+n 的链表。

3. 处理流程方式一：顺序处理

- 合并操作的时间复杂度为 O((m+n)log(m+n))，其中 m 和 n 分别为两个有序表的长度。
- 空间复杂度为 O(m+n)，需要新建一个长度为 m+n 的数组。

4. 处理流程方式二：并行处理

- 合并操作的时间复杂度为 O((m+n)log(m+n)/p)，其中 m 和 n 分别为两个有序表的长度，p 为线程数。
- 空间复杂度为 O(m+n)，需要新建一个长度为 m+n 的数组。