Java堆排序算法
最后修改时间：2025 年 4 月 16 日
排序算法简介
算法是解决问题或执行计算的逐步过程。排序算法按特定顺序排列元素，通常是数字或按字典顺序排列。高效排序对于优化其他算法至关重要。
常见的排序算法包括冒泡排序、选择排序、插入排序、归并排序、快速排序和堆排序。每种算法都有不同的时间和空间复杂度特性，使其适用于不同的场景。
堆排序概述
堆排序是一种基于比较的排序算法，它使用二叉堆数据结构。在所有情况下，它的时间复杂度为O(n log n)，使其对于大型数据集非常有效。堆排序是不稳定的，但空间复杂度为O(1)。
该算法的工作原理是首先从输入数据构建一个最大堆。然后，它重复从堆中提取最大元素，并重建堆，直到所有元素都被排序。这种原地排序使其在内存使用上非常有效。
堆排序实现
这是一个用Java实现堆排序的基本示例，用于按升序对整数进行排序。该实现包括两个主要部分：heapify和实际的排序方法。
HeapSort.java
package com.zetcode;
public class HeapSort {
public void sort(int[] arr) {
int n = arr.length;
// Build max heap
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// Extract elements 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;
// Heapify reduced heap
heapify(arr, i, 0);
}
}
void heapify(int[] arr, int n, int i) {
int largest = i; // Initialize largest as root
int left = 2 * i + 1;
int right = 2 * i + 2;
// If left child is larger than root
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// If right child is larger than largest so far
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// If largest is not root
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Recursively heapify affected sub-tree
heapify(arr, n, largest);
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
System.out.println("Original array:");
printArray(arr);
HeapSort heapSort = new HeapSort();
heapSort.sort(arr);
System.out.println("Sorted array:");
printArray(arr);
}
static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
}
此实现首先从输入数组构建一个最大堆。然后，它重复提取最大元素并保持堆的性质。heapify方法确保以索引i为根的子树是一个最大堆。
对文本数据进行排序
堆排序也可以按字典顺序对字符串进行排序。该实现类似于数字版本，但使用compareTo方法比较字符串。
StringHeapSort.java
package com.zetcode;
public class StringHeapSort {
public void sort(String[] arr) {
int n = arr.length;
// Build max heap
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// Extract elements from heap
for (int i = n - 1; i > 0; i--) {
// Move current root to end
String temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// Heapify reduced heap
heapify(arr, i, 0);
}
}
void heapify(String[] arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left].compareTo(arr[largest]) > 0) {
largest = left;
}
if (right < n && arr[right].compareTo(arr[largest]) > 0) {
largest = right;
}
if (largest != i) {
String swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}
public static void main(String[] args) {
String[] words = {"banana", "apple", "orange", "grape", "kiwi"};
System.out.println("Original array:");
printArray(words);
StringHeapSort sorter = new StringHeapSort();
sorter.sort(words);
System.out.println("Sorted array:");
printArray(words);
}
static void printArray(String[] arr) {
for (String word : arr) {
System.out.print(word + " ");
}
System.out.println();
}
}
此版本按升序对字符串进行排序。heapify方法使用String.compareTo进行比较。该算法保持与数字版本相同的O(n log n)时间复杂度。
降序排序
要按降序排序，我们可以修改堆的性质以创建一个最小堆而不是最大堆。或者，我们可以按升序排序，然后反转数组。
DescendingHeapSort.java
package com.zetcode;
public class DescendingHeapSort {
public void sort(int[] arr) {
int n = arr.length;
// Build min heap
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// Extract elements 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;
// Heapify reduced heap
heapify(arr, i, 0);
}
}
void heapify(int[] arr, int n, int i) {
int smallest = i; // Initialize smallest as root
int left = 2 * i + 1;
int right = 2 * i + 2;
// If left child is smaller than root
if (left < n && arr[left] < arr[smallest]) {
smallest = left;
}
// If right child is smaller than smallest so far
if (right < n && arr[right] < arr[smallest]) {
smallest = right;
}
// If smallest is not root
if (smallest != i) {
int swap = arr[i];
arr[i] = arr[smallest];
arr[smallest] = swap;
// Recursively heapify affected sub-tree
heapify(arr, n, smallest);
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
System.out.println("Original array:");
printArray(arr);
DescendingHeapSort heapSort = new DescendingHeapSort();
heapSort.sort(arr);
System.out.println("Sorted array (descending):");
printArray(arr);
}
static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
}
此实现通过更改比较运算符来创建一个最小堆而不是最大堆。最小的元素被移动到数组的末尾，从而产生降序。时间复杂度仍然是O(n log n)。
堆排序与快速排序基准测试
堆排序和快速排序都是高效的排序算法，平均时间复杂度为O(n log n)。但是，它们具有不同的特性，使其适用于不同的场景。
由于更好的缓存性能和更低的常数因子，快速排序通常在实践中更快。但是，它的最坏情况时间复杂度为O(n²)，而堆排序在所有情况下都保持O(n log n)。堆排序也是原地排序。
SortBenchmark.java
package com.zetcode;
import java.util.Arrays;
import java.util.Random;
public class SortBenchmark {
public static void main(String[] args) {
int size = 100000;
int[] arr1 = generateRandomArray(size);
int[] arr2 = Arrays.copyOf(arr1, arr1.length);
// Heap Sort benchmark
long start = System.currentTimeMillis();
sort(arr1);
long heapTime = System.currentTimeMillis() - start;
// Quick Sort benchmark
start = System.currentTimeMillis();
Arrays.sort(arr2); // Uses Dual-Pivot QuickSort
long quickTime = System.currentTimeMillis() - start;
System.out.println("Heap Sort time: " + heapTime + " ms");
System.out.println("Quick Sort time: " + quickTime + " ms");
}
static int[] generateRandomArray(int size) {
Random random = new Random();
int[] arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i] = random.nextInt(size * 10);
}
return arr;
}
static private void sort(int[] arr) {
int n = arr.length;
// Build max heap
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// Extract elements 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;
// Heapify reduced heap
heapify(arr, i, 0);
}
}
static void heapify(int[] arr, int n, int i) {
int largest = i; // Initialize largest as root
int left = 2 * i + 1;
int right = 2 * i + 2;
// If left child is larger than root
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// If right child is larger than largest so far
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// If largest is not root
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Recursively heapify affected sub-tree
heapify(arr, n, largest);
}
}
}
此基准测试将我们的堆排序实现与Java的内置Arrays.sort（它使用双轴快速排序）进行比较。平均而言，快速排序更快，但堆排序在所有情况下都提供一致的性能。
何时使用堆排序
当您需要保证O(n log n)的性能和原地排序时，堆排序特别有用。它非常适合内存有限的系统，或者当最坏情况性能至关重要时。但是，对于大多数通用排序，快速排序或归并排序可能是更好的选择。
堆排序也是优先级队列的基础，并用于图算法，如Dijkstra算法和Prim算法。理解堆排序有助于掌握这些更高级的算法和数据结构。
来源
在本文中，我们介绍了Java中的堆排序算法，包括升序和降序的数字和文本数据的实现。我们还通过一个简单的基准测试将其与快速排序进行了比较。
作者
列出所有Java教程。