堆排序简介

概念：

堆排序是一种基于二叉堆数据结构的排序算法。它的概念是通过将待排序的元素构建成一个二叉堆，然后通过不断地取出堆顶元素并重新调整堆的结构来实现排序。

算法步骤：

1. 构建最大堆（或最小堆）：将待排序的元素构建成一个二叉堆。最大堆的特点是父节点的值大于其子节点的值，最小堆的特点是父节点的值小于其子节点的值。
2. 交换堆顶元素和最后一个元素：将堆顶元素与堆中最后一个元素交换位置，然后将堆的大小减1。
3. 调整堆结构：对交换后的堆顶元素进行调整，使其满足堆的性质。
4. 重复步骤2和步骤3，直到堆的大小为1。

算法特点：

• 堆排序是一种原地排序算法，不需要额外的存储空间。
• 时间复杂度为O(nlogn)，其中n是待排序元素的个数。
• 不稳定排序算法，可能改变相同值的元素的相对顺序。

优点：

• 相对于其他排序算法，堆排序的常数因子较小，因此在大规模数据的排序中表现较好。
• 由于堆排序的每一次交换都是跨越较大的距离，因此对于顺序存储的数据，堆排序的缓存命中率较高。

缺点：

• 堆排序的主要缺点是在排序过程中，需要频繁地进行元素的比较和交换，因此相对于其他排序算法，它的性能较差。
• 不适合对于小规模数据的排序。

适用场景：

• 堆排序适用于大规模数据的排序，尤其是外部排序（数据量无法一次性装入内存）的情况下。
• 由于堆排序对数据的随机访问较多，因此在数据的存储方式为顺序存储时，堆排序的性能较好。

实现代码：

public class HeapSort {public static void heapSort(int[] arr) {int n = arr.length;// 构建最大堆for (int i = n / 2 - 1; i >= 0; i--) {heapify(arr, n, i);}// 交换堆顶元素和最后一个元素，并重新调整堆结构for (int i = n - 1; i >= 0; i--) {int temp = arr[0];arr[0] = arr[i];arr[i] = temp;heapify(arr, i, 0);}}// 调整堆结构public static void heapify(int[] arr, int n, int i) {int largest = 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) {int temp = arr[i];arr[i] = arr[largest];arr[largest] = temp;heapify(arr, n, largest);}}public static void main(String[] args) {int[] arr = { 4, 10, 3, 5, 1, 11, 33, 7, 12, 9 }};heapSort(arr);System.out.println("排序结果：");for (int num : arr) {System.out.print(num + " ");}}
}