Java堆排序算法详解及性能分析270

堆排序是一种高效的排序算法，它基于堆数据结构。堆是一种特殊的树状数据结构，满足堆性质：父节点的值总是大于或等于（大根堆）或小于或等于（小根堆）其子节点的值。Java中，我们可以利用堆的性质来实现高效的排序。

本文将深入探讨Java中的堆排序算法，包括其原理、实现细节、时间复杂度和空间复杂度分析，以及与其他排序算法的比较。我们将提供完整的Java代码实现，并通过实例分析来说明其工作过程。

堆数据结构

在理解堆排序之前，我们需要先了解堆数据结构。堆通常用数组来实现，一个大小为n的堆可以表示为一个长度为n+1的数组(为了方便索引从1开始)。堆的根节点位于数组的索引1处。对于一个节点i，其左子节点位于2i，右子节点位于2i+1，父节点位于⌊i/2⌋。

大根堆：父节点的值大于等于其子节点的值。

小根堆：父节点的值小于等于其子节点的值。

堆排序使用大根堆来实现降序排序，使用小根堆来实现升序排序。下文我们将以大根堆为例进行讲解，小根堆的实现只需要做细微的修改。

堆排序算法步骤

堆排序算法主要分为两个步骤：构建堆和堆化。

1. 构建堆 (Build Heap)

构建堆的过程是将输入数组转换成一个大根堆。这可以通过自底向上地调整堆的结构来实现。从数组的最后一个非叶子节点开始(⌊n/2⌋)，依次向上调整每个节点，使其满足大根堆性质。调整过程需要使用一个名为`heapify`的方法。

2. 堆化 (Heapify)

`heapify`方法是堆排序的核心。它接收一个数组，一个节点索引以及数组的长度作为输入。该方法确保以给定索引为根的子树满足大根堆性质。如果某个节点不满足大根堆性质（其值小于其子节点的值），则需要将其与最大的子节点交换，并递归地调用`heapify`方法来调整交换后的子树。

3. 排序 (Sort)

构建好大根堆后，堆排序算法开始排序。首先，将堆顶元素（最大元素）与数组的最后一个元素交换。然后，将堆的大小减1，再对剩余的元素进行`heapify`操作，使其仍然保持大根堆性质。重复这个过程，直到堆的大小为1，此时数组就已排好序。

Java代码实现

以下是用Java实现的堆排序算法：```java
public class HeapSort {
public static void heapSort(int[] arr) {
int n = ;
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// One by one extract an element from heap
for (int i = n - 1; i > 0; i--) {
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
static void heapify(int arr[], int n, int i) {
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
heapSort(arr);
("Sorted array is");
for (int j : arr)
(j + " ");
}
}
```