Python 归并排序教程
最后修改于 2025年3月8日
在本文中，我们将解释归并排序算法，并演示它在 Python 中的使用。
算法是解决问题或执行计算的逐步过程。算法是计算机科学和编程的基础。
排序 是以特定顺序（例如升序或降序）排列数据的过程。排序对于高效的数据检索和分析至关重要。
常用排序算法
一些常见的排序算法包括
- 气泡排序
- 选择排序
- 插入排序
- 归并排序
- 快速排序
- 堆排序
归并排序算法
归并排序是一种分而治之的算法。它将输入数组分成两半，递归地对它们进行排序，然后合并两个已排序的半部分。
归并排序示例
下面是归并排序算法的 Python 实现。
merge_sort.py
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
merge_sort(left_half)
merge_sort(right_half)
i = j = k = 0
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
arr[k] = left_half[i]
i += 1
else:
arr[k] = right_half[j]
j += 1
k += 1
while i < len(left_half):
arr[k] = left_half[i]
i += 1
k += 1
while j < len(right_half):
arr[k] = right_half[j]
j += 1
k += 1
def sort_ascending(arr):
merge_sort(arr)
return arr
def sort_descending(arr):
merge_sort(arr)
return arr[::-1]
# Example usage
numbers = [38, 27, 43, 3, 9, 82, 10]
words = ["apple", "banana", "cherry", "date", "elderberry"]
print("Sorted numbers (ascending):", sort_ascending(numbers))
print("Sorted numbers (descending):", sort_descending(numbers))
print("Sorted words (ascending):", sort_ascending(words))
print("Sorted words (descending):", sort_descending(words))
merge_sort 函数按升序对数组进行排序。 sort_ascending 和 sort_descending 函数使用 merge_sort 分别按升序和降序对数组进行排序。
$ ./merge_sort.py Sorted numbers (ascending): [3, 9, 10, 27, 38, 43, 82] Sorted numbers (descending): [82, 43, 38, 27, 10, 9, 3] Sorted words (ascending): ['apple', 'banana', 'cherry', 'date', 'elderberry'] Sorted words (descending): ['elderberry', 'date', 'cherry', 'banana', 'apple']
归并排序与快速排序的比较
归并排序和快速排序都是高效的排序算法。归并排序的时间复杂度始终为 O(n log n)，而快速排序的平均时间复杂度为 O(n log n)，但在最坏情况下可能会降低到 O(n^2)。
下面是一个比较归并排序和快速排序性能的基准。
benchmark.py
import time
import random
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
def benchmark(sort_func, arr):
start_time = time.time()
sort_func(arr)
end_time = time.time()
return end_time - start_time
# Generate a large list of random numbers
random_numbers = [random.randint(0, 10000) for _ in range(10000)]
# Benchmark Merge Sort
merge_sort_time = benchmark(lambda arr: merge_sort(arr), random_numbers.copy())
# Benchmark Quick Sort
quick_sort_time = benchmark(lambda arr: quick_sort(arr), random_numbers.copy())
print(f"Merge Sort Time: {merge_sort_time:.6f} seconds")
print(f"Quick Sort Time: {quick_sort_time:.6f} seconds")
该基准比较了归并排序和快速排序对大量随机数列表进行排序所花费的时间。
来源
在本文中，我们已经解释并演示了 Python 中的归并排序算法。
作者
列出所有 Python 教程。