在学习数据结构时，排序算法是一个非常重要的主题。在这篇文章中，我们将重点介绍冒泡排序和归并排序这两种常见的排序算法，并给出示例代码。
一、冒泡排序
冒泡排序是最简单的排序算法之一，其基本思想是通过重复遍历待排序的数列，比较相邻元素并交换它们的位置。这样，每一趟遍历后，都能将未排序部分中最大的元素“冒泡”到数列的末端。由于算法简单，冒泡排序适合用于较小规模的数据集，但在较大的数据集上效率较低，平均时间复杂度为O(n^2)。
冒泡排序的实现代码：
def bubble_sort(arr):
n = len(arr)
for i in range(n):
# 设置一个标志位，判断这一趟是否进行了交换
swapped = False
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
# 如果前面的元素比后面的大，进行交换
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
# 如果没有交换，说明数组已经有序，直接退出
if not swapped:
break
return arr
# 测试冒泡排序
array = [64, 34, 25, 12, 22, 11, 90]
print("排序前：", array)
sorted_array = bubble_sort(array)
print("排序后：", sorted_array)
二、归并排序
归并排序是一种高效的排序算法，它采用了分治法的策略。其基本步骤是将一个未排序的数组分成两个子数组，分别对这两个子数组进行排序，再将已经排序的子数组合并成一个最终的排序数组。这种方法的时间复杂度为O(n log n)，适合处理大规模数据。
归并排序的关键在于“归并”的过程。在合并两个已经排好序的数组时，我们可以借助一个临时数组来比较并插入元素。
归并排序的实现代码：
def merge(left, right):
result = []
i = j = 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.extend(left[i:])
result.extend(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) # 合并排序后的数组
# 测试归并排序
array = [38, 27, 43, 3, 9, 82, 10]
print("排序前：", array)
sorted_array = merge_sort(array)
print("排序后：", sorted_array)
三、总结
冒泡排序是一种简单直观的排序算法，尽管其性能在大数据集上较差，但它的实现非常简单，非常适合初学者理解基本的排序逻辑。归并排序则利用了分治策略，具有更高的效率，适合处理大规模的数据，在实际应用中往往表现得更加优越。
对于具体的应用场景，选择合适的排序算法能显著提高程序的性能。同时，学习如何优化和实现这些算法，也为进一步掌握数据结构与算法打下了坚实的基础。希望这篇文章能对你理解和掌握这两种排序算法有所帮助！
