使用Python实现归并排序算法
归并排序基于分治法，核心分三步：分解（将数组拆分为左右子数组，直至单元素）、递归排序（各子数组递归排序）、合并（合并有序子数组为整体有序数组）。 以数组[3,1,4,2]为例，分解后递归排序各子数组，再合并为[1,2,3,4]。Python实现含合并函数（按序合并两个有序子数组）与递归排序函数（分解并递归调用合并）。 其特点：时间复杂度O(n log n)，空间复杂度O(n)（需额外存储合并结果），为稳定排序（相等元素相对顺序不变）。
阅读全文使用Python实现堆排序算法
堆排序是利用堆数据结构的高效排序算法，时间复杂度稳定为O(n log n)，空间复杂度O(1)，适合大规模数据排序。堆是完全二叉树，父节点值≥（最大堆）或≤（最小堆）子节点值。数组中堆的索引关系：父节点i的子节点为2i+1、2i+2，子节点j的父节点为(j-1)//2。 核心操作包括：1. **Heapify**：调整以i为根的子树为最大堆，递归比较子节点并交换；2. **构建最大堆**：从最后非叶子节点（n//2-1）向上调整所有节点，确保整体满足最大堆性质。 排序流程：先构建最大堆，再反复交换堆顶（最大值）与堆尾元素，同时调用Heapify调整剩余元素为最大堆，最终得到有序数组。堆排序为原地排序，适用于大数据量场景。
阅读全文使用Python实现快速排序算法
快速排序基于“分而治之”思想，核心是选基准值分区并递归排序。基本思路：选基准值（如数组首元素），将数组分为小于和大于基准值的两部分，再递归处理子数组。 分区过程是关键：通过左右指针遍历，右指针左移找小于基准值元素，左指针右移找大于基准值元素，交换后继续，直到指针相遇，交换基准值到最终位置，完成分区。 Python实现中，`partition`函数确定基准位置，`quick_sort`递归处理左右子数组。测试代码验证了排序效果。 复杂度：平均O(n log n)（分区均衡），最坏O(n²)（如已排序数组且基准选首元素，可通过随机选基准优化）。 快速排序是高效实用的排序算法，广泛应用于实际场景，理解其分区逻辑和递归过程是掌握排序算法的关键。
阅读全文