堆排序（Heap Sort）是一种基于堆数据结构的比较排序算法。堆是一个近似完全二叉树的结构，满足堆属性：即对于最大堆，任何一个节点的值都大于或等于其子节点的值；对于最小堆，任何一个节点的值都小于或等于其子节点的值。
下面的代码例子展示了堆排序的实现，包括构建最大堆、堆排序主函数和辅助函数：
// Java 实现的堆排序 public class HeapSort { // 主函数，用于对输入数组进行排序 public void sort(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); } } // 辅助函数，用于维护堆属性 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 swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap; // 递归地对受影响的子树进行堆化 heapify(arr, n, largest); } } // 测试函数 public static void main(String args[]) { int arr[] = {12, 11, 13, 5, 6, 7}; int n = arr.length; HeapSort ob = new HeapSort(); ob.sort(arr); System.out.println("排序后的数组是:"); printArray(arr); } // 用于打印数组 static void printArray(int arr[]) { int n = arr.length; for (int i = 0; i < n; ++i) { System.out.print(arr[i] + " "); } System.out.println(); } }
代码解析：
构建最大堆： 在sort方法中，我们首先从第一个非叶子节点开始，从右到左从下到上地对每个节点调用heapify方法，这样就能将输入数组构建成一个最大堆。
堆排序： 通过从数组的最后一个元素开始，逐步将根节点（最大值）与当前元素交换，然后对缩小后的堆进行堆化，从而使数组从小到大排序。
堆化（heapify）： heapify方法用于维护堆属性。它通过比较父节点与其子节点的大小，如果子节点大于父节点，则交换它们的位置，并递归地对受影响的子树进行堆化。
打印数组： printArray方法用于输出排序后的数组。
第二个代码例子
这里是另一个堆排序的实现例子，这次使用最小堆来进行排序：
// Java 实现的最小堆排序 public class MinHeapSort { // 主函数，用于对输入数组进行排序 public void sort(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); } } // 辅助函数，用于维护最小堆属性 void heapify(int arr[], int n, int i) { int smallest = i; // 初始化为根节点 int left = 2 * i + 1; // 左子节点 int right = 2 * i + 2; // 右子节点 // 如果左子节点比根节点小 if (left < n && arr[left] < arr[smallest]) { smallest = left; } // 如果右子节点比当前最小值小 if (right < n && arr[right] < arr[smallest]) { smallest = right; } // 如果最小值不是根节点，则交换它们 if (smallest != i) { int swap = arr[i]; arr[i] = arr[smallest]; arr[smallest] = swap; // 递归地对受影响的子树进行堆化 heapify(arr, n, smallest); } } // 测试函数 public static void main(String args[]) { int arr[] = {12, 11, 13, 5, 6, 7}; int n = arr.length; MinHeapSort ob = new MinHeapSort(); ob.sort(arr); System.out.println("排序后的数组是:"); printArray(arr); } // 用于打印数组 static void printArray(int arr[]) { int n = arr.length; for (int i = 0; i < n; ++i) { System.out.print(arr[i] + " "); } System.out.println(); } }
代码解析：
构建最小堆： 在sort方法中，我们首先从第一个非叶子节点开始，从右到左从下到上地对每个节点调用heapify方法，这样就能将输入数组构建成一个最小堆。
堆排序： 通过从数组的最后一个元素开始，逐步将根节点（最小值）与当前元素交换，然后对缩小后的堆进行堆化，从而使数组从大到小排序。
堆化（heapify）： heapify方法用于维护最小堆属性。它通过比较父节点与其子节点的大小，如果子节点小于父节点，则交换它们的位置，并递归地对受影响的子树进行堆化。
通过这两个例子，我们可以看到堆排序的主要步骤和其实现方式。堆排序的时间复杂度为O(n log n)，它是一种不稳定的排序算法，但它的空间复杂度为O(1)，因为它是就地排序（in-place sorting）。
