以下是手写List容器的扩展功能实现,包含排序、反转和合并功能。使用Python实现,并确保代码清晰可读:

class MyList:
    def __init__(self, items=None):
        self._items = items if items is not None else []
    
    def __str__(self):
        return str(self._items)
    
    def append(self, item):
        self._items.append(item)
    
    def __len__(self):
        return len(self._items)
    
    # 排序功能(使用归并排序)
    def sort(self):
        """对列表进行升序排序"""
        if len(self._items) <= 1:
            return
        
        # 归并排序实现
        def merge_sort(arr):
            if len(arr) <= 1:
                return arr
            
            mid = len(arr) // 2
            left = merge_sort(arr[:mid])
            right = merge_sort(arr[mid:])
            
            return merge(left, right)
        
        def merge(left, right):
            result = []
            i = j = 0
            while i < len(left) and j < len(right):
                if left[i] < right[j]:
                    result.append(left[i])
                    i += 1
                else:
                    result.append(right[j])
                    j += 1
            result.extend(left[i:])
            result.extend(right[j:])
            return result
        
        self._items = merge_sort(self._items)
    
    # 反转功能
    def reverse(self):
        """原地反转列表元素"""
        left, right = 0, len(self._items) - 1
        while left < right:
            self._items[left], self._items[right] = self._items[right], self._items[left]
            left += 1
            right -= 1
    
    # 合并功能
    def merge(self, other_list):
        """将另一个列表的元素合并到当前列表末尾"""
        if not isinstance(other_list, MyList):
            raise TypeError("参数必须是MyList类型")
        self._items.extend(other_list._items)

# 测试用例
if __name__ == "__main__":
    # 创建列表
    lst1 = MyList([3, 1, 4, 2])
    lst2 = MyList([9, 7, 5])
    
    print("原始列表1:", lst1)
    print("原始列表2:", lst2)
    
    # 测试排序
    lst1.sort()
    print("\n排序后列表1:", lst1)  # 输出: [1, 2, 3, 4]
    
    # 测试反转
    lst2.reverse()
    print("反转后列表2:", lst2)  # 输出: [5, 7, 9]
    
    # 测试合并
    lst1.merge(lst2)
    print("\n合并后列表1:", lst1)  # 输出: [1, 2, 3, 4, 5, 7, 9]

实现说明:

  1. 排序算法

    • 使用归并排序实现,时间复杂度为 $O(n \log n)$
    • 递归分割列表直到单个元素
    • 合并时按顺序比较元素
  2. 反转算法

    • 双指针法原地交换元素
    • 时间复杂度 $O(n)$,空间复杂度 $O(1)$
    • 指针从两端向中间移动并交换元素
  3. 合并功能

    • 直接扩展当前列表
    • 类型检查确保参数是 MyList 实例
    • 时间复杂度 $O(m)$,其中 $m$ 是被合并列表长度

算法复杂度分析:

功能时间复杂度空间复杂度
排序$O(n \log n)$$O(n)$
反转$O(n)$$O(1)$
合并$O(m)$$O(1)$

此实现完整展示了自定义List容器的核心扩展功能,可直接用于实际开发场景。

更多推荐