蓝桥杯Python赛道备赛——Day3：排序算法（二）（归并排序、堆排序、桶排序）

   本博客是蓝桥杯备赛系列中排序算法的第二期，包括：归并排序、堆排序和桶排序。每一个算法都在给出概念解释的同时，给出了示例代码，以供低年级师弟师妹们学习和练习。

   由于本期的三个算法的复杂度相对来说要高于上一期的三个算法，因此，每个算法均以某个待排序的数组为例，进行逐步分析。

   前序知识：
（1）Python基础语法
（2）Python基础算法
（3）基本数据结构：二叉树初步（知道他是啥就好，详细的数据结构内容计划在Day4讲解）。

   Tips：若对基本数据结构不太了解，可以先往下看，当看到不太懂的内容（如：“堆”）时，再去搜索。

---

一、归并排序

1. 流程示意图：

2. 举例说明：
   就像上图中所描述的那样，先进行拆分，再逐步合并。
（1）步骤1：递归拆分

原始数组：[38,27,43,3,9,82,10]
第1层拆分：左=[38,27,43] 右=[3,9,82,10]
第2层拆分：左左=[38] 左右=[27,43] | 右左=[3,9] 右右=[82,10]
继续拆分直到所有子数组长度为1

（2）步骤2：有序合并

左子数组：[27,38,43]  右子数组：[3,9,10,82]
比较过程：3<27 → 填3；9<27 → 填9；10<27 → 填10；27<82 → 填27...
最终结果：[3,9,10,27,38,43,82]

3. 性能分析
（1）优点：

• 稳定排序（相同值保持原顺序）
• 时间复杂度稳定O(n log n)
• 适合链表等非连续存储结构

（2）缺点：

• 需要额外O(n)存储空间
• 递归调用栈可能造成内存开销
• 小规模数据效率低于插入排序

4. 示例代码：

# 归并排序
import numpy as npdef merge_sort(arr):# 递归终止条件：当数组长度<=1时直接返回if len(arr) <= 1:return arr# 分治步骤：将数组平分成左右两部分mid = len(arr) // 2left = merge_sort(arr[:mid])  # 递归处理左半部分right = merge_sort(arr[mid:]) # 递归处理右半部分# 合并两个有序数组return merge(left, right)def merge(left, right):merged = np.empty(len(left)+len(right), dtype=left.dtype) # 创建空数组存放结果l = r = i = 0  # 初始化三个指针# 比较左右数组元素并填充while l < len(left) and r < len(right):if left[l] <= right[r]:merged[i] = left[l]l += 1else:merged[i] = right[r]r += 1i += 1# 处理剩余元素merged[i:] = left[l:] if l < len(left) else right[r:]return merged# 示例运行
arr = np.array([38, 27, 43, 3, 9, 82, 10])
print("原数组:", arr)
sorted_arr = merge_sort(arr)
print("归并排序结果:", sorted_arr)

二、堆排序

1. 流程示意图：

2. 举例说明：
（1）步骤1：构建“大根堆”（确保“子节点”永远小于其“双亲节点”）

初始数组：[12,11,13,5,6,7]
构建堆过程：调整节点1（11）→ 无交换调整节点0（12）→ 与13交换 → [13,11,12,5,6,7]

（2）步骤2：排序阶段，本质是“大根堆”的性质维护

第1次交换后：[7,11,12,5,6,13]
重新堆化后：[12,11,7,5,6,13]
第2次交换后：[6,11,7,5,12,13]
...

3. 性能分析
（1）优点：

• 原地排序（空间复杂度O(1)）
• 最坏情况仍保持O(n log n)
• 适合实时数据处理

（2）缺点：

• 不稳定排序
• 缓存不友好（跳跃访问）
• 实现复杂度较高

4. 示例代码：

# 堆排序
import numpy as npdef heapify(arr, n, i):largest = i  # 初始化最大元素为根节点left = 2 * i + 1right = 2 * i + 2# 检查左子节点是否大于根if left < n and arr[left] > arr[largest]:largest = left# 检查右子节点是否大于当前最大值if right < n and arr[right] > arr[largest]:largest = right# 如果最大值不在根节点，进行交换并递归调整if largest != i:arr[i], arr[largest] = arr[largest], arr[i]heapify(arr, n, largest)def heap_sort(arr):n = len(arr)# 构建最大堆（从最后一个非叶子节点开始）for i in range(n//2 - 1, -1, -1):heapify(arr, n, i)# 逐个提取元素for i in range(n-1, 0, -1):arr[i], arr[0] = arr[0], arr[i]  # 交换堆顶和末尾元素heapify(arr, i, 0)  # 调整剩余元素的堆结构return arr# 示例运行
arr = np.array([12, 11, 13, 5, 6, 7])
print("\n原数组:", arr)
heap_sort(arr)
print("堆排序结果:", arr)

三、桶排序

1. 基本步骤：
（1）步骤1：分桶策略
   示例：数据范围0-49，桶大小10 → 5个桶（0-9,10-19,…40-49）
（2）步骤2：桶内排序
   使用任意排序算法，对桶内的数据进行排序。因此，桶内排序算法的选择将影响整体性能。

2. 性能分析
（1）优点：

• 线性时间复杂度O(n+k)（k为桶数量）
• 稳定排序（若桶内排序稳定）
• 适合外部排序场景

（2）缺点：

• 依赖数据均匀分布
• 需要额外内存存储桶
• 空桶会造成空间浪费

3. 示例代码：

# 桶排序
import numpy as npdef bucket_sort(arr, bucket_size=5):# 确定数据范围min_val, max_val = np.min(arr), np.max(arr)# 计算需要的桶数量bucket_count = (max_val - min_val) // bucket_size + 1buckets = [[] for _ in range(bucket_count)]  # 初始化空桶# 元素分配到桶中for num in arr:idx = (num - min_val) // bucket_sizebuckets[idx].append(num)# 对每个桶内部排序（这里使用内置排序）sorted_arr = np.empty_like(arr)i = 0for bucket in buckets:if len(bucket) > 0:sorted_bucket = np.sort(bucket)  # 实际比赛可用其他排序算法sorted_arr[i:i+len(sorted_bucket)] = sorted_bucketi += len(sorted_bucket)return sorted_arr# 示例运行
arr = np.array([29, 25, 3, 49, 9, 37, 21, 43])
print("\n原数组:", arr)
sorted_arr = bucket_sort(arr)
print("桶排序结果:", sorted_arr)