13.堆排序：基于完全二叉树的高效排序算法一、什么是堆排序？

一、什么是堆排序堆排序Heap Sort是一种基于完全二叉树的高效排序算法它利用堆的性质最大堆或最小堆将数组转换为有序序列。简单来说堆排序就像 “养猪场选猪王”把数组元素看作一群猪堆的结构就像金字塔越上层的猪体重越大先把猪群整理成最大堆最上面的猪是最重的每次把最上面的猪最大元素放到数组末尾再把剩下的猪重新整理成最大堆重复这个过程直到所有猪都按体重从小到大排好序。二、堆的核心性质堆是一种特殊的完全二叉树分为两种最大堆每个父节点的值都大于或等于它的子节点的值根节点是整个堆的最大值最小堆每个父节点的值都小于或等于它的子节点的值根节点是整个堆的最小值。堆排序通常使用最大堆因为这样可以每次取出最大值放到数组末尾最终得到从小到大的有序数组。三、堆排序的核心步骤堆排序的核心步骤可以分为以下两步构建最大堆将数组转换为最大堆从最后一个非叶子节点开始向上调整每个节点使其满足最大堆的性质排序每次将堆顶元素最大值与数组末尾元素交换然后将剩下的元素重新调整为最大堆重复这个过程直到数组有序。四、堆排序的代码实现1. Python 版本直观易懂def heapify(arr, n, i): # 假设当前节点i是最大的 largest i # 左子节点的索引 left 2 * i 1 # 右子节点的索引 right 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) # 测试 arr [80, 150, 100, 60, 170, 120, 90] print(排序前, arr) heap_sort(arr) print(排序后, arr) # 输出[60, 80, 90, 100, 120, 150, 170]2. C 语言版本更贴近底层#include stdio.h // 交换两个元素 void swap(int* a, int* b) { int temp *a; *a *b; *b temp; } // 调整堆使以i为根的子树满足最大堆性质 void heapify(int arr[], int n, int i) { int largest i; // 假设当前节点i是最大的 int left 2 * i 1; // 左子节点索引 int right 2 * i 2; // 右子节点索引 // 如果左子节点比当前节点大更新最大节点索引 if (left n arr[left] arr[largest]) { largest left; } // 如果右子节点比当前节点大更新最大节点索引 if (right n arr[right] arr[largest]) { largest right; } // 如果最大节点不是当前节点交换并继续调整 if (largest ! i) { swap(arr[i], arr[largest]); // 递归调整交换后的子树 heapify(arr, n, largest); } } // 堆排序函数 void heap_sort(int arr[], int n) { // 第一步构建最大堆从最后一个非叶子节点开始 for (int i n / 2 - 1; i 0; i--) { heapify(arr, n, i); } // 第二步排序逐个取出最大值 for (int i n - 1; i 0; i--) { // 将堆顶元素最大值与数组末尾元素交换 swap(arr[0], arr[i]); // 调整剩下的元素为最大堆 heapify(arr, i, 0); } } // 打印数组 void printArray(int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); } int main() { int arr[] {80, 150, 100, 60, 170, 120, 90}; int n sizeof(arr) / sizeof(arr[0]); printf(排序前); printArray(arr, n); heap_sort(arr, n); printf(排序后); printArray(arr, n); // 输出60 80 90 100 120 150 170 return 0; }五、堆排序的时间复杂度和空间复杂度时间复杂度O (n log n)构建最大堆的时间复杂度为 O (n)排序过程中每次调整堆的时间复杂度为 O (log n)共进行 n 次调整空间复杂度O (1)堆排序是原地排序算法不需要额外的内存空间稳定性不稳定因为交换操作可能会改变相同元素的相对位置。六、堆排序的优化为了提高堆排序的效率可以进行以下优化迭代实现 heapify使用迭代代替递归减少递归调用栈的深度避免栈溢出使用最小堆如果需要得到从大到小的有序数组可以使用最小堆小数组优化当数组的大小小于某个阈值如 10时使用插入排序代替堆排序因为插入排序在小规模数据上效率更高。七、堆排序的实际应用场景堆排序是一种高效、稳定的排序算法常见场景包括大规模数据排序堆排序的时间复杂度稳定为 O (n log n)适合大规模数据排序内存受限场景堆排序是原地排序算法不需要额外的内存空间优先队列堆是优先队列的底层实现用于动态获取最大值或最小值Top K 问题使用堆可以高效地从大量数据中找出前 K 个最大或最小的元素。八、总结堆排序是一种基于完全二叉树的高效排序算法它利用堆的性质将数组转换为有序序列核心步骤是构建最大堆和排序。堆排序的时间复杂度为 O (n log n)空间复杂度为 O (1)是一种稳定、高效的排序算法适合大规模数据排序和内存受限场景。希望这篇文章能帮助你理解堆排序的原理和实现