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

本文将使用 Python 分别实现归并排序和快速排序两种经典排序算法，并通过随机生成不同规模的数据进行测试，比较两种算法的实际运行时间，最后使用图表展示输入规模与运行时间之间的关系。

1. 归并排序

1.1 算法思路

归并排序采用分治法的思想，将待排序的数组递归地分成两半，直到每个子数组只包含一个元素。然后，将这些已排序的子数组两两合并成更大的排序数组，最终得到完整的排序结果。

1.2 代码实现pythonimport randomimport time

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): i = j = 0 res = [] while i < len(left) and j < len(right): if left[i] < right[j]: res.append(left[i]) i += 1 else: res.append(right[j]) j += 1 res += left[i:] res += right[j:] return res

1.3 测试pythonn_list = [64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536]time_list_merge = []for n in n_list: arr = [random.randint(1, 10000) for _ in range(n)] start_time = time.time() merge_sort(arr) end_time = time.time() time_list_merge.append(end_time - start_time)

print('归并排序的运行时间：', time_list_merge)

2. 快速排序

2.1 算法思路

快速排序也采用了分治法的思想。在每一轮排序中，首先选择一个基准元素，然后将数组分成两个子数组，其中一个子数组的所有元素都小于等于基准元素，另一个子数组的所有元素都大于基准元素。递归地对这两个子数组进行排序，最终得到完整的排序结果。

2.2 代码实现pythonimport randomimport time

def quick_sort(arr): if len(arr) <= 1: return arr pivot = arr[0] left = [x for x in arr[1:] if x <= pivot] right = [x for x in arr[1:] if x > pivot] return quick_sort(left) + [pivot] + quick_sort(right)

2.3 测试pythonn_list = [64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536]time_list_quick = []for n in n_list: arr = [random.randint(1, 10000) for _ in range(n)] start_time = time.time() quick_sort(arr) end_time = time.time() time_list_quick.append(end_time - start_time)

print('快速排序的运行时间：', time_list_quick)

3. 运行时间与输入规模的关系曲线图pythonimport matplotlib.pyplot as plt

plt.plot(n_list, time_list_merge, 'bo-', label='Merge Sort')plt.plot(n_list, time_list_quick, 'ro-', label='Quick Sort')plt.xlabel('Input Size')plt.ylabel('Time (s)')plt.title('Sorting Algorithms Time Complexity')plt.legend()plt.show()

通过运行以上代码，我们可以得到归并排序和快速排序在不同输入规模下的运行时间，并绘制出相应的曲线图。从图中可以看出，随着输入规模的增大，两种算法的运行时间都呈上升趋势。但是，归并排序的运行时间增长速度较为平缓，而快速排序的运行时间增长速度较快。

4. 总结

归并排序和快速排序是两种常用的排序算法，它们的时间复杂度分别为 O(n log n) 和 O(n^2)。在实际应用中，我们需要根据具体的应用场景选择合适的排序算法。