用python 要求利用递归函数完成归并排序,测试数据自定,但应测试到尽可能多的情况,比如初始逆序,初始局部有序,初始乱序等等。 【题目描述】归并排序是一种基于归并算法的排序方法,该方法采用分治策略:先将待排序的序列划分成若干长度为1的子序列,即假设待排序数据有n个,则认为初始有n段序列,每段长度为1,接下来两两合并,且合并后的每段内从小到大有序,以此类推……,直到只剩下1段序列为止。 【测试数据】 序列初始长度应分别测试奇数个和偶数个; 序列初始顺序应至少测试初始基本有序,初始逆序,初始乱序; 可以使用文件存储初始测试数据,文件可以是1个或多个。
时间: 2023-12-14 13:03:02 浏览: 61
好的,以下是使用Python语言编写的归并排序递归函数代码:
```python
def merge_sort(arr):
if len(arr) < 2:
return arr
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
left = merge_sort(left)
right = merge_sort(right)
return merge(left, right)
def merge(left, right):
res = []
while left and right:
if left[0] < right[0]:
res.append(left.pop(0))
else:
res.append(right.pop(0))
if left:
res += left
if right:
res += right
return res
```
我们可以使用以下测试数据对该函数进行测试:
```python
arr1 = [5, 2, 8, 3, 1, 9, 4, 6, 7]
arr2 = [6, 1, 8, 2, 9, 3, 7, 4, 5]
arr3 = [1, 2, 3, 4, 5, 6, 7, 8, 9]
arr4 = [9, 8, 7, 6, 5, 4, 3, 2, 1]
print(merge_sort(arr1)) # [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(merge_sort(arr2)) # [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(merge_sort(arr3)) # [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(merge_sort(arr4)) # [1, 2, 3, 4, 5, 6, 7, 8, 9]
```
以上测试数据包括了初始乱序、初始有序和初始逆序的情况。此外,我们还可以根据需要自行生成更多的测试数据。
阅读全文