课后作业-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 的数组。