当前位置：首页 > news >正文

Java实现堆排序算法详解及优化

news 来源：原创 2024/9/20 19:39:41

引言

堆排序（Heap Sort）是一种基于堆数据结构的比较排序算法。它具有良好的时间复杂度特性，在许多实际应用中表现出色。本文将详细讲解如何使用Java实现堆排序算法，并结合图解和实例代码，帮助您全面理解这一高级排序算法。同时，我们还将探讨堆排序的优化方法，以进一步提高其性能。

堆排序算法的原理

堆排序通过将数组构建成一个最大堆，然后重复地将堆顶元素与末尾元素交换，并缩小堆的范围，重新调整堆结构来实现排序。

算法步骤

构建最大堆：将数组构建成一个最大堆。
交换并调整堆：将堆顶元素与末尾元素交换，缩小堆的范围，并调整堆结构，直到整个数组有序。

图解堆排序

为了更清晰地展示堆排序的过程，以下使用一个简单示例并分步骤图解：

Java实现堆排序

public class HeapSort {/*** 实现堆排序算法* @param arr 待排序的数组*/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);}}/*** 调整堆的方法* @param arr 待调整的数组* @param n 数组大小* @param i 根节点索引*/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 swap = arr[i];arr[i] = arr[largest];arr[largest] = swap;// 递归调整受影响的子树heapify(arr, n, largest);}}public static void main(String[] args) {// 初始化数组int[] arr = {4, 10, 3, 5, 1};// 调用堆排序方法heapSort(arr);// 输出排序后的数组System.out.println("排序后的数组:");for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}}
}

堆排序的优化方法

使用更小的辅助空间

堆排序是原地排序算法，但在实现过程中可以进一步优化，以减少递归调用的栈空间消耗。

图解优化后的堆排序

Java实现优化后的堆排序

public class OptimizedHeapSort {/*** 实现优化后的堆排序算法* @param arr 待排序的数组*/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);}}/*** 调整堆的方法* @param arr 待调整的数组* @param n 数组大小* @param i 根节点索引*/public static void heapify(int[] arr, int n, int i) {while (true) {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;// 更新根节点索引i = largest;} else {break;}}}public static void main(String[] args) {// 初始化数组int[] arr = {4, 10, 3, 5, 1};// 调用优化后的堆排序方法heapSort(arr);// 输出排序后的数组System.out.println("排序后的数组:");for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}}
}