Python实现归并排序及时间复杂度分析

归并排序是一种高效、稳定的排序算法，采用分治策略，其时间复杂度为O(n log n)。本文将使用Python代码实现归并排序，并通过实验分析其时间复杂度。

1. 归并排序算法实现

以下是Python实现归并排序的代码：pythonimport randomimport timeimport matplotlib.pyplot as plt

def merge(left, right): result = [] i, j = 0, 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 += left[i:] result += right[j:] return result

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)

2. 实验测试

为了测试归并排序算法的性能，我们使用不同规模的随机整数数组进行测试，并记录排序所需时间。pythonn_list = [64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576]avg_times = []for n in n_list: total_time = 0 for _ in range(10): # 重复10次取平均值 arr = [random.randint(1, 10000) for _ in range(n)] start_time = time.time() merge_sort(arr) end_time = time.time() total_time += end_time - start_time avg_time = total_time / 10 avg_times.append(avg_time) print(f'n={n}, avg_time={avg_time:.5f} seconds')

3. 运行时间与输入规模关系图pythonplt.plot(n_list, avg_times)plt.xlabel('输入规模 n')plt.ylabel('平均运行时间 (秒)')plt.title('归并排序运行时间与输入规模关系图')plt.grid(True)plt.show()

4. 时间复杂度和空间复杂度

从实验结果和运行时间曲线图可以看出，随着输入规模的增加，归并排序的运行时间呈现出 O(n log n) 的增长趋势。这是因为归并排序在每一层递归中都需要对数组进行线性时间的归并操作，而递归的层数为 log n。

归并排序的空间复杂度为 O(n)，因为它需要额外的空间来存储归并过程中的临时数组。

结论

归并排序是一种高效稳定的排序算法，其时间复杂度为 O(n log n)，空间复杂度为 O(n)。在处理大规模数据时，归并排序是一个不错的选择。