归并排序 vs 快速排序：Python代码实现及性能比较

本文将分别使用 Python 实现归并排序和快速排序算法，并通过实验比较两种算法在不同输入规模下的运行时间，分析其时间复杂度和空间复杂度，最后总结两种算法的优缺点。

1. 算法实现

1.1 归并排序pythondef 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): ''' 合并两个有序数组 ''' res = [] i = j = 0 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.2 快速排序pythondef 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. 性能测试

以下代码测试了归并排序和快速排序在不同输入规模下的运行时间：pythonimport randomimport timeimport matplotlib.pyplot as plt

def test_sort(sort_func, n): ''' 测试排序算法的运行时间 ''' arr = [random.randint(1, 10000) for _ in range(n)] start = time.time() sort_func(arr) end = time.time() return end - start

测试不同输入规模ns = [64, 128, 256, 512, 1024, 2048, 4096, 8192]merge_times = []quick_times = []for n in ns: merge_times.append(test_sort(merge_sort, n)) quick_times.append(test_sort(quick_sort, n))

绘制运行时间曲线图plt.plot(ns, merge_times, label='Merge Sort')plt.plot(ns, quick_times, label='Quick Sort')plt.xlabel('Input Size')plt.ylabel('Running Time (s)')plt.legend()plt.show()

3. 复杂度分析

3.1 时间复杂度

• 归并排序: 平均情况下为 O(nlogn)，最坏情况下也为 O(nlogn)。* 快速排序: 平均情况下为 O(nlogn)，最坏情况下为 O(n^2)。

3.2 空间复杂度

• 归并排序: 需要额外的 O(n) 空间用于合并两个有序数组。* 快速排序: 平均情况下需要 O(logn) 的栈空间用于递归调用，最坏情况下需要 O(n) 的栈空间。

4. 优劣比较

• 快速排序: 平均情况下，快速排序比归并排序更快，因为它的常数因子更小。空间复杂度方面，快速排序也更优秀，尤其是在平均情况下。* 归并排序: 归并排序是一种稳定的排序算法，而快速排序不是。在某些特定情况下，例如当输入数据已经有序或近乎有序时，快速排序的时间复杂度会退化到 O(n^2)，此时归并排序表现更优秀。

5. 总结

实际应用中，需要根据具体情况选择合适的排序算法。如果对稳定性没有要求，并且数据规模不太大，可以选择快速排序。如果对稳定性有要求，或者数据规模很大，可以选择归并排序。