DS内排—直插排序

### 数据结构中的堆排序 #### 堆排序概述 堆排序是一种基于二叉堆数据结构实现的排序算法。该算法通过构建和调整堆来完成排序操作，时间复杂度为 O(n log n)[^2]。 #### 二叉堆特性 二叉堆是一个近似完全二叉树的数据结构，在逻辑上可以分为两种形式：最大堆（Max Heap）和最小堆（Min Heap）。对于最大堆而言，父节点的关键字总是大于等于子节点关键字；而对于最小堆，则相反。这种性质使得堆顶元素始终是整个集合的最大值或最小值[^3]。 #### 构建最大堆/最小堆 为了执行堆排序，首先要将待排序序列构建成一个初始堆。通常情况下会选择构建最大堆以便升序排列最终结果。具体过程如下： 1. 将给定数组视为一棵完整的二叉树； 2. 自底向上遍历非叶子节点并调用 `heapify` 函数修复当前子树使其满足堆属性； 3. 完成上述步骤后即得到所需类型的初始堆。 ```python def heapify(arr, n, i): largest = i l = 2 * i + 1 r = 2 * i + 2 if l < n and arr[i] < arr[l]: largest = l if r < n and arr[largest] < arr[r]: largest = r if largest != i: arr[i],arr[largest] = arr[largest],arr[i] heapify(arr, n, largest) def build_heap(arr): n = len(arr) for i in range(n // 2 - 1, -1, -1): heapify(arr, n, i) ``` #### 执行堆排序 一旦建立了合适的堆之后就可以开始正式排序了。每次取出堆顶元素作为已排序部分的第一个元素，并将其与最后一个未排序位置交换，随后减少堆大小并对新形成的根节点再次应用 `heapify` 来维持剩余部分仍保持有效堆形态直到全部元素都被处理完毕为止。 ```python def heap_sort(arr): build_heap(arr) for i in range(len(arr)-1, 0, -1): arr[i], arr[0] = arr[0], arr[i] heapify(arr, i, 0) ``` #### 特点总结 - 时间复杂度稳定为 O(n log n)，适用于大规模数据集。 - 是一种原地排序算法，只需要占用少量额外空间。 - 不稳定性意味着相同键值记录之间的相对顺序可能会改变。 - 对于内存敏感的应用场景特别有用，因为不需要大量辅助存储资源即可工作良好[^4]。