堆排序的实现 堆排序基于二叉堆数据结构,通常使用数组实现。算法分为两个主要部分:构建堆和排序。 构建最大堆的过程从最后一个非叶子节点开始,向上调整每个子树使其满足堆性质。调整方法是将当前节点与较大子节点交换,递归向下调整。 排序阶段将堆顶元素(最大值)与末尾元素交换,缩小堆范围并重新调整堆。重复此过程直到堆大小为1。 时间复杂度为O(n log n),空间复杂度为O(1)。适用于大规模数据排序,但不稳定。 def heapify(arr, n, i): largest = i left = 2 * i + 1 right = 2 * i + 2 if left < n and arr[l...