堆排序算法详解及其 Java 实现

### 堆排序算法详解及其Java实现 #### 一、堆排序概述 堆排序是一种非常高效的排序算法，它利用了二叉堆的数据结构来完成排序的过程。二叉堆可以分为最大堆和最小堆两种类型。最大堆指的是父节点的值总是大于或等于其两个子节点的值；而最小堆则相反，父节点的值总是小于或等于其两个子节点的值。 堆排序的基本思想是先将待排序的序列构造成一个最大堆或最小堆，然后不断地将堆顶元素与堆尾元素交换，减少堆的大小，并重新调整堆的结构，直至堆为空。这一过程会确保每次被交换到堆尾的都是未排序部分中的最大或最小元素，从而逐步完成整个序列的排序。 #### 二、堆排序的步骤 堆排序的具体步骤如下： 1. **构建最大堆**：将初始的无序数组构建成一个最大堆。 2. **交换堆顶元素和末尾元素**：将最大堆的根节点（即最大值）与堆的最后一个元素交换，并将堆的大小减1。 3. **重新调整堆**：对新的根节点进行堆化，使其重新满足最大堆的性质。 4. **重复步骤2和3**，直到堆的大小为1。 #### 三、堆排序的Java实现 下面是一段实现了堆排序的Java代码示例： ```java public class HeapSort { // 主方法：测试堆排序 public static void main(String[] args) { int[] array = {12, 11, 13, 5, 6, 7}; System.out.println("Unsorted array: "); printArray(array); HeapSort heapSort = new HeapSort(); heapSort.sort(array); System.out.println("Sorted array: "); printArray(array); } // 堆排序的主要方法 public void sort(int[] array) { int n = array.length; // 构建最大堆 for (int i = n / 2 - 1; i >= 0; i--) { heapify(array, n, i); } // 一个个从堆中取出元素 for (int i = n - 1; i >= 0; i--) { // 将当前根节点（最大值）移到末尾 int temp = array[0]; array[0] = array[i]; array[i] = temp; // 重新调整剩余的堆 heapify(array, i, 0); } } // 堆化一个子树 private void heapify(int[] array, int n, int i) { int largest = i; // 初始化最大值为根节点 int left = 2 * i + 1; // 左子节点 int right = 2 * i + 2; // 右子节点 // 如果左子节点大于根节点 if (left < n && array[left] > array[largest]) { largest = left; } // 如果右子节点大于目前最大的节点 if (right < n && array[right] > array[largest]) { largest = right; } // 如果最大值不是根节点，则交换并继续堆化 if (largest != i) { int swap = array[i]; array[i] = array[largest]; array[largest] = swap; // 递归地堆化受影响的子树 heapify(array, n, largest); } } // 打印数组 private static void printArray(int[] array) { for (int value : array) { System.out.print(value + " "); } System.out.println(); } } ``` #### 四、代码详解 - **主方法** `main`：在主方法中，首先创建了一个数组，并调用堆排序方法对其进行排序。排序前后，通过`printArray`方法分别打印数组。 - **排序方法** `sort`： 1. **构建最大堆**：从第一个非叶子节点开始，从下至上，从右至左调整整个数组，使其满足最大堆的性质。第一个非叶子节点的索引为`n / 2 - 1`，其中`n`是数组的长度。 2. **交换堆顶元素和末尾元素**：将最大堆的根节点（最大值）与堆的最后一个元素交换，并将堆的大小减1。 3. **重新调整堆**：对新的根节点进行堆化，使其重新满足最大堆的性质。 - **堆化方法** `heapify`：这个方法用于调整一个子树，使其满足最大堆的性质。它通过比较根节点与其左右子节点的值，将最大值调整到根节点位置，并递归地处理受影响的子树。 通过以上步骤，我们可以有效地实现堆排序算法，并应用于各种实际场景中。