Java堆排序算法实现详细解析

Java堆排序是一种基于比较的排序算法，它利用了数据结构中的堆这种完全二叉树的特性来实现排序。堆排序算法主要分为两个步骤：构建堆和堆调整。堆是一种特殊的完全二叉树，满足任何父节点的值总是大于或等于其子节点的值，这样的堆被称为最大堆；如果父节点的值总是小于或等于子节点的值，则称为最小堆。堆排序通常采用最大堆实现。 堆排序的算法流程如下： 1. 构建最大堆：将待排序的数组构造成一个最大堆，此时，根节点的值最大。 2. 堆调整：将堆顶元素（当前最大值）与堆中最后一个元素交换，此时堆的大小减一，然后对新的堆顶进行下沉操作，调整为最大堆，保证剩余元素的最大值仍然位于堆顶。 3. 重复步骤2，直到堆的大小为1，此时数组已经是有序的。 Java代码实现堆排序的步骤如下： ```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 l = 2 * i + 1; // 左子节点 int r = 2 * i + 2; // 右子节点 // 如果左子节点大于根节点 if (l < n && arr[l] > arr[largest]) { largest = l; } // 如果右子节点比最大的还大 if (r < n && arr[r] > arr[largest]) { largest = r; } // 如果最大的不是根节点 if (largest != i) { int swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap; // 递归地调整受影响的子树 heapify(arr, n, largest); } } // 打印数组函数 static void printArray(int arr[]) { for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } // 主函数测试堆排序 public static void main(String args[]) { int arr[] = {12, 11, 13, 5, 6, 7}; int n = arr.length; HeapSort hs = new HeapSort(); hs.sort(arr); System.out.println("Sorted array is"); printArray(arr); } } ``` 在上述代码中，`sort` 方法用于执行堆排序算法，`heapify` 方法用于调整堆结构，确保每个父节点的值都大于其子节点的值。`main` 方法中初始化了一个待排序的数组，并调用 `sort` 方法进行排序，最后打印排序后的数组。 注意，堆排序的时间复杂度在最好、平均和最坏情况下均为 O(nlogn)，这是因为构建最大堆需要 O(n) 的时间复杂度，而每次进行堆调整需要 O(logn) 的时间复杂度，并且这种操作需要进行 n-1 次。因此，堆排序是一种不稳定的排序算法。