手写 List 容器的扩展功能:排序、反转、合并的实现
·
以下是手写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]
实现说明:
-
排序算法:
- 使用归并排序实现,时间复杂度为 $O(n \log n)$
- 递归分割列表直到单个元素
- 合并时按顺序比较元素
-
反转算法:
- 双指针法原地交换元素
- 时间复杂度 $O(n)$,空间复杂度 $O(1)$
- 指针从两端向中间移动并交换元素
-
合并功能:
- 直接扩展当前列表
- 类型检查确保参数是
MyList实例 - 时间复杂度 $O(m)$,其中 $m$ 是被合并列表长度
算法复杂度分析:
| 功能 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 排序 | $O(n \log n)$ | $O(n)$ |
| 反转 | $O(n)$ | $O(1)$ |
| 合并 | $O(m)$ | $O(1)$ |
此实现完整展示了自定义List容器的核心扩展功能,可直接用于实际开发场景。
更多推荐
所有评论(0)